No Regret Learning

If you scroll to the bottom of the page, you’ll find this:

\lim_{T \to \infty} \frac{R_T}{T} = 0

This formula isn’t just something I think looks cool. It’s the idea behind a no-regret algorithm, and one of my favourite concepts in game theory.

In fact, the basic problem is something we see alot in air traffic management: decisions have to be made before you know exactly what is going to happen.

Demand evolves, weather moves, capacity changes, and decisions have to be made with the information available at the time. By the time you know what the best decision would have been, you’ve already made it.

Game theory gives us a useful way to think about what good decision-making can mean in a setting like that.

Suppose decisions are made over $T$ rounds. At round $t$ , an algorithm chooses an action $x_t$ . Afterwards, the consequences of that decision become known, represented by a loss function $\ell_t$ .

The important part is the order: you choose $x_t$ before you know $\ell_t$ .

In an air traffic setting, $x_t$ might represent a routing, allocation, or control decision. The loss could capture delay, congestion, cost, or some combination of objectives.

We can even allow the sequence of losses to be adversarial. We don’t need to assume that the environment behaves nicely or that future conditions follow a pattern we can predict perfectly.

So if optimal decisions require information we don’t yet have, what can we reasonably ask of an algorithm?

One answer is regret.

Rather than expecting every decision to be optimal, we compare the decisions we actually made with the best fixed decision we could have chosen in hindsight:

R_T = \sum_{t=1}^{T} \ell_t(x_t) - \min_{x \in \mathcal{X}} \sum_{t=1}^{T} \ell_t(x)

The first term is the total loss from the decisions we actually made.

The second asks what would have happened if, after seeing the entire sequence, we could go back and choose the single fixed action that would have performed best.

Regret is the difference between the two.

An algorithm is no-regret if

\frac{R_T}{T} \to 0.

You’ll also often see this written as

R_T = O(T).

In other words, regret grows more slowly than the number of decisions.

That doesn’t mean the algorithm eventually stops making mistakes. It doesn’t need to predict the sequence of losses correctly, and it doesn’t need to know in advance which action will turn out to be best.

What matters is what happens across the whole sequence. If regret grows more slowly than $T$ , then those errors do not accumulate at the same rate as the number of decisions. Their average cost goes to zero.

There are stronger results that tell us how quickly regret can grow under different assumptions. But the part I care about here is simpler: learning is possible even when some of the information needed to evaluate a decision only becomes available after that decision has been made.

That is what makes the result interesting to me. And I think it is very relevant in the context of air traffic management.

Demand changes. Weather forecasts change. Capacity constraints appear and disappear. A routing or flow-management decision has to be made using what is known now, not what will be known an hour from now.

You can’t optimise against a future you haven’t seen.

But you can ask whether a decision-making method learns from what happens. You can ask whether, over time, its decisions perform well relative to a meaningful benchmark, despite having to operate under uncertainty.

It doesn’t say that every decision will be right. It doesn’t say uncertainty can be eliminated. It says that uncertainty doesn’t make learning hopeless.

That’s the idea behind No Regret Learning:

\lim_{T \to \infty} \frac{R_T}{T} = 0.

The future can remain uncertain, and we can still get better at making decisions