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 2^m through 2^(m+1) - 1. Its size is 2^m. 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 2^(m+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 2^m through 2^(m+1) - 1, including both endpoints.
Locating Round 13
Which doubling period contains round 13?
Check period 0: Period 0 covers round 1, so round 13 is not in period 0.
Check period 1: Period 1 covers rounds 2 through 3, so round 13 is not in period 1.
Check period 2: Period 2 covers rounds 4 through 7, so round 13 is not in period 2.
Check 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
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. |
Common Misreadings
Treating the first period as rounds 0 through 1.
The source defines period m as covering rounds 2^m through 2^(m+1) - 1.
Fix:
Period 0 covers round 1 only.Using the period length as though it were the period's ending round.
The size 2^m tells how many rounds are in the period; the ending round is 2^(m+1) - 1.
Fix:
Track both facts: period 2 has size 4 and ends at round 7.Assuming the doubling trick requires the final value of T before the process begins.
Its purpose is to replace one horizon-dependent run with expanding periods.
Fix:
Run on the current period and advance to the next prescribed period when the current one ends.Reading α√T as if α were the horizon.
The two symbols have separate roles in the expression.
Fix:
Identify 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 2^m through 2^(m+1) - 1 for each period.
- Check the endpoints carefully: round 7 is the last round of period 2, while round 8 begins period 3.
- The doubling trick handles an unknown total horizon by dividing the process into expanding periods. Period m covers rounds 2^m through 2^(m+1) - 1 and has size 2^m. 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 2^m through 2^(m+1) - 1 and contains 2^m 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.