mlsanityData to 14 Oct 2026

Learning to Play Against Unknown Opponents

arXiv 2412.18297 ↗First posted 24 Dec 2024cs.GT cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

We consider the problem of a learning agent who has to repeatedly play a general sum game against a strategic opponent who acts to maximize their own payoff by optimally responding against the learner's algorithm. The learning agent knows their own payoff function, but is uncertain about the payoff of their opponent (knowing only that it is drawn from some distribution D). What learning algorithm should the agent run in order to maximize their own total utility, either in expectation or in the worst-case over D? When the learning algorithm is constrained to be a no-regret algorithm, we demonstrate how to efficiently construct an optimal learning algorithm (asymptotically achieving the optimal utility) in polynomial time for both the in-expectation and worst-case problems, independent of any other assumptions. When the learning algorithm is not constrained to no-regret, we show how to construct an varepsilon-optimal learning algorithm (obtaining average utility within varepsilon of the optimal utility) for both the in-expectation and worst-case problems in time polynomial in the size of the input and 1/varepsilon, when either the size of the game or the support of D is constant. Finally, for the special case of the maximin objective, where the learner wishes to maximize their minimum payoff over all possible optimizer types, we construct a learner algorithm that runs in polynomial time in each step and guarantees convergence to the optimal learner payoff. All of these results make use of recently developed machinery that converts the analysis of learning algorithms to the study of the class of corresponding geometric objects known as menus.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 19 of its 34 references that are in the map. First posted on arXiv 24 Dec 2024.

Builds on

19 of 34 references.

References · 19

  1. 2019Strategizing against No-regret Learnerscited by 50
  2. 2017Selling to a No-Regret Buyercited by 43
  3. 2022Strategizing against Learners in Bayesian Gamescited by 34
  4. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 32
  5. 2023Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agentscited by 25
  6. 2017Efficient Convex Optimization with Membership Oraclescited by 23
  7. 2024Contracting with a Learning Agentcited by 23
  8. 2021Auctions Between Regret-Minimizing Agentscited by 22
  9. 2023Is Learning in Games Good for the Learners?cited by 20
  10. 2023Selling to Multiple No-Regret Buyerscited by 19
  11. 2020Learning to Play Sequential Games versus Unknown Opponentscited by 18
  12. 2021How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agentscited by 17
7 more
  1. 2024Pareto-Optimal Algorithms for Learning in Gamescited by 16
  2. 2023Online Learning in Stackelberg Games with an Omniscient Followercited by 15
  3. 2023From External to Swap Regret 2.0: An Efficient Reduction and Oblivious Adversary for Large Action Spacescited by 11
  4. 2022Efficient Stackelberg Strategies for Finitely Repeated Gamescited by 9
  5. 2023Persuading a Behavioral Agent: Approximately Best Responding and Learningcited by 7
  6. 2022Robust No-Regret Learning in Min-Max Stackelberg Gamescited by 5
  7. 2024Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactionscited by 5

Built on by

Cited by year

Citing papers per year: 2025: 3.

3 papers.

  1. 2025Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learnerscited by 1
  2. 2025Learning Local Stackelberg Equilibria from Repeated Interactions with a Learning Agentcited by 1
  3. 2025The Bidding Games: Reinforcement Learning for MEV Extraction on Polygon Blockchaincited by 0