Does an online algorithm need future probabilities?

Not necessarily. Some frameworks analyze adversarial loss sequences without assuming a probability model, subject to their stated restrictions.

Is online optimization always machine learning?

It overlaps strongly with learning, but it also includes sequential decision and resource-allocation problems.

Can regret be negative on a realized sequence?

Yes. An adaptive decision sequence can outperform the best fixed comparator on a particular sequence; worst-case bounds concern a broader guarantee.

AI Glossary / Mathematics and optimization / Intermediate

Online optimization

Definition

Online optimization studies how to make a sequence of decisions when relevant information arrives over time and future costs are not yet known. After each decision, the algorithm receives feedback and adjusts later choices. It differs from solving one fully specified optimization problem: the central challenge is acting before all the information needed for a hindsight-best plan is available.

What it means

Online does not necessarily mean connected to the internet. It refers to the timing of decisions and information. Examples include allocating resources before demand is observed or predicting a value before its outcome arrives. A common framework, online convex optimization, uses a convex decision set and convex losses. Performance is often assessed by regret: the algorithm's cumulative loss minus the loss of the best fixed decision chosen afterward using the whole sequence. Other online problems use different benchmarks, including competitive ratios, so the chosen comparison must be stated.

How it works

At round t, select a feasible decision using information available so far. The round's loss or other feedback then becomes available. Update the internal state or model and repeat. An online gradient method takes a step opposite the newly observed loss gradient and projects back into the feasible set when needed. Full-information settings reveal more about the loss function than bandit settings, where only the chosen action's result may be observed. Delayed feedback, changing constraints and switching costs require additional treatment. The algorithm's guarantee must match the information it actually receives and the assumptions imposed on losses and decisions.

Three practical examples

A service adjusts a continuous resource allocation before each workload period, learning from the cost observed afterward.
A forecasting tool updates its parameters after actual demand is revealed, tracking cumulative prediction loss against a specified baseline.
A routing model selects a path before current travel costs are fully known. Whether it later observes all path costs or only the chosen route changes the online learning problem and the suitable algorithm.

Think of it this way

Think of choosing how much food to prepare each day before seeing that day's customers. Yesterday's experience can inform today's choice, but it cannot reveal today's demand. The analogy captures sequential uncertainty. Real inventory problems may include spoilage, carryover and asymmetric costs, so they do not automatically match a simple convex model with independent daily accounting.

Worked example

Let decisions x lie between 0 and 1, and let each round's loss be (x − y)² after outcome y is revealed. Start at x1 = 0.5 and use online gradient descent with step size 0.5. Outcomes are 0, 1 and 1. Round 1 loss is 0.25; gradient is 2(0.5 − 0) = 1, so x2 = 0. Round 2 loss is 1; gradient is −2, so x3 = 1. Round 3 loss is zero. Total loss is 1.25. The best single fixed decision in hindsight is the mean outcome, 2/3, with total loss 4/9 + 1/9 + 1/9 = 2/3. The realized regret is therefore 1.25 − 2/3 = 7/12, approximately 0.5833. A decision-maker who knew each outcome in advance could obtain zero loss, but that is a different, changing comparator. The example illustrates timing and regret, not a claim that this fixed step size is optimal.

Illustrative case study

In a fictional project, Willow Compute updates a workload predictor after each operating period. The team initially compares its decisions with a planner allowed to see every future workload and change actions without cost. It revises the analysis to state that this is an oracle benchmark, then also reports regret against a feasible fixed policy. It records delays in outcome reporting and checks whether those delays affect updates. The case shows how the benchmark and feedback model shape interpretation, without claiming a real performance gain.

Common misconceptions and mistakes

Low regret does not mean low absolute cost when every feasible policy performs poorly. Static regret compares with one fixed decision, not with the best changing action on every round. A sublinear regret bound implies diminishing average excess loss relative to its comparator, not that every future decision is correct. Online optimization is also different from repeatedly retraining on all historical data without considering decision timing. Avoid leaking the current outcome into a choice that is supposed to precede it. Convex guarantees do not automatically extend to an arbitrary nonconvex model.

Business use

Use the framework when decisions recur and feedback can improve later choices. Define the allowed actions, loss, timing and comparator before selecting an algorithm. Include operational costs of changing actions if they matter, rather than optimizing a simplified loss that rewards excessive switching. Evaluate a time-ordered replay with only information available at each decision. Track both cumulative performance and recent behavior, because a strong long-run average can conceal difficulty after a change in conditions. Establish how delayed, missing or revised outcomes will enter updates.

Check your understanding

An online method matches the best fixed decision's average loss. Has it matched a planner who changes decisions perfectly with every future outcome?

Answer: No. Those are different comparators. Static regret does not provide an unrestricted hindsight guarantee against a changing oracle.

Related terms

Online learning
regret minimization
online convex optimization
bandit feedback
dynamic regret
competitive analysis

Learn next

replay the worked sequence with a smaller learning rate and calculate both total loss and static regret. Then allow only the chosen action's loss to be observed and identify which gradient information is no longer available. Study how changing feedback alters the algorithmic problem.

Learning rate

Sources

Sources: Elad Hazan, Introduction to Online Convex Optimization, second edition, sections 1.1 and 3.1, https://arxiv.org/pdf/1909.05207 ; publisher's open-access edition record, https://mitpress.mit.edu/9780262046985/introduction-to-online-convex-optimization/ . The three-round calculation and operational scenarios are original examples of decision timing and comparator choice.

Previous: Online One-Class SVM Next: Online replanning