A new algorithm calculates optimal strategies for two-player zero-sum games.
problem Computing the optimal strategies for two-player zero-sum games.
method Extending successive relaxation to two-player zero-sum games and developing a generalized minimax Q-learning algorithm.
result The proposed algorithm converges and effectively computes optimal strategies.
Gradient methods converge exponentially in concave network games.
problem Finding Nash equilibria in concave network zero-sum games.
method Gradient Ascent and Optimistic Gradient Ascent analyses.
result Exponential convergence rates in various game settings.
New algorithm finds near-optimal policies efficiently in zero-sum games.
problem Lack of provable efficiency guarantees for policy optimization in zero-sum games.
method Policy optimization algorithm with function approximation.
result Proves efficient convergence to near-optimal policies with polynomial samples and iterations.
New game approximates mean curvature flow evolution.
problem Approximating geometric mean curvature flow evolution.
method Two-player zero-sum game with probabilistic elements.
result Value function approximates mean curvature flow.
New assumptions and algorithm solve offline two-player zero-sum Markov games.
problem Solving offline two-player zero-sum Markov games under insufficient assumptions.
method Proposed unilateral concentration assumption and pessimism-type algorithm.
result Algorithm efficiently learns Nash equilibrium under unilateral concentration.
Study proposes new OPE estimators for two-player zero-sum games.
problem Evaluating new policies using historical data from a different policy in multi-player zero-sum games.
method Doubly robust and double reinforcement learning estimators to project exploitability.
result Prove exploitability estimation error bounds and regret bounds for policy profiles.
Study Nash equilibrium in non-zero-sum game with Bermudan strategies.
problem Optimizing pay-offs in non-linear non-zero-sum games.
method Recursive construction to find Nash equilibrium.
result Existence of Nash equilibrium in non-zero-sum game.
Optimal algorithm for two-player zero-sum games with linear parameterization.
problem Finding Nash Equilibrium in two-player zero-sum Markov games with linear transition.
method Nash-UCRL algorithm, Coarse Correlated Equilibrium, Optimism-in-Face-of-Uncertainty.
result Proves i l d e O ( d H T ) ilde{O}(dH\sqrt{T}) i l d e O ( d H T ) regret bound, matching lower bound up to logarithmic factors. The paper explores how regularization can lead to convergence in imperfect information games.
problem Finding equilibrium in imperfect information games with imperfect information.
method Investigates Follow the Regularized Leader dynamics and how adding a regularization term can lead to strong convergence guarantees.
result The approach leads to algorithms that converge exactly to the Nash equilibrium in imperfect information games.
Gradient-based methods for games suffer from discrete update steps that cause drift, affecting performance.
problem Gradient-based methods for two-player games suffer from drift due to discrete update steps.
method Derived modified continuous dynamical systems to closely follow the discrete dynamics of games.
result Identified distinct components of discretization drift that can alter or destabilize game performance.
Optimistic Hedge achieves optimal regret bounds in two-player zero-sum games.
problem Achieving optimal regret bounds for optimistic Hedge in two-player zero-sum games.
method Refined regret analysis and optimization problem formulation.
result Optimistic Hedge achieves O ( log m log n ) O(\sqrt{\log m \log n}) O ( log m log n ) regret bounds, matching upper and lower bounds. Research tackles alliance formation in many-player zero-sum games, showing reinforcement learning fails but a contract mechanism can help.
problem Tackles the challenge of alliance formation in many-player zero-sum games.
method Demonstrates the social dilemma aspect of alliance formation, introduces a contract mechanism to augment reinforcement learning.
result Naïve reinforcement learning fails to form alliances, but a contract mechanism can help.
Algorithm learns NE in imperfect information games with imperfect feedback.
problem Learning Nash equilibrium in imperfect information games with bandit feedback.
method IXOMD algorithm for model-free learning with 1 / T 1/\sqrt{T} 1/ T convergence rate. result IXOMD achieves 1 / T 1/\sqrt{T} 1/ T convergence rate to NE. A geometric approach to differential game theory is illustrated. The parallel pursuit is considered as a two-player zero-sum differential game. The optimal strategies of each player is designed based on Riemann-Finsler geometry. Our approach incorporates a closed loop optimal control and the presentation is familiar wi…
We consider two-player non-zero-sum stopping games in discrete time. Unlike Dynkin games, in our games the payoff of each player is revealed after both players stop. Moreover, each player can adjust her own stopping strategy according to the other player's action. In the first part of the paper, we consider the game wh…
Method identifies mixed Nash equilibria in high dimensions for training mixtures of GANs.
problem Finding Nash equilibria in two-player zero-sum continuous games, especially in high dimensions.
method Parametrizing mixed strategies as mixtures of particles, updating their positions and weights using gradient descent-ascent.
result Global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic.
Mutation improves FTRL convergence in zero-sum games.
problem Lack of last-iterate convergence in FTRL variants.
method Introduced mutation to perturb action probabilities in FTRL.
result M-FTRL converges to Nash equilibria under full-information feedback.
This paper studies a 2-players zero-sum Dynkin game arising from pricing an option on an asset whose rate of return is unknown to both players. Using filtering techniques we first reduce the problem to a zero-sum Dynkin game on a bi-dimensional diffusion ( X , Y ) (X,Y) ( X , Y ) . Then we characterize the existence of a Nash equilibrium…
A RL approach finds Nash equilibrium for turn-based zero-sum games.
problem Finding Nash equilibrium in two-player turn-based zero-sum games.
method EIS method combining exploration, policy improvement, and supervised learning.
result EIS method finds an ε-approximate value function of Nash equilibrium in O(ε^(-(d+4))) steps.
Consider a two-player zero-sum stochastic game where the transition function can be embedded in a given feature space. We propose a two-player Q-learning algorithm for approximating the Nash equilibrium strategy via sampling. The algorithm is shown to find an ε ε ε -optimal strategy using sample size linear to the number …
Study learns optimal strategies in imperfect information games with self-play.
problem Learning optimal strategies in imperfect information games.
method Proposes Follow the Regularized Leader (FTRL) algorithms for imperfect information games.
result Proposes two FTRL algorithms: Balanced FTRL and Adaptive FTRL.
Algorithm learns from changing zero-sum games with no regret.
problem Learning in time-varying zero-sum games.
method Developed a single parameter-free algorithm with three performance measures.
result Algorithm recovers best known results for fixed games and adapts to non-stationarity.
New algorithm improves sample efficiency for zero-sum Markov games.
problem Improving sample efficiency for model-free algorithms in zero-sum Markov games.
method Proposes a model-free stage-based Q-learning algorithm using variance reduction techniques.
result Achieves optimal sample complexity for finding ε-optimal Nash Equilibrium.
Algorithm finds near-optimal strategy in changing zero-sum games.
problem Finding near-optimal strategy in changing zero-sum games.
method Designing an algorithm with small NE regret for online matrix games.
result Achieves near-optimal dependence on the number of rounds and number of actions.
Paper solves discounted stochastic games with near-optimal time and sample complexity.
problem Solving discounted stochastic two-player games with optimal complexity.
method Generalizes Q-learning to two-player strategy computation, overcoming limitations of existing methods.
result Near-optimal ε ε ε -strategy computation with polylogarithmic factors in 1 − γ 1 - γ 1 − γ and ε − 2 ε^{-2} ε − 2 . Paper develops efficient algorithms for zero-sum Markov games with general function classes.
problem Challenging settings in zero-sum Markov games with parameterized value functions or models.
method Developed new model-free and model-based algorithms for decoupled and coordinated settings.
result Improved sample complexity and regret bounds for various settings.
Transformers learn to play games in-context, proving Nash equilibrium.
problem Understanding in-context game-playing capabilities of pre-trained transformers.
method Theoretical guarantees and constructional results for transformer architecture in multi-agent games.
result Pre-trained transformers can learn Nash equilibrium in-context for two-player zero-sum games.
We propose local symplectic surgery, a two-timescale procedure for finding local Nash equilibria in two-player zero-sum games. We first show that previous gradient-based algorithms cannot guarantee convergence to local Nash equilibria due to the existence of non-Nash stationary points. By taking advantage of the differ…
Paper solves complex game theory problems with new equations.
problem Zero-sum stochastic games with non-Markovian switching.
method New multidimensional SRE and BSDE solutions.
result Existence and uniqueness of SRE solutions.
We develop an option pricing model based on a tug-of-war game. This two-player zero-sum stochastic differential game is formulated in the context of a multi-dimensional financial market. The issuer and the holder try to manipulate asset price processes in order to minimize and maximize the expected discounted reward. W…
Pessimistic model-based algorithm finds Nash equilibria in zero-sum Markov games from offline data.
problem Learning Nash equilibria in two-player zero-sum Markov games from limited data.
method Pessimistic model-based algorithm with Bernstein-style lower confidence bounds (VI-LCB-Game).
result Proves sample complexity no larger than C c l i p p e d ⋆ S ( A + B ) ( 1 − γ ) 3 ε 2 \frac{C_{\mathsf{clipped}}^\star S(A+B)}{(1-γ)^3 \varepsilon^2} ( 1 − γ ) 3 ε 2 C clipped ⋆ S ( A + B ) , achieving minimax optimality. This paper optimizes model-based RL for two-player zero-sum games with near-optimal sample complexity.
problem Optimizing model-based reinforcement learning for two-player zero-sum games with minimal samples.
method Model-based reinforcement learning approach for two-player discounted zero-sum Markov games with a generative model.
result Achieves a sample complexity of i l d e O ( ∣ S ∣ ∣ A ∣ ∣ B ∣ ( 1 − γ ) − 3 ε − 2 ) ilde O(|S||A||B|(1-γ)^{-3}ε^{-2}) i l d e O ( ∣ S ∣∣ A ∣∣ B ∣ ( 1 − γ ) − 3 ε − 2 ) for finding the Nash equilibrium and ε-NE policies. Paper solves learning imperfect-information games with fewer episodes.
problem Learning imperfect-information extensive-form games from bandit feedback.
method Balanced Online Mirror Descent and Balanced Counterfactual Regret Minimization algorithms.
result Achieves near-optimal sample complexity for finding approximate Nash equilibria.
Unified framework for estimating reward functions in competitive games.
problem Estimating unknown reward functions in competitive games.
method Unified framework with entropy regularization for reward function recovery.
result Strong theoretical guarantees and practical effectiveness demonstrated.
Algorithm finds Nash equilibria in complex games with function approximation.
problem Learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation.
method Online learning algorithm using upper and lower confidence bounds derived from optimism in the face of uncertainty.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret with polynomial complexity, under mild assumptions. DREAM learns optimal strategies in imperfect games without needing a simulator.
problem Learning optimal strategies in imperfect-information games with multiple agents.
method DREAM is a deep reinforcement learning algorithm that converges to Nash Equilibria and coarse correlated equilibria.
result DREAM achieves state-of-the-art performance in benchmark games and is competitive with simulator-based algorithms.
We study optimal behavior of energy producers under a CO_2 emission abatement program. We focus on a two-player discrete-time model where each producer is sequentially optimizing her emission and production schedules. The game-theoretic aspect is captured through a reduced-form price-impact model for the CO_2 allowance…
Improved model-based reinforcement learning for multi-agent Markov games.
problem Suboptimal sample complexity for model-based algorithms in multi-agent reinforcement learning.
method Optimistic Nash Value Iteration (Nash-VI) for two-player zero-sum Markov games.
result First model-based algorithm matching information-theoretic lower bound with improved sample complexity.
Paper tackles multiplayer symmetric games, securing equal share for n players.
problem Multiplayer games lack unique equilibria, making guarantees unreliable.
method Identifies conditions for equal share, designs efficient algorithms inspired by no-regret learning.
result Proves algorithms achieve approximate equal share across various settings.
A new multi-armed bandit framework with credal sets for uncertain outcomes.
problem Optimizing decisions under uncertainty with unknown outcomes.
method Introduces a novel multi-armed bandit framework with credal sets and defines regret as lower prevision.
result Upper bounds on regret for certain hypothesis classes and lower bounds for special cases.
New algorithms achieve logarithmic regret in KL-regularized Markov games.
problem Improving sample efficiency in game-theoretic settings with KL regularization.
method Developed OMG and SOMG algorithms for matrix and Markov games, using best response sampling and superoptimistic bonuses.
result Logarithmic regret in T T T that scales inversely with KL regularization strength β β β . New approach improves robustness of deep neural networks without overfitting.
problem Adversarial vulnerability of deep neural networks.
method Non-zero-sum bilevel formulation of adversarial training.
result Algorithm matches and outperforms state-of-the-art attacks, maintains robustness, and avoids overfitting.
A method learns to solve multilevel combinatorial problems with two players.
problem Multilevel combinatorial optimization problems with multiple players.
method Value-based multi-agent reinforcement learning in a graph neural network framework.
result Close to optimal solutions on graphs up to 100 nodes, with a significant speedup.
A large body of research is currently investigating on the connection between machine learning and game theory. In this work, game theory notions are injected into a preference learning framework. Specifically, a preference learning problem is seen as a two-players zero-sum game. An algorithm is proposed to incremental…
Efficient reinforcement learning for simultaneous-move zero-sum games using optimistic value iteration.
problem Learning optimal strategies in simultaneous-move zero-sum Markov games with function approximation.
method Developed an optimistic variant of least-squares minimax value iteration algorithm for offline and online settings.
result Achieved an upper bound of i l d e O ( d 3 H 3 T ) ilde O(\sqrt{d^3 H^3 T}) i l d e O ( d 3 H 3 T ) on duality gap and regret. Study adversarial attacks on cost-sensitive classifiers.
problem Safety-critical classification problems with cost-sensitive predictions.
method Used state-of-the-art adversarially-resistant neural networks and analyzed as a two-player zero-sum game.
result Introduced a new cost-sensitive attack that performs better than targeted attacks in some cases.
We study the problem of learning classifiers robust to universal adversarial perturbations. While prior work approaches this problem via robust optimization, adversarial training, or input transformation, we instead phrase it as a two-player zero-sum game. In this new formulation, both players simultaneously play the s…
Policy gradient method proves convergence in imperfect-information games.
problem Policy gradient methods in imperfect-information games (EFGs).
method Policy gradient approach with best-iterate convergence.
result Policy gradient leads to provable best-iterate convergence in self-play EFGs.