Learning to Steer Learners in Games

• URL: http://arxiv.org/abs/2502.20770v1
• Date: Fri, 28 Feb 2025 06:43:15 GMT
• Title: Learning to Steer Learners in Games
• Authors: Yizhou Zhang, Yi-An Ma, Eric Mazumdar,
• Abstract summary: We consider the problem of learning to exploit learning algorithms through repeated interactions in games.<n>We first show that this is impossible if the only knows that the learner is using an algorithm from the general of no-regret algorithms.<n>We demonstrate the effectiveness of this approach if the learner's algorithm is drawn from a smaller class by analyzing a mirror ascent with known regularizer and step sizes.
• Score: 13.843722297585158
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of learning to exploit learning algorithms through repeated interactions in games. Specifically, we focus on the case of repeated two player, finite-action games, in which an optimizer aims to steer a no-regret learner to a Stackelberg equilibrium without knowledge of its payoffs. We first show that this is impossible if the optimizer only knows that the learner is using an algorithm from the general class of no-regret algorithms. This suggests that the optimizer requires more information about the learner's objectives or algorithm to successfully exploit them. Building on this intuition, we reduce the problem for the optimizer to that of recovering the learner's payoff structure. We demonstrate the effectiveness of this approach if the learner's algorithm is drawn from a smaller class by analyzing two examples: one where the learner uses an ascent algorithm, and another where the learner uses stochastic mirror ascent with known regularizer and step sizes.

Related papers

• Learning to Play Against Unknown Opponents [9.346742321348366]
  We show how to efficiently construct an optimal learning algorithm when the learning agent is not constrained to no-regret.<n>All these results make use of recently developed machinery that converts the analysis of learning algorithms to the class of corresponding geometric objects known as menus.
  arXiv  Detail & Related papers  (2024-12-24T09:05:06Z)
• Tree-Based Adaptive Model Learning [62.997667081978825]
  We extend the Kearns-Vazirani learning algorithm to handle systems that change over time. We present a new learning algorithm that can reuse and update previously learned behavior, implement it in the LearnLib library, and evaluate it on large examples.
  arXiv  Detail & Related papers  (2022-08-31T21:24:22Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  We study repeated two-player games where one of the players, the learner, employs a no-regret learning strategy. We consider general Bayesian games, where the payoffs of both the payoffs of both the learner and the learner could depend on the type.
  arXiv  Detail & Related papers  (2022-05-17T18:10:25Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  Learning from repeated play in a fixed zero-sum game is a classic problem in game theory and online learning. We develop a single parameter-free algorithm that simultaneously enjoys favorable guarantees under three performance measures. Our algorithm is based on a two-layer structure with a meta-algorithm learning over a group of black-box base-learners satisfying a certain property.
  arXiv  Detail & Related papers  (2022-01-30T06:10:04Z)
• The Information Geometry of Unsupervised Reinforcement Learning [133.20816939521941]
  Unsupervised skill discovery is a class of algorithms that learn a set of policies without access to a reward function. We show that unsupervised skill discovery algorithms do not learn skills that are optimal for every possible reward function.
  arXiv  Detail & Related papers  (2021-10-06T13:08:36Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Mastering Rate based Curriculum Learning [78.45222238426246]
  We argue that the notion of learning progress itself has several shortcomings that lead to a low sample efficiency for the learner. We propose a new algorithm, based on the notion of mastering rate, that significantly outperforms learning progress-based algorithms.
  arXiv  Detail & Related papers  (2020-08-14T16:34:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.