acceptodds
Under review as a conference paper at ICLR 2027

From Finite Plans to Long-Run Optimality Against Hedge

Abstract

We study optimal play against full-history Hedge in infinitely repeated games with arbitrary finite payoff matrices and learning rate , where . 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.

Primary area:
optimization
Keywords:
Repeated games, Learning in games, Hedge algorithm, Optimal strategizing, Prefix-safe planning, Infinite-horizon planning.

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_kmG2OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper asks how to play against an opponent whose learning rule is Hedge, an exponential-weights learning algorithm. This algorithm favors actions that would have earned higher rewards in previous rounds. Your choices therefore affect both your immediate reward and the opponent’s future behavior: accepting a loss now may encourage responses that benefit you later.

The authors construct a strategy that achieves the best possible long-run average reward, measured in expectation. They first build and check plans for a finite number of rounds they then combine these plans, carefully timing replacements so that the opponent’s memory of earlier rounds does not undermine the result.

The optimality guarantee concerns the limit of indefinitely repeated rounds. Experiments test the finite plans, the verification shortcut, and the effect of the opponent’s memory.

Critical strengths

The results claimed in this paper, if corrects and introduced clearly might be interesting.

Critical weaknesses

The paper is extremely difficult to follow, to the point that its central contribution is obscured by the presentation. Dense terminology and explanations scattered across sections make it hard to understand what is being constructed, why each component is needed, and how the guarantees fit together.

Abstract

The abstract is unclear, even to a reader familiar with Hedge in infinitely repeated games. Expressions such as “certified extension” and “distribution of the latest reference” appear without making clear what the objects are or how they relate. The reader must already understand the method to understand the abstract meant to introduce it.

Main text

The main text has a pervasive clarity problem. Dense terminology, compressed descriptions, and deferred definitions repeatedly force the reader to reconstruct what individual statements mean before following the argument. The three-step organization does not resolve this difficulty: the relationships between planning, reference histories, verification, and long-run guarantees remain difficult to track. Essential information is scattered across sections and the appendix, which becomes necessary to understand the construction itself.

The following sentences illustrate this broader problem:

Line 056 “A repetition-independent variation bound for the actual softmax rewards supports compressed long-reference verification.” Line 329 “After merging their change times, the reward enclosures are periodic on each resulting interval, so the lower prefix margin is affine across repetitions with the same remainder; its first and last values suffice.”

Both sentences compress several technical objects and implications into assertions whose meaning the reader must reconstruct. The authors should unpack these statements, identify the relevant objects explicitly, and explain the connections between them.

Proofs

The proofs are insufficiently explicit to verify with confidence. Several passages describe a proof strategy without developing the chain of equalities, inequalities, or logical implications needed to establish the conclusion. The reader must reconstruct intermediate steps rather than check a fully developed argument. These passages therefore read more like proof sketches. For the central theorems, the nontrivial steps and the justification for each transition should be explicit.

Questions for authors

I have no questions for the authors, and I encourage them to revise their paper and submit it to an upcoming conference.

Reviewer_TtjXOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how a strategist should play against a learner in an infinitely repeated game with known finite payoff matrices.

The learner uses the full-history Hedge algorithm with a learning rate ηt=t−α\eta_t = t^{-\alpha}, for some 0<α<10 < \alpha < 1.

The objective is the lower limit of expected average payoff.

The paper constructs a single computable strategy that attains the optimal value, without resetting the learner's history.

It proposes Certified Continuation Planning (CCP).

CCP searches a short horizon hh to get an upper bound, extends the short plan into a long reference built from repeated action words, and verifies a lower bound. This gives a global ε\varepsilon-certificate, with the complete LP as a fallback.

It also proposes Sparse-Refresh Prefix Planning (SRPP).

SRPP replaces references at geometrically spaced times, with decreasing probability. With high probability the latest reference is recent enough to cover the current round and old enough for the earlier history's effect.

The paper reports certified finite plans for 28 small targets, a 24.6× median speedup (line 424) from compressed verification, and history decay within the derived bounds.

Critical strengths

The main result, a computable strategy attaining the exact optimal long-run value against decaying-rate full-history Hedge in general finite games, seems to be new.

The paper gives a long-run optimality result for a general class of games. It constructs a computable strategy that attains the optimal lower limit of expected average payoff against full-history Hedge with a decaying learning rate. It does this in arbitrary finite games without resetting the learner.

This answers a basic question in strategizing against no-regret learners.

The finite planner also returns verified two-sided certificates, which were cross-checked independently in the experiments.

Critical weaknesses

The practical significance of the result is unclear. The long-run theorem gives asymptotic optimality, without a convergence rate. The history experiment suggests that convergence can be slow for small α\alpha.

Refresh planning is superpolynomial: at round tj=2jt_j = 2^j, CCP must certify a plan over horizon Hj=2j2H_j = 2^{j^2}, and when the short search doesn't close the gap, the complete fallback has about Hm−1H^{m-1} states per layer.

The paper is sometimes hard to follow because terms are used long before they are defined. Examples include "score discrepancy", "count-state", "reference", "word", TT, and ℓ\ell.

Several sentences stack terms that haven't been introduced and defined before, such as "repetition-independent variation bound for the actual softmax rewards", "exact repeated-word dynamics", "turning point", "reward enclosures", and "lower prefix margin".

The main text doesn't give the logit form behind compressed verification (equation 35), why rounding to dyadic probabilities is needed, or why the enclosures are periodic. References to the relevant appendix sections would be helpful here.

Some terminology is used inconsistently. An example is "score discrepancy", "score difference" and "relative score".

Page-by-page comments and feedback:

Page 1:

With rate t^−α, [...]

State the range of α here.

a fixed historical score discrepancy has diminishing influence

Both "score" and "score discrepancy" are undefined at this point.

The paper uses the terms "score discrepancy", "score difference", "earlier discrepancy", and "relative score" in different places. I recommend choosing one and using it consistently.

its expected cumulative payoff is at least ℓT − C at every prefix of a prescribed horizon

T and ℓ are undefined here. They are not defined until section 3.1 (line 157).

Consider rewording this to "for a horizon H, its expected cumulative payoff over the first T rounds is at least ℓT − C for every T ≤ H, where ℓ is a per-round payoff rate and C is a budget."

direct count-state representation

This is undefined until section 3.1 (line 183).

Consider saying up front that the learner's state is determined by the strategist's action counts.

extends a short policy into a finitely represented reference of length H ≥ h

"Reference" is used here and in the abstract before it is defined (in section 3.1, line 161).

At first use, state that it is evaluated from the initial state (prior q, zero counts) rather than the actual history.

Also, it's unclear what "finitely represented" means here, since every length-H sequence is finite.

A repetition-independent variation bound for the actual softmax rewards supports compressed long-reference verification.

This sentence is difficult to parse. Also, several terms are undefined at this point.

Consider rewording this to something like the following:

Verifying a reference of length HH round by round takes HH reward evaluations. When the reference repeats a short action word, however, the strategist's expected reward at each position of the word changes over the whole game by a total amount bounded by a constant that depends only on the learner's number of actions, regardless of how many times the word repeats. This lets us verify the entire prefix-reward curve with a number of reward evaluations logarithmic in the repetition count.

Page 2:

exact repeated-word dynamics

"Word" is undefined here.

Define it earlier, e.g., "a word is a finite strategist action sequence; long references repeat a short word".

Also, clarify what "dynamics" means here. Whose dynamics? Does it refer to the learner's response?

Also, clarify why "exact" is used here. "Exact" as opposed to what?

Equation 1 (Hedge update) could be stated more concisely as p_t = softmax(log q + η_t Σ_{s<t} B_{a_s,·}).

This matches the form used in equation 3, , with Σ_{s<t} B_{a_s,·} = BᵀN(t−1).

Moving the softmax definition (line 163) up to section 2.1 would unify the two and avoid presenting the same update twice in different notation.

Page 4:

e_a is the ath coordinate vector

"the aath standard basis vector" is more clear.

After rounding its sampling probabilities to dyadic rationals,

The motivation for this isn't stated here.

From the appendix (A.2.5, l. 806), it seems the reasons are (i) the certificate should cover the exact law that is executed, and (ii) dyadic probabilities can be sampled exactly with finitely many fair coin flips, which the computability claim needs.

Consider a clause such as "so that the plan can be sampled exactly with finitely many random bits and the certificate applies to the executed law; the rounding error is absorbed into the gap (Lemma 8)."

Page 5:

global error certificates; the main step

The semicolon is unnecessary here. Change it to a period.

Page 7:

At each word position, the logits contain both t^{1−α} and t^{−α} terms, and the reward need not be monotone.

It's unclear where these terms come from or why they cause non-monotonicity.

Consider adding a reference to Appendix A.3.

Consider stating the logit form z_b(t) = log q_b + β_b t^{1−α} + γ_{r,b} t^{−α} (equation 35) in the main text, explaining it as a growing word term plus a decaying offset term.

each pairwise logit difference has at most one turning point

It's unclear what "turning point" means here (a stationary point or a local extremum?).

"pairwise logit difference" and "logistic transform" seem to be undefined in the main text.

the reward enclosures

"Enclosures" is undefined. Consider adding a reference to Appendix A.2.3.

Also, the main text doesn't explain why the enclosures are periodic. A reference to the relevant appendix should be added.

so the lower prefix margin is affine across repetitions with the same remainder

"Lower prefix margin" and "remainder" aren't defined here.

Equation 14

The limit variable isn't stated. Presumably k → ∞.

Also, say what the probability is over. Presumably the refresh randomness.

Page 9:

We use finite prefix guarantees to connect a computable planning problem to optimal long-run play against a learner that keeps its history.

Consider rewording this to something like:

We show that finite plans with payoff guarantees at every prefix yield a computable strategy that attains the optimal lower limit of expected average payoff against full-history Hedge, without resetting the learner's history.

Questions for authors
  1. Computation cost:

At refresh jj, CCP must certify a plan over horizon Hj=2j2H_j = 2^{j^2}. Can you bound the computation per round of CCP–SRPP, even in the worst case? Is a horizon of 2j22^{j^2} necessary, or would a smaller schedule (such as polynomial in tjt_j) work with a different refresh law?

  1. When does short search succeed?

In your experiments, 24 of 28 targets at H≈32H \approx 32 needed the complete fallback. Is there any class of games, or any condition, under which you can guarantee that CCP stops at some h≪Hh \ll H?

  1. The value VV:

How does VV relate to standard benchmarks, such as the Stackelberg value, or the value achievable against mean-based learners (Deng et al., 2019)? Is VV strictly larger than the Stackelberg value for some games? Does your characterization via ΛH(C)\Lambda_H(C) say anything qualitative about optimal play?

  1. The full strategy:

Have you run the complete CCP–SRPP strategy to see how FTF_T compares with VV at practical horizons?

My suggestions for future work:

  1. Convergence rates for FT→VF_T \to V, even under extra assumptions.

  2. Extensions to unknown learner parameters (e.g., α\alpha or BB) or to other learning rules.

Reviewer_PevpOpenReview ↗
Rating
3
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the problem of computing an optimal strategy against a full-history Hedge learner in infinitely repeated games. The main contribution is a constructive optimality result. The authors establish a connection between finite-horizon planning problems and the optimal long-run average payoff. They use this connection to construct a computable strategy achieving the optimal asymptotic value.

Critical strengths

The main contribution of the paper is an algorithm that computes a strategy achieving the best possible long-run average payoff against an opponent using Hedge.

The authors first show how the optimal long-run payoff can be characterised using finite planning problems. They then explain how to combine the resulting plans into a single strategy without resetting the opponent’s learning history. The paper also proposes a method to evaluate the quality of finite plans and a faster procedure for checking long sequences of repeated actions.

The theoretical results are interesting, although the experiments mainly assess the finite planning procedure rather than the performance of the complete algorithm.

Critical weaknesses

The ideas in the paper are non trivial and interesting. However, it is not clear to me if the complexity is required in the first place. The Hedge strategy is known in advance, so the first player face a fully observable MDP with known transitions and expected rewards. Since the problem reduces to an MDP, finite-horizon optimal strategies follow directly from Bellman recursion. Could the authors clarify what prevents a direct infinite-horizon dynamic programming approach from establishing the desired optimality result, and which additional guarantees require the proposed CCP–SRPP construction?

Questions for authors

Could the authors clarify what prevents a direct infinite-horizon dynamic programming approach from establishing the desired optimality result, and which additional guarantees require the proposed CCP–SRPP construction?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.