From Finite Plans to Long-Run Optimality Against Hedge

We study optimal play against full-history Hedge in infinitely repeated games with arbitrary finite payoff matrices and learning rate $t^{-\alpha }$, where $0<\alpha <1$. We construct a computable strategy that maximizes the lower limit of expected average payoff, using one strategy for all evaluation horizons while the learner keeps its actual history. The construction has three steps: finite planning with a payoff guarantee at every prefix, certified extension from short searches to long references, and sparse replacement of references during the continuing game. The finite planner returns global lower and upper bounds and has a complete count-state fallback. A uniform variation bound supports verification of repeated references with logarithmic dependence on the repetition count in a scalar-evaluation model. The execution rule controls the effect of earlier history and weights finite planning errors by the distribution of the latest reference. Experiments check the finite certificates against independent solvers, measure when compression saves verification work, and show how history-induced payoff differences decrease over time.