Time Horizons in Online Algorithms
The doubling trick replaces dependence on an unknown total horizon with a sequence of expanding periods.
The Unknown-Horizon Problem
An online algorithm makes decisions while a process is unfolding. Some algorithms choose their parameters using the total number of rounds T. That creates a practical difficulty: the algorithm may need to begin before anyone knows how long the process will continue. If the final horizon is unavailable at the start, a parameter that depends on T cannot be selected in the usual way.
The doubling trick addresses this difficulty by replacing one run that requires the complete horizon with a sequence of runs on periods whose lengths grow geometrically. Instead of committing to the unknown final value of T, the construction uses a current period, advances when that period ends, and continues on the next prescribed period.
Period Boundaries
Period m covers rounds 2m through 2m+1 - 1. Its size is 2m. When that period ends, the construction advances to period m + 1.
| Period | Rounds covered | Period size |
|---|---|---|
| 0 | 1 through 1 | 1 |
| 1 | 2 through 3 | 2 |
| 2 | 4 through 7 | 4 |
| 3 | 8 through 15 | 8 |
The first four periods generated by the rule for period m.
The periods are consecutive: period 0 ends just before period 1 begins, period 1 ends just before period 2 begins, and so on. Their lengths double from one period to the next: 1, 2, 4, and 8 in the first four periods. The important boundary rule is that period m ends at round 2m+1 - 1.
Tracing a Round
To locate a round t, compare it with the intervals for successive periods. A round belongs to period m when it lies from 2m through 2m+1 - 1, including both endpoints.
Locating Round 13
Which doubling period contains round 13?
- 1Check period 0
Period 0 covers round 1, so round 13 is not in period 0.
- 2Check period 1
Period 1 covers rounds 2 through 3, so round 13 is not in period 1.
- 3Check period 2
Period 2 covers rounds 4 through 7, so round 13 is not in period 2.
- 4Check period 3
Period 3 covers rounds 8 through 15. Since 13 lies in that interval, round 13 belongs to period 3.
Round 13 is in period 3.
What do you think happens?
Which period contains round 8?
Reveal answer
Period 3
Period 3 covers rounds 8 through 15, so round 8 is the first round of period 3.
Regret and Parameter Dependence
The regret expression discussed in the source has the form α√T. In this expression, T is the time horizon, while α is the factor multiplying √T. These symbols have different roles: T describes the total number of rounds, and α is the separate factor in the stated regret expression.
| Symbol or expression | Role |
|---|---|
| T | The time horizon, or total number of rounds. |
| α | The factor multiplying √T in the stated regret expression. |
| α√T | The original regret expression discussed in the source. |
| η | A parameter in the referenced theorem that the source notes depends on T. |
The horizon, regret expression, and parameters should not be conflated.
Common Misreadings
Common mistake Treating the first period as rounds 0 through 1.
What it looks likeThe schedule starts period 0 at round 2^0, which is round 1.
Why it failsThe source defines period m as covering rounds 2m through 2m+1 - 1.
Do this insteadPeriod 0 covers round 1 only.
Common mistake Using the period length as though it were the period's ending round.
What it looks likePeriod 2 has size 4, but it covers rounds 4 through 7.
Why it failsThe size 2m tells how many rounds are in the period; the ending round is 2m+1 - 1.
Do this insteadTrack both facts: period 2 has size 4 and ends at round 7.
Common mistake Assuming the doubling trick requires the final value of T before the process begins.
What it looks likeThe construction is designed for the case in which the total number of rounds is not known at the start.
Why it failsIts purpose is to replace one horizon-dependent run with expanding periods.
Do this insteadRun on the current period and advance to the next prescribed period when the current one ends.
Common mistake Reading α√T as if α were the horizon.
What it looks likeIn α√T, T is the time horizon and α is the factor multiplying √T.
Why it failsThe two symbols have separate roles in the expression.
Do this insteadIdentify T as the horizon and α as the separate factor.
Practice Check
For each round, identify its period: round 3, round 7, round 8, and round 15. Then state which symbol represents the time horizon in α√T and which symbol is the multiplying factor.
Hints
- Use the interval from 2m through 2m+1 - 1 for each period.
- Check the endpoints carefully: round 7 is the last round of period 2, while round 8 begins period 3.
- 1The doubling trick handles an unknown total horizon by dividing the process into expanding periods. Period m covers rounds 2m through 2m+1 - 1 and has size 2m. When a period ends, the construction advances to the next period. In the regret expression α√T, T is the time horizon and α is the separate factor multiplying √T.
Key Takeaways
- An algorithm may need a special technique when its parameter choices depend on a total horizon T that is unknown at the start.
- The doubling trick replaces one horizon-dependent run with a sequence of expanding periods.
- Period m covers rounds 2m through 2m+1 - 1 and contains 2m rounds.
- A new period begins after the current period ends, so the schedule can continue without knowing the final T.
- In α√T, T is the time horizon and α is the factor multiplying √T.