Does online mean the algorithm learns?

No. An online scheduling or caching rule can make sequential decisions without fitting a statistical model.

Can an online algorithm store old observations?

Yes, unless the problem imposes a memory restriction. Sequential operation does not itself require forgetting past data.

Can it change its internal state?

Yes. State updates are common. Whether it may revise earlier decisions depends on the application and problem definition.

AI Glossary / Mathematics and optimization / Intermediate

Online algorithm

Definition

An online algorithm processes input as it arrives and makes required decisions without knowing the entire future input sequence. It can maintain and update an internal state, but it must operate with the information available at each decision time. The defining feature is incomplete future information, not whether the program is connected to the internet.

What it means

An offline algorithm can inspect its complete input before choosing an answer. An online algorithm faces a sequence of arrivals: a request, measurement, job, or labeled example appears, and the algorithm responds before later inputs are known.

Some online problems make earlier decisions irreversible, such as assigning a job or purchasing a resource. Others allow the algorithm to update estimates or revise stored state. The relevant restrictions belong to the problem definition. Updating tomorrow's model does not retroactively change the prediction that was issued today.

How it works

Specify what arrives at each step, what the algorithm observes, which decision it must make, and when feedback becomes available. The algorithm uses its current state and the newly available information to produce an output and update that state.

Performance can be assessed in several ways. Competitive analysis compares cost with an offline optimum that knows the complete sequence. Online learning often uses regret, comparing accumulated loss with a defined class of alternatives in hindsight. These are different measures and should not be treated as interchangeable labels.

Memory limits, computation time, lookahead, randomization, and the input-generation assumptions also matter. An online algorithm need not use tiny memory, and a streaming algorithm's memory restriction is a separate concern. “Online” alone does not guarantee a real-time deadline or adaptation to a changing statistical distribution.

Three practical examples

1. Resource allocation: assign arriving jobs to available machines before future jobs and their processing requirements are known.

2. Cache management: decide which stored item to evict when a request arrives, without knowing the complete future request sequence.

3. Incremental prediction: issue a forecast, observe its outcome later, and update a learning model for subsequent forecasts using only information revealed so far.

Think of it this way

Think of preparing seats for guests who arrive one at a time without a complete guest list. Each seating choice uses what is currently known, while the best arrangement in hindsight can exploit information that was unavailable earlier.

The analogy captures sequential uncertainty. It does not imply that every online decision must be permanent: a particular application may permit reseating at a cost. A rigorous algorithmic model must specify those revision rules rather than leave them hidden in the story.

Worked example

Consider an illustrative rent-or-buy resource. Renting costs one unit for each day it is used; buying costs ten units once and covers all later use. The number of days D is unknown, and each morning reveals only whether the resource is needed that day. There is no resale value or extra running cost.

Use this rule: rent for the first nine required days, then buy on the tenth if it occurs. If D=4, total cost is four, matching the offline optimum. If D=9, cost is nine, also optimal. If D=10, cost is 9+10=19, while an offline planner would buy immediately for ten.

For every D<10, the online cost and offline optimum both equal D. For every D≥10, the online cost is nineteen and the offline optimum is ten. The worst cost ratio is therefore 19/10=1.9 under these discrete-day assumptions.

Buying immediately would be excellent for a long sequence but cost ten when only one day is needed. Renting forever would cost one hundred over one hundred days, versus an offline cost of ten. The example shows why an online rule must balance possible futures rather than optimize only the future that eventually occurs.

Illustrative case study

Fictional case study: a customer-support platform assigns incoming tasks to available agents. An evaluation initially sorts the day's requests using information about final handling times before replaying them. This gives the scheduler knowledge that was unavailable when the original assignments had to be made.

The team rebuilds the replay around arrival times and information available at each decision. It records when outcomes become known and what reassignment is permitted. The revised evaluation can fairly test an online policy; it does not automatically prove that the policy is good or that every historical condition will recur.

Common misconceptions and mistakes

Do not interpret “online” as an internet requirement. An entirely disconnected device can run an online algorithm on a sequence of sensor readings.

Do not give an online policy future labels or later measurements during evaluation. That changes the information available and can make results misleading.

Do not assume competitive guarantees imply the lowest expected cost for a specific business distribution. Worst-case comparisons and distribution-based objectives answer different questions. Also distinguish updating an internal estimate from revising a past action whose consequences have already occurred.

Business use

Online algorithms are useful when operations cannot wait for a complete dataset: requests arrive continuously, resources must be assigned, or predictions must precede outcomes. Their design makes the timing of information central to the problem.

For business review, document response deadlines, available inputs, feedback delays, revision costs, and failure handling. Compare policies using chronological replay or another evaluation consistent with the actual decision process. A sophisticated policy evaluated with future information can be less useful than a simple policy evaluated honestly under deployment constraints.

Check your understanding

Why does the offline benchmark pay ten when the rent-or-buy sequence lasts ten days, while the illustrated online rule pays nineteen?

Answer: The benchmark knows the full duration and buys immediately. The online rule learns only whether each new day occurs, so it has already paid nine rental units before buying.

Related terms

Online learning
Competitive ratio
Regret
offline algorithm
streaming algorithm
sequential decision
feedback delay
chronological evaluation

Learn next

change the rent-or-buy purchase cost and derive the cost of buying on a chosen day. Then specify an online prediction timeline, marking exactly when features, predictions, outcomes, and model updates become available.

Sources

Sources: Aalto Dictionary of Machine Learning, online algorithm: https://aaltodictionaryofml.github.io/ADictML_Main.pdf ; Carnegie Mellon, Online Algorithms, rent-or-buy and competitive analysis: https://www.cs.cmu.edu/~15850/notes/lec26.pdf . Relevant primary definitions and analytical framework were read. The numerical rent-or-buy illustration uses stated discrete-day assumptions; revision restrictions are treated as problem-specific rather than universal.

Previous: One-way ANOVA Next: Online complex processing