{"id":"80fa081e-c694-4595-b220-28a7993f3793","arxiv_id":"2501.19144","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A contextual optimistic multiplicative weights algorithm (POMWU) achieves static-game regret, equilibrium convergence, and social welfare guarantees in time-varying games when players can predict the changing state of nature with bounded error.","lead":"This paper proposes POMWU, an algorithm that lets players in an online game use forecasts of future game states to keep regret low. If the forecasts are mostly correct, it recovers the same performance guarantees as static games, a step toward making learning dynamics useful in predictable but non-stationary environments.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1/2 equilibrium claims rely on Proposition 2, whose proof assumes deviations are context-only while Definition 1 quantifies over history-dependent policies; the key inequality fails for history-dependent π^j.","rationale":"The reader's weakest assumption (H2) is acknowledged and does not threaten the finite-context theorem. The load-bearing gap is that the equilibrium-convergence half of the central claim conflates the deviation class: regret is measured against context-only comparators, while the CCE/CE definitions allow history-dependent deviations. Since the proof of Prop 2 explicitly uses the context-only comparator as a lower bound on arbitrary history-dependent policies, the implication is invalid in general; a concrete counterexample exists. This does not impeach the regret and welfare bounds, so the appropriate action is to require revision (restrict the equilibrium definition or fix the proof), not rejection.","tokens_in":32806,"tokens_out":19629,"duration_ms":183016,"concrete_test":"Verify Proposition 2 with a two-player, m=1 matching-pennies game: player 2 plays 0 on even rounds and 1 on odd rounds; player 1 uses any no-regret algorithm (or POMWU). Compute player 1's contextual regret vs. the best fixed action (should be ≤ 0 if player 1 tracks the pattern) and evaluate Definition 1 against the history-dependent policy that plays the exact best response each round. If the CCE violation is Ω(1) while regret is non-positive, Prop 2 fails. Also re-derive Prop 2 with Π^j restricted to context-only policies to confirm the fix.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 2 defines Π^j as policies from (histories) × Z to ΔK, so Definition 1's ε-contextual CCE and Definition 2's ε-contextual CE allow deviations that depend on all past feedback. But the regret R^j_T in (4) is benchmarked against π*_⋆ : Z → ΔK, the best fixed action per context (context-only). Proposition 2's proof (Appendix G) replaces the deviation π^j(Z_t) by π*_⋆(Z_t) and uses the inequality E_{π^j(Z_t)⊗w^{-j}_t}[φ] ≥ E_{π*_⋆(Z_t)⊗w^{-j}_t}[φ]. This holds only if π^j is a context-only policy; a history-dependent policy can track temporal patterns in the opponent's play and beat every fixed action. For example, with a single context (m=1), let opponent alternate actions deterministically; a history-dependent policy observing the parity can play the exact best response each round (average cost 0) while the best fixed action incurs average cost 1/2. Such a player has negative contextual regret, yet the empirical distribution violates Definition 1 for ε < 1/2. Hence Proposition 2 and Corollaries 1–2 are not established for the stated equilibrium concepts. The individual-regret and social-welfare results (Prop 6, Prop 7, Cor 3) are unaffected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a prediction-aware framework for repeated general-sum games with an unobserved state of nature. Each agent receives a prediction of the current state, and payoffs are linear in the state. The proposed algorithm, POMWU, maintains one optimistic multiplicative-weights update per context and uses the predicted context in the optimistic step. The main theoretical results are a contextual RVU bound (Proposition 5); an individual contextual-regret bound of order O([ln K (L_T + m)]^{3/4} T^{1/4} J^{1/2}) under a condition T = Omega(J^2 L_T) (Proposition 6); convergence of the empirical policy to epsilon-contextual coarse correlated and correlated equilibria (Corollaries 1--2); a social-welfare bound under the contextual smoothness condition (Proposition 7 and Corollary 3); and robustness against arbitrary opponent sequences (Proposition 8). The paper also reports a traffic-routing experiment on the Sioux Falls network.","tokens_in":33029,"tokens_out":21185,"duration_ms":216382,"significance":"If the issues below are repaired, this is a useful contribution: it extends the static-game guarantees of Syrgkanis et al. (2015) to games whose payoffs vary in a predictable way, and the per-context RVU decomposition is nontrivial. The paper is honest about the finite-context assumption H2 and about the fact that infinite contexts require different techniques. The individual-regret and social-welfare parts appear sound, and the realizable-case reduction to known multiclass mistake bounds is a nice touch. However, the equilibrium part currently contains a proof step that is invalid for the stated equilibrium definition, and Corollary 2 states a rate with the wrong dependence on K. Both problems are local and fixable.","major_comments":[{"comment":"The proof of Proposition 2 replaces the deviation term E_{pi^j(Z_t) \\otimes \\nu^{-j}(Z_t)}[\\phi] by E_{pi^j(Z_t) \\otimes w^{-j}_t}[\\phi]. This equality is valid when pi^j is a context-only policy, but Definition 1 quantifies over the set Pi^j of history-dependent policies introduced in Section 2, where pi^j takes the history h_{t-1} as an argument. For history-dependent policies the two expressions differ, so the displayed chain of equalities in the proof is not justified. The proposition can be repaired: after the context-conditional decomposition, one should apply, for each s, the per-round inequality \\langle Z, \\Phi^j(w^{-j}_s)\\pi^j_t(z)\\rangle \\ge \\langle Z, \\Phi^j(w^{-j}_s)\\pi^j_\\star(z)\\rangle before averaging over s; this gives the same final bound. However, as written, the proof is invalid for the stated definition, and the notation pi^j(Z_t) for a history-dependent policy is ambiguous. Please rewrite the proof and, if the intended equilibrium concept is the context-only one, say so explicitly in Definition 1.","section":"Section 2, Definition 1, and Proposition 2 (Appendix G)"},{"comment":"The stated rate for the contextual correlated equilibrium does not follow from the preceding results. Proposition 1 gives \\bar{R}^j_T \\le K R^j_T, and Proposition 6 gives R^j_T = O([\\ln K (L_T + m)]^{3/4} T^{1/4} J^{1/2}). Combining these with Proposition 3 yields \\bar{\\varepsilon} = O(K [\\ln K (L_T + m)]^{3/4} T^{-3/4} J^{1/2}), not O([K \\ln K (L_T + m)]^{3/4} T^{-3/4} J^{1/2}). The displayed bound is smaller by a factor K^{1/4}, and I see no argument in the paper that removes this factor. Please correct the statement and any downstream discussion of the correlated-equilibrium rate.","section":"Corollary 2"}],"minor_comments":[{"comment":"The displayed equality in the bound of term (ii) has an index error. Writing a_i = \\|w_{z,i}-\\tilde{\\rho}_{z,i}\\|_1^2 and b_i = \\|w_{z,i}-g_{z,i}\\|_1^2, the correct identity is \\sum_{i=1}^{n_z}(a_i+b_i) = \\sum_{i=1}^{n_z}(a_{i-1}+b_i) + (a_{n_z}-a_0). With w_{z,0}=\\tilde{\\rho}_{z,0}, the subsequent lower bound follows; the version printed in the paper is not correct as written.","section":"Appendix G, proof of Proposition 5, term (ii)"},{"comment":"The choice \\eta = (4(J-1))^{-1} is undefined for J=1. The paper should either state an assumption J \\ge 2 or give a separate argument for the single-player case.","section":"Proposition 7 and Corollary 3"},{"comment":"The symbol L_T is used with two different meanings: in Proposition 6 and Corollaries 1--2 it is the per-player maximum, while in Proposition 7 it is the sum over players. Please rename one of them (for example L_T^{\\max} and L_T^{\\rm sum}) to avoid confusion when the results are compared.","section":"Notation for L_T"},{"comment":"The abstract writes 'POWMU' instead of 'POMWU'; Corollary 2 writes 'conjonction' for 'conjunction'; Corollary 3 contains 'If Assume all agents'; and the reference to Foster and Vohra contains an extraneous space. These should be corrected.","section":"Typos and wording"}],"recommendation":"major_revision","confidential_remarks":"The paper's equilibrium claims are likely correct after a short repair of the proof of Proposition 2 and after correcting the K dependence in Corollary 2. The individual-regret and social-welfare arguments appear sound, and the proposed framework is a reasonable contribution to learning in time-varying games. I recommend major revision rather than rejection because the issues are local and fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the prediction-aware framework is a real and useful extension of contextual learning in games, and the contextual RVU bound (Prop 5) is the genuine technical contribution. The individual regret and social welfare results (Props 6–7, Cor 3) check out as far as I can tell. But the equilibrium convergence claims (Cor 1 and 2) are not established for the equilibrium concepts as defined. The stress-test note is right: Definition 1 quantifies over history-dependent policies, while Proposition 2's proof only controls deviations to the best fixed action per context. A history-dependent deviator can beat every fixed action by tracking patterns in opponents' play (e.g., a single context with alternating opponents), so the inequality in the proof doesn't go through for the stated Π^j. This means the paper overclaims convergence to contextual CCE/CE as defined. Fixing this would require either restricting the deviation class to context-only policies (which weakens the equilibrium concept) or comparing against history-dependent comparators (which would reintroduce path-length terms and undermine the 'prediction-aware rates' story). This is a load-bearing issue for those corollaries, not a minor typo.\n\nEverything else is in decent shape. The finite-context assumption H2 is explicitly acknowledged and the appendix sketches extensions. The experiments are illustrative only: no code, no hyperparameters, no non-trivial baselines. That's fine for a theory paper but shouldn't be oversold.\n\nWho should read this: anyone working on time-varying or contextual games, especially people interested in optimistic MWU and RVU-style analyses. The regret and welfare bounds are worth having even if the equilibrium results need repair.\n\nRecommendation: send to peer review. It's a serious paper with a real technical core, but the authors need a major revision to fix the equilibrium definitions or proofs before it's publishable as is.","headline":"Solid RVU analysis and a genuinely new prediction-aware framework, but the equilibrium convergence claims don't survive contact with history-dependent deviations.","tokens_in":33664,"tokens_out":6160,"would_cite":true,"duration_ms":58643,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A26","91A20","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that in time-varying multiplayer games, learning rates can be governed by forecasting accuracy instead of by how fast the game changes: with the POMWU algorithm, bounded prediction errors yield the same regret…","keywords":["prediction-aware learning","time-varying games","optimistic multiplicative weights","contextual regret","coarse correlated equilibrium","correlated equilibrium","social welfare","online learning in games"],"falsifier":"Run POMWU with a perfect oracle predictor ($L_T = 0$) on a finite-context game for $T = 10^6$ with $\\eta$ tuned as in Proposition 6; the theorem predicts per-agent contextual regret growing like $T^{1/4}$. If the empirical regret grows linearly, or if the $m=1$ static case fails to reproduce the known optimistic-MWU behavior, the contextual RVU bound is falsified.","tokens_in":32522,"feed_emoji":"🚦","tokens_out":7906,"duration_ms":74616,"temperature":0.7,"pith_summary":"The paper proposes a prediction-aware model of time-varying multiplayer games: at each round every player receives a private forecast of an unobserved state of nature, chooses a mixed action, then observes the true state and the full-information payoff. Against this backdrop, it introduces POMWU, a contextual extension of optimistic multiplicative weights, and proves that the quality of the players' forecasts, measured by the number of mispredictions, controls how far individual regret, equilibrium approximation, and social welfare are from the static-game benchmarks. Under bounded prediction errors the rates match the guarantees known for constant games. The point of the exercise is that predictable variation in a game does not have to be paid for in regret; only the residual forecasting error matters.","feed_headline":"Prediction errors, not game drift, set regret in changing games","feed_subtitle":"POMWU learns one optimistic update per context, and its guarantees degrade only with misprediction counts.","key_machinery":"The central object is POMWU, which keeps one optimistic multiplicative weights instance per context $z \\in \\mathcal{Z}$; when a player predicts $\\hat{Z}_t^j$, it plays from that instance's distribution and receives an optimistic hint from the stored matrix $\\Psi_z$. The load-bearing proof device is a new contextual RVU (regret bounded by variation in utility) bound: instead of the classic global path-length term, the regret of each player is bounded by the sum of per-context path lengths of feedback and strategies plus the number $L_T^j$ of mispredictions. The argument also uses a contextual version of the Blum-Mansour reduction to convert external-regret guarantees into swap-regret guarantees, and the smoothness condition to turn sums of regrets into social-cost bounds.","core_discovery":"The paper's central claim is that in a time-varying game, the quantity that should appear in regret bounds is not a measure of how much the game moved but a measure of how often players failed to predict the state of nature. Formally, if every agent uses POMWU with learning rate $\\eta^\\star$ and $L_T = \\max_j L_T^j$ is the largest number of context mispredictions, the contextual external regret of every agent is $O([\\ln(K)(L_T + m)]^{3/4} T^{1/4} J^{1/2})$ (Proposition 6). The empirical joint policy is then an $\\epsilon$-approximate coarse correlated equilibrium with $\\epsilon = O([\\ln(K)(L_T + m)]^{3/4} J^{1/2} T^{-3/4})$ (Corollary 1), and under the smoothness condition the average social cost satisfies $\\frac{1}{T}\\sum_t C_t(w_t) \\leq \\gamma C^\\star + O(J \\ln(K) T^{-1}(L_T + mJ))$ (Corollary 3). When $L_T$ is constant, these recover the static-game rates of Syrgkanis et al. (2015). The same story holds for swap regret and correlated equilibrium, with an extra factor of $K$ from a contextual Blum-Mansour reduction.","pith_inferences":["A consequence left implicit in the paper is that forecast quality is fungible: any online multiclass predictor with a mistake bound can be plugged into POMWU, so better forecasting algorithms directly improve equilibrium and welfare guarantees without changing the game-theoretic analysis.","The per-context tabular structure suggests the finite-context assumption is the real bottleneck; an infinite-context version would need function approximation or discretization, and the paper explicitly defers this, so testing on large or continuous context sets is a natural next step.","The paper states that extending to bandit feedback should be feasible but does not carry it out; if that extension holds, POMWU would apply to settings where players observe only realized costs rather than full payoff matrices.","Proposition 9 shows that shared predictions remove the condition $T = \\Omega(J^2 L_T)$, hinting that collaborative forecasting is not only a practical convenience but can strengthen the theoretical guarantee; quantifying this trade-off is an open direction."],"forward_implications":["When all players use POMWU with bounded mispredictions, their empirical joint policy converges to a coarse correlated equilibrium at rate $T^{-3/4}$ up to logarithmic factors.","With the swap-regret variant, the same guarantees apply to the tighter correlated equilibrium concept, at the cost of an extra factor $K$.","Under the smoothness condition, average social cost approaches $\\gamma$ times the optimal cost, with an error that shrinks like $T^{-1}$ when mispredictions are bounded.","Predictions from any multiclass learner with a finite Littlestone dimension give $L_T = O(1)$ in the realizable case, so the static-game guarantees transfer essentially unchanged.","POMWU remains a no-regret algorithm against arbitrary opponent sequences, with regret $O(\\sqrt{\\ln(K)(L_T^j + m)(L_T^j + T)})$, so robustness to adversarial play is preserved."],"supporting_citations":[{"why":"Supplies the static-game RVU regret, equilibrium, and social-welfare rates that POMWU recovers when prediction errors are bounded.","marker":"(Syrgkanis et al., 2015)"},{"why":"Provides the contextual game setting, the definition of contextual coarse correlated equilibrium, and the contextual regret comparator used in the model.","marker":"(Sessa et al., 2021)"},{"why":"Introduces the optimistic multiplicative weights update that POMWU extends to predicted contexts.","marker":"(Daskalakis et al., 2021)"},{"why":"Supplies the predictable-sequence analysis and the Bregman-divergence lemma underlying the new contextual RVU bound.","marker":"(Rakhlin and Sridharan, 2013)"},{"why":"Gives multiclass online learning mistake bounds that control $L_T$ in the realizable and agnostic cases.","marker":"(Daniely et al., 2014)"},{"why":"Provides the time-varying zero-sum game dynamic regret bounds with path-length terms that the paper shows become vacuous for easy-to-predict variations.","marker":"(Zhang et al., 2022)"},{"why":"Supplies the smoothness condition H3 that converts sums of external regrets into social-cost bounds.","marker":"(Roughgarden, 2015)"},{"why":"Provides the external-to-swap regret reduction that the contextual Blum-Mansour procedure builds on.","marker":"(Blum and Mansour, 2007)"}],"fun_headline_variants":["Mispredictions, not game drift, drive regret in changing games","Regret in changing games depends on prediction misses","Predictions, not drift: new bound for time-varying games","POWMU ties regret to mispredictions in dynamic games","Contextual optimism: regret scales with prediction errors"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The context set $\\mathcal{Z}$ must be finite and known in advance, because POMWU keeps a separate OMWU instance for each of the $m$ contexts and every bound contains $m$; the paper does not prove an infinite-context version.","fun_headline_variants_meta":{"raw":{"variants":["Mispredictions, not game drift, drive regret in changing games","Regret in changing games depends on prediction misses","Predictions, not drift: new bound for time-varying games","POWMU ties regret to mispredictions in dynamic games","Contextual optimism: regret scales with prediction errors"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000607,"raw_usage":{"total_tokens":2866,"prompt_tokens":1020,"completion_tokens":1846,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":636,"completion_tokens_details":{"reasoning_tokens":1764}},"tokens_in":636,"tokens_out":1846,"duration_ms":11688,"temperature":1.0,"reasoning_tokens":1764,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T21:10:36.941416+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run POMWU with a perfect oracle predictor ($L_T = 0$) on a finite-context game for $T = 10^6$ with $\\eta$ tuned as in Proposition 6; the theorem predicts per-agent contextual regret growing like $T^{1/4}$. If the empirical regret grows linearly, or if the $m=1$ static case fails to reproduce the known optimistic-MWU behavior, the contextual RVU bound is falsified.","supporting_citations":[{"cited_title":"Fast Convergence of Regularized Learning in Games","cited_arxiv_id":"1507.00407","evidence_quote":"Supplies the static-game RVU regret, equilibrium, and social-welfare rates that POMWU recovers when prediction errors are bounded."},{"cited_title":"Contextual Games: Multi-Agent Learning with Side Information","cited_arxiv_id":"2107.06327","evidence_quote":"Provides the contextual game setting, the definition of contextual coarse correlated equilibrium, and the contextual regret comparator used in the model."},{"cited_title":"Near-optimal no-regret learning in general games","cited_arxiv_id":null,"evidence_quote":"Introduces the optimistic multiplicative weights update that POMWU extends to predicted contexts."},{"cited_title":"No-regret learning in time-varying zero-sum games","cited_arxiv_id":null,"evidence_quote":"Provides the time-varying zero-sum game dynamic regret bounds with path-length terms that the paper shows become vacuous for easy-to-predict variations."},{"cited_title":"Intrinsic robustness of the price of anarchy","cited_arxiv_id":null,"evidence_quote":"Supplies the smoothness condition H3 that converts sums of external regrets into social-cost bounds."}],"review_version":1}