A parameter-free hedging algorithm

• When the action count is very large, choosing Hedge’s learning rate is not understood, while running multiple Hedge copies is described as impractical.The introduction motivates this challenge with applications such as tracking, where actions can represent paths through a continuous state space.Source: §1 · pp. 1–2
• Top-ε-quantile regret compares the learner’s cumulative loss with the ⌊εN⌋-th lowest cumulative action loss, rather than only the single best action.The paper presents this as a more natural comparator for practical applications with many actions.Source: §1 · p. 2, Figure 1 · p. 2
• At ε = 1/N, NormalHedge’s best-action bound is only slightly worse than Hedge’s optimally tuned bound, while the quantile bound’s T-term does not depend on N.The quantile guarantee holds simultaneously for all T and ε.Source: §1 · p. 2
• NormalHedge uses an adaptive potential based on each action’s regret and a scale parameter adjusted across rounds, with weights proportional to the potential’s derivative.The potential differs from Hedge’s exp(ηR_i,t) potential.Source: §1 · p. 2
• NormalHedge assigns zero weight to actions whose cumulative loss exceeds the algorithm’s, so only actions performing better than the learner receive nonzero weight.The paper connects this property to settings where a small set of actions performs significantly better than most.Source: §1 · p. 3
• The paper leaves open an adaptive DTOL algorithm with regret bounds depending on the best action’s loss, noting its potential-based analysis does not directly yield such bounds.The cited alternative bounds may depend on best-action loss or loss variations.Source: §1 · p. 3

2.1 Setting

• In each round, the learner chooses a distribution over N actions, incurs its expected loss, and accumulates regret relative to each action; losses lie in an interval of length 1.The objective is to minimize cumulative regret to any action for any round t.Source: §2.1 · p. 3

2.2 Normal-Hedge

• Normal-Hedge uses a potential based on positive regret and maintains scale c_t so the average potential across actions remains e; convexity in c permits a line search.The potential is separately convex in x and c and twice differentiable except at x = 0.Source: §2.2 · p. 4
• Each action’s weight is proportional to the potential’s first derivative at its previous regret and scale, giving zero weight to actions with nonpositive regret.Source: §2.2 · p. 4

• The example models settings such as tracking, where similar paths can have nearly identical loss sequences and performance may depend on state-space discretization.The authors note that NormalHedge is comparatively unaffected by such discretization.Source: §3 · p. 4
• The example distinguishes N total actions from n distinct actions, k good actions, and ε, their advantage over the others.T is the number of rounds.Source: §3 · p. 4
• The construction begins with an n × T loss matrix based on a Hadamard matrix, then modifies the first k rows by subtracting ε.The resulting losses are represented in an N × T matrix; each action row is replicated N/n times.Source: §3 · pp. 4–5
• When the n distinct actions have equal average performance, a typical algorithm eventually assigns them equal weights; the first k are then made better by ε.Replicating each row creates N total actions from the n-action construction.Source: §3 · p. 5
• The example compares NormalHedge with Exp, a time/variation-adaptive Hedge variant, and Poly, polynomial weights with p = 2 ln N.The comparison uses parameters for Exp and Poly that depend on total action count N.Source: §3 · pp. 4–5
• NormalHedge’s performance is unchanged by replication, while Exp and Poly are affected when multiple good actions must share weight.For k = 1, Exp and Poly instead perform better with inflated N; setting their parameters by n removes the replication effect.Source: §3 · p. 5, Figure 3 · p. 6

• Time-varying Hedge learning rates yield a best-action regret bound of √(2T ln N) + O(ln N), but the method remains susceptible to poor performance and does not address the paper’s regret notion.Source: §4 · p. 6
• Hedge can bound regret to a fixed top ε-quantile by O(√(T log(1/ε))), but its learning rate must be set for that ε.The bound therefore does not hold uniformly for all ε.Source: §4 · p. 6
• NormalHedge guarantees regret bounds uniformly for all ε-quantiles without the extra overhead of running multiple Hedge copies.The multi-copy alternative incurs an additive O(√(T log log N)) factor.Source: §4 · p. 6
• Other adaptive methods can give sharper bounds when the best action’s total loss or loss variation is small, but their learning rates depend explicitly on N.These methods use a different notion of regret.Source: §4 · p. 7
• Polynomial weights require a parameter tied to N, and with p = 2 ln N achieve a regret bound of 2√(eT(ln N − 0.5)).The passage also notes that polynomial weights give zero weight to actions performing worse than the algorithm.Source: §4 · p. 7

5.1 Main results

• As t→∞, NormalHedge’s top-ε-quantile regret is bounded by 3t(1+ln(1/ε))+o(t), and its best-action regret by 3t(1+ln N)+o(t).The authors say δ appears to be an artifact of the analysis and its effect essentially disappears for large t.Source: §5.1 · p. 7

5.2 Regret bounds from the potential equation

• Lemma 3 connects the scale c_t to best-action and top-ε-quantile regret bounds using the potential of active actions and actions at the quantile cutoff.Source: §5.2 · pp. 7–8

5.3 Bounds on the scale ct and proof of Theorem 1

• The proof splits rounds before and after t0, bounding early scale and later per-round growth; Lemma 4 gives c_{t+1} ≤ 2c_t(1+ln N)+3.Source: §5.3 · p. 8

6.1 Proof of Lemma 4

• Lemma 4 bounds scale growth at each round by c_{t+1}≤2c_t(1+ln N)+3.Source: §6.1 · p. 9

6.2 A bootstrap for Lemma 5

• The bootstrap establishes that c_t is nondecreasing and derives a preliminary growth bound used to obtain a tighter bound on c_{t+1}−c_t.Source: §6.2 · pp. 9, 11
• Lemma 7 separates potential change from regret updates at fixed c_t and from the scale update, yielding a bound on the scale increment.Source: §6.2 · p. 10

6.3 Proof of Lemma 5

• The proof of Lemma 5 sharpens the bound on c_{t+1}−c_t using Lemmas 6 and 7, ending with a closing estimate at most 1+45.7δ.Source: §6.3 · pp. 12, 14
• Lemma 11 uses convexity and Taylor bounds to control changes in f across cases split at a.Source: §6.3 · p. 14