{"id":"3f1bffb2-1089-42a6-bd35-f18a923e60ca","arxiv_id":"1908.08773","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"An opponent-aware Q-learning scheme, built on level-k reasoning and Bayesian averaging over adversary types, improves robustness and exploitability in security games and repeated matrix games.","lead":"This paper introduces a framework for reinforcement learning agents that must act while an opponent can interfere with their rewards. It extends standard Q-learning by modeling the adversary's likely actions, using level-k reasoning and a Bayesian mixture over opponent types.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Convergence proof covers a fixed opponent policy, not the online opponent-model estimator used in Algorithm 1, so the theoretical guarantee is narrower than claimed.","rationale":"The reader's weakest assumption correctly identifies that the guarantees depend on a good estimate of the opponent's policy and on the opponent belonging to the modeled class. My analysis sharpens this to a precise soundness gap: the contraction lemma in Appendix A is proved for a fixed p(b'|s'), while Algorithm 1 estimates p online from an opponent Q-function that is itself being learned. The resulting time-varying operator is not covered by standard Q-learning convergence theorems, so the paper's statement that 'we may use RL convergence results' is not justified for the implemented algorithm. This is the most load-bearing concern because the theoretical convergence claim is the paper's main formal support for the framework. I do not see a fatal flaw: the framework is coherent, the empirical studies are extensive and include honest negative results, and the contraction lemma is correct for its narrower scope. The concern is best resolved by the authors clarifying the convergence statement, citing related hyper-Q learning work, and ideally providing conditions under which the online opponent estimator is consistent. This matches the reader's conditional verdict, so no verdict change is needed.","tokens_in":17659,"tokens_out":5376,"duration_ms":61129,"concrete_test":"Run Algorithm 1 exactly as specified for a level-2 DM against a stationary opponent who plays a fixed mixed strategy (e.g., 50/50 in the stateless security game of Section 4.2.1), so the true p(b|s) is constant. Record the estimated p_t and Q^2_t over 10^5 steps. If p_t does not converge to the true p, or if Q^2_t does not converge to the fixed point of the contraction operator H from Appendix A evaluated with the true p, then the online estimation step is not covered by the contraction lemma.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's theoretical claim is that the learning rule in Eqs. (3)-(4) converges because the operator in Lemma 1 (Appendix A) is a contraction, and therefore 'we may use RL convergence results.' But Lemma 1 fixes the opponent policy p(b'|s') and the transition kernel; it is a statement about a single MDP with a known adversary. Algorithm 1, however, maintains Q^1, an estimate of the opponent's Q-function, and derives p(b|s) from it at each step. That estimated policy changes as the opponent learns and as the DM updates Q^1, so the stochastic process is a Q-learning iteration whose target operator H_t depends on the current estimate. The contraction proof does not apply to a time-varying operator. The paper's own Fig. 9(c) confirms the practical side of this gap: a level-3 DM modeling a level-2 opponent is exploited by a level-1 opponent, because the online opponent model is inaccurate. Thus the statement that the update rule is a contraction supports convergence only for a fixed, correctly specified opponent model, not for the implemented online level-k scheme. The empirical results are broad and include honest failure cases, but the central convergence claim overreaches what is proved.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Threatened Markov Decision Processes (TMDPs), an extension of MDPs in which a supported decision maker (DM) faces an adversary whose actions b enter both the transition and reward processes. The DM maintains beliefs p_A(b|s) about the adversary's actions, and the paper proposes modifying Q-learning by averaging over these beliefs, together with a level-k thinking hierarchy in which the DM also estimates the opponent's Q-function. The framework includes fictitious-play-style and Bayesian opponent models, a model-averaging scheme for uncertain opponent types, and an extension to multiple adversaries. The theoretical contribution is a contraction argument in Appendix A intended to justify convergence of the update rule. Empirical results are reported for repeated matrix games, AI Safety Gridworlds, and a security resource allocation (Blotto) game, with code released online.","tokens_in":17940,"tokens_out":6032,"duration_ms":60933,"significance":"If the claims hold, the TMDP framework is a useful one-sided prescriptive tool for security-oriented reinforcement learning, and the level-k scheme is a natural way to inject opponent modeling into Q-learning without common-knowledge assumptions. The paper's strengths include a broad and honest empirical study, including a documented failure case (Fig. 9(c)), robustness checks in Appendix D, and publicly released code. The contraction lemma in Appendix A is correct for a fixed opponent policy, and the computational complexity analysis is sensible. The significance is tempered, however, by the gap between the proven contraction result and the online opponent-model estimator used in the actual algorithm, as well as by the reliance on the opponent being close to the modeled class.","major_comments":[{"comment":"Lemma 1 and the surrounding argument prove that the operator H is a contraction only for a fixed opponent policy p(b'|s') and a fixed transition kernel. In Algorithm 1, however, the expectation in the Q2 update is taken with respect to p_A(b|s1), which is recomputed at every step from the evolving estimate Q^1 of the opponent's Q-function. The resulting stochastic update is a Q-learning iteration with a time-varying target operator, so the cited standard convergence result (Ref. [45]) does not apply, and the paper's statement that 'we may use RL convergence results' overreaches what is proved. I recommend either proving convergence of the coupled stochastic approximation under explicit conditions (e.g., consistency or slow variation of the opponent-model estimates), or restating the theoretical contribution as convergence of the TMDP optimality operator for a fixed opponent model and presenting the online level-k scheme as a heuristic supported by the experiments.","section":"Appendix A; Eqs. (3)-(4); Algorithm 1"},{"comment":"The failure of the level-3 DM against a level-1 opponent in Fig. 9(c) is a direct illustration of the load-bearing assumption that the opponent is, or is close to, the modeled type. The paper acknowledges this and proposes the Bayesian model-averaging scheme of Section 3.3, but that scheme is demonstrated on only one configuration (Figs. 9(d)-(e)), and no characterization is given of when the posterior will concentrate on the correct model. Without such a characterization, the claim that the framework 'generalize[s] between different kinds of opponents' remains an empirical observation rather than a supported property. The paper should either add a formal or systematic empirical study of model misspecification (e.g., varying the true opponent level and the candidate model set) or explicitly limit the generalization claim.","section":"Section 4.2.2 (Fig. 9(c)-(e))"},{"comment":"The text repeatedly states that the FPQ-learner 'converges to the Nash equilibrium' in IPD, ISH, and IC, but the evidence shown is only reward trajectories. Since equilibrium selection is a policy-level claim, please report the empirical frequency of the DM's actions (as is done for the stateless security game in Section 4.2.2) or a distance-to-equilibrium metric for the matrix games; otherwise the reader cannot distinguish convergence to an equilibrium from convergence of average rewards.","section":"Section 4.1, Figs. 2-4"}],"minor_comments":[{"comment":"The abstract contains the typo 'suporting' and the Appendix A title uses 'TDMPs' instead of 'TMDPs'; please correct these.","section":"Abstract and Appendix A title"},{"comment":"The caption for Fig. 9 says 'Rewards obtained against the exponential smoother adversary,' but panels (a)-(e) are against level-k Q-learners, as Section 4.2.2 itself states; the caption should be updated to reflect the actual opponents.","section":"Fig. 9 caption"},{"comment":"The sentence 'we focus on the stateless version of a TMDP and analyze the policies learnt by the DM, and analyze the policies learnt by the DM' repeats the same phrase; please remove the duplication.","section":"Section 4.1"},{"comment":"The deep-Q generalization omits standard DQN machinery such as target networks and replay buffers; even if these are intended to be unchanged from standard DQN, a sentence clarifying that the extension inherits the usual deep-RL components would help reproducibility.","section":"Algorithm 4 (Appendix B)"},{"comment":"Equation (4) defines Q(s,a) as an expectation over the opponent's actions, but the surrounding text sometimes refers to Q(s,a) without distinguishing the decision Q-function from the action-opponent Q(s,a,b) in Eq. (3); a brief notational clarification would avoid ambiguity.","section":"Section 3, Eq. (4)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is within scope for the journal and I found no evidence of citation manipulation. The main issue is the mismatch between the contraction proof, which holds for a fixed opponent model, and the online coupled update in Algorithm 1; this is fixable by either extending the theory or carefully circumscribing the claim. The empirical breadth and the honest reporting of a failure case are strengths, and the released code is a plus. I would encourage the authors to add a more systematic study of model misspecification, since the current Fig. 9(c) actually demonstrates the central fragility of the approach."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version. This paper does something genuinely useful: it gives a practical, one-sided way to make Q-learning robust to an adversary by averaging over opponent beliefs, and it wraps that in a level-k hierarchy with Bayesian model averaging over opponent types. The empirical section is broader than typical, includes honest failure cases (a level-3 DM exploited by a level-1 opponent, Fig 9c), and the code is public. If you work on adversarial RL or security games, this is worth knowing about.\n\nWhat is actually new: the TMDP formalism is a clean way to extend MDPs with an opponent action, the level-k thinking scheme that estimates the opponent's Q-function is a useful concrete algorithm, and the Dirichlet model-averaging over different opponent models is a nice practical answer to the 'which level is my opponent?' problem. Credit where due: the contraction lemma in Appendix A is correct, as far as it goes, for a fixed opponent policy. The experiments span matrix games, gridworlds, and a Blotto-style allocation game, which is more than most papers in this space.\n\nThe soft spots, in order of real importance. First, the convergence claim is narrower than stated. Lemma 1 fixes p(b|s); Algorithm 1 estimates that policy online from a learned opponent Q-function, so the operator is time-varying and the standard Q-learning convergence argument does not transfer. The paper does not quite misstate this—Appendix A says 'if she knows his policy, or has a good estimate of it'—but the conclusion in Section 5 that 'we may use RL convergence results' is an overreach. The practical consequence shows in Fig 9(c), where a misspecified level assumption gets the DM exploited.\n\nSecond, the central update rule is close to hyper-Q learning (Tesauro 2003), which is not cited. The level-k hierarchy and the Bayesian averaging are the actual novelty, and the paper would be stronger and more honest if it acknowledged the lineage and compared against a hyper-Q baseline.\n\nThird, and minor: the main evidence is qualitative reward curves; the hyperparameter robustness table is nice, but the paper does not report variance across seeds for the headline gridworld results, so I would want a few summary numbers.\n\nWho is this for? Researchers in multi-agent RL and security games who want a practical opponent-modeling recipe. It deserves a serious referee. I would accept it with minor-to-major revision: fix the convergence statement, cite and compare against hyper-Q, and add summary statistics.","headline":"Useful, honest paper on level-k Q-learning for adversarial settings, but the convergence theorem only covers a fixed opponent policy and the core update is essentially hyper-Q learning, which is not cited or compared against.","tokens_in":18425,"tokens_out":2042,"would_cite":true,"duration_ms":20236,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A single RL agent can learn robust policies against reward-manipulating opponents by averaging its Q-learning update over their likely actions.","keywords":["threatened Markov decision processes","adversarial reinforcement learning","level-k thinking","opponent modeling","Q-learning","security games","adversarial risk analysis","multi-agent reinforcement learning"],"falsifier":"Run a level-3 TMDP learner against a level-1 Q-learner in the stateless security game: the paper's own Fig. 9(c) shows the level-1 opponent exploits the level-3 agent, so a decisive test is whether the Bayesian model-averaging version reliably recovers positive reward when the prior is centered on the wrong level. A second test is to compare the TMDP averaged update against minimax-Q and WoLF-PHC in a zero-sum stochastic game over many seeds; if the TMDP learner's average reward is not at least as high, the robustness claim is not supported.","tokens_in":1576,"feed_emoji":"🛡️","tokens_out":1942,"duration_ms":79625,"temperature":0.7,"pith_summary":"The paper introduces Threatened Markov Decision Processes (TMDPs), an extension of MDPs in which an adversary's actions modify rewards and transitions, and proposes a Q-learning variant that averages the standard update over the agent's beliefs about the adversary's action. The authors prove that the resulting update operator is a contraction, so standard reinforcement-learning convergence arguments apply. In experiments, the supported agent reaches Nash equilibria in repeated matrix games, avoids exploitation in a security gridworld, and handles multiple attackers in a resource-allocation game. The intended payoff is a practical way to make single-agent reinforcement learning robust to opponents without assuming common knowledge.","feed_headline":"Averaging Q-learning over the enemy's moves beats opponent-blind RL","feed_subtitle":"Model the adversary as a level-k thinker and one agent can defend against reward-hijacking opponents.","key_machinery":"The load-bearing object is the Threatened Markov Decision Process, a tuple $(S,A,B,T,R,p_A)$ that augments an MDP with a threat-action space $B$ for the opponent and a belief distribution $p_A(b|s)$ for the supported agent. Its mechanism is the averaged Q-learning update: first learn an action-pair value $Q(s,a,b)$, then collapse it to $Q(s,a)=\\mathbb{E}_{p_A(b|s)}[Q(s,a,b)]$ before selecting an $\\epsilon$-greedy action. That averaging is what converts opponent uncertainty into a robust single-agent policy, and Lemma 1 shows the resulting operator is a $\\gamma$-contraction under the supremum norm.","core_discovery":"The central claim is that a decision maker can defend against an opponent who interferes with the reward process by replacing the standard Q-learning update with an expectation over the adversary's likely action: $Q(s,a)=\\mathbb{E}_{p_A(b|s)}[Q(s,a,b)]$, where $Q(s,a,b)$ itself updates with $r(s,a,b)+\\gamma\\max_{a'}\\mathbb{E}_{p_A(b'|s')}[Q(s',a',b')]$. The belief $p_A(b|s)$ is learned either from empirical frequencies in the style of fictitious play, from a level-$k$ hierarchy in which each player models the other as a level-$(k-1)$ thinker, or from a Bayesian mixture over opponent models. The paper shows that the operator defining this update is a contraction in the supremum norm, so the learned Q-function converges. It then demonstrates empirically that an opponent-aware level-2 learner outperforms both naive Q-learning and the WoLF-PHC baseline in security settings.","pith_inferences":["Because the contraction proof takes the opponent policy $p_A(b|s)$ as known, the scheme's robustness in practice hinges on online estimation of that policy; a misspecified level can be worse than no model, so an adaptive level-selection rule with a misspecification guarantee is a natural next step.","The update rule is agnostic to how the Q-function is represented, so the same averaging idea should transfer to policy-gradient and actor-critic learners, which would cover continuous action spaces not treated in the paper.","The Bayesian mixture over opponent models points toward deployment-time adaptation: keep a distribution over opponent types, update it from observed actions, and train a single policy that is good against the mixture rather than against a fixed level-$k$ type.","The repeated-game results suggest the framework's advantage is largest when the opponent reacts to the supported agent's choices; in settings where both players learn at the same speed, level selection itself becomes the strategic decision and could be treated as an upper-level learning problem."],"forward_implications":["A level-1 fictitious-play learner reaches the Nash equilibrium in repeated Prisoner's Dilemma, Stag Hunt, and Chicken games, while an opponent-blind Q-learner does not.","Adding memory of the previous joint action lets the same framework learn to cooperate with a Tit-for-Tat opponent in the iterated Prisoner's Dilemma.","In the AI Safety Gridworlds friend-or-foe task, a level-2 learner obtains positive rewards where naive Q-learning is exploited, even when the true adversary is not exactly a level-1 Q-learner.","Maintaining a Bayesian mixture over opponent models lets the decision maker identify whether she faces a level-1 or level-2 opponent and avoids the failure of a mismatched level-3 model.","The update rule generalizes to deep Q-networks by replacing tabular Q-functions with neural function approximators."],"supporting_citations":[{"why":"Supplies the standard Q-learning update rule that the TMDP learner modifies.","marker":"[19]"},{"why":"Provides the adversarial risk analysis perspective of one-sided prescriptive support with uncertainty about the opponent.","marker":"[10]"},{"why":"Supplies fictitious play, the basis of the FPQ-learning variant for non-strategic opponents.","marker":"[20]"},{"why":"Supplies the level-k thinking hierarchy used to model how deeply the opponent reasons.","marker":"[22]"},{"why":"Defines Markov games and minimax-Q, the multi-agent baseline this framework departs from by avoiding common knowledge.","marker":"[23]"},{"why":"Provides the AI Safety Gridworlds friend-or-foe benchmark used to test the decision maker against an adaptive adversary.","marker":"[38]"},{"why":"Supplies WoLF-PHC, the multi-agent learning algorithm used as a comparison opponent.","marker":"[40]"},{"why":"Gives the standard Q-learning convergence proof that the paper's contraction lemma extends.","marker":"[45]"}],"fun_headline_variants":["Expect the enemy's move: opponent-aware Q-learning wins","Level-k opponent thinking beats blind RL in security games","Defend rewards by modeling the adversary as a level-k thinker","Opponent-aware RL: averaging over enemy's moves wins"],"cache_read_input_tokens":20608,"weakest_assumption_plain":"The whole scheme works only if the agent has a good picture of how the opponent decides: when the opponent acts outside the modeled classes, the learned policy can be exploited rather than protected.","fun_headline_variants_meta":{"raw":{"variants":["Expect the enemy's move: opponent-aware Q-learning wins","Level-k opponent thinking beats blind RL in security games","Defend rewards by modeling the adversary as a level-k thinker","Opponent-aware RL: averaging over enemy's moves wins"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001109,"raw_usage":{"total_tokens":4556,"prompt_tokens":811,"completion_tokens":3745,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":427,"completion_tokens_details":{"reasoning_tokens":3678}},"tokens_in":427,"tokens_out":3745,"duration_ms":27025,"temperature":1.0,"reasoning_tokens":3678,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:47:26.375299+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a level-3 TMDP learner against a level-1 Q-learner in the stateless security game: the paper's own Fig. 9(c) shows the level-1 opponent exploits the level-3 agent, so a decisive test is whether the Bayesian model-averaging version reliably recovers positive reward when the prior is centered on the wrong level. A second test is to compare the TMDP averaged update against minimax-Q and WoLF-PHC in a zero-sum stochastic game over many seeds; if the TMDP learner's average reward is not at least as high, the robustness claim is not supported.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the adversarial risk analysis perspective of one-sided prescriptive support with uncertainty about the opponent."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies fictitious play, the basis of the FPQ-learning variant for non-strategic opponents."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the level-k thinking hierarchy used to model how deeply the opponent reasons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines Markov games and minimax-Q, the multi-agent baseline this framework departs from by avoiding common knowledge."},{"cited_title":"Bowling, M","cited_arxiv_id":null,"evidence_quote":"Supplies WoLF-PHC, the multi-agent learning algorithm used as a comparison opponent."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the standard Q-learning convergence proof that the paper's contraction lemma extends."}],"review_version":1}