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. 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. Actor-critic finds Nash in mean-field games with linear-quadratic costs.
problem Finding Nash equilibrium in mean-field Markov games with linear dynamics and quadratic costs.
method Mean-field actor-critic algorithm with linear function approximation.
result Algorithm converges linearly to Nash equilibrium.
New RL algorithms find SNE in Markov games with myopic followers.
problem Finding SNE in Markov games with myopic followers.
method Optimistic and pessimistic variants of least-squares value iteration, incorporating function approximation.
result First provably efficient RL algorithms for SNEs in general-sum Markov games with myopic followers.
Paper optimizes reinforcement learning in self-play games with reduced steps.
problem Optimizing reinforcement learning algorithms for self-play in two-player zero-sum games.
method Proposes optimistic Nash Q-learning and Nash V-learning algorithms with improved sample complexity.
result Achieves sample complexity of O ( S A B ) O(SAB) O ( S A B ) for Nash Q-learning and O ( S ( A + B ) ) O(S(A+B)) O ( S ( A + B )) for Nash V-learning, closing the gap with lower bounds. 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.
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. 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 efficient offline RL in Markov games with general models.
problem Learn approximate equilibria from offline data in Markov games.
method Use Bellman-consistent pessimism for interval estimation and optimize gap relaxation.
result First framework for sample-efficient offline learning in Markov games, handling all equilibria.
Introduces strong equilibrium for time-inconsistent stopping problems in continuous time.
problem Time-inconsistent stopping problems in continuous time.
method Introduces strong equilibrium, compares with existing mild and weak equilibria, and provides an iteration method to construct optimal mild equilibria.
result Optimal mild equilibria are always strong equilibria under certain conditions.
Model shows how adding liquidity in banking system can lead to defaults.
problem Systemic risk and interbank lending in banking systems.
method Simple model using Feller diffusions and Markov Nash equilibrium.
result Adding liquidity leads to defaults in banking system.
The paper examines Nash equilibrium in GANs for stationary Gaussian processes.
problem Existence and uniqueness of Nash equilibrium in GANs for stationary Gaussian processes.
method Analyzes the existence of Nash equilibrium in GANs for stationary Gaussian processes, considering different discriminator families.
result The existence of Nash equilibrium depends on the discriminator family and symmetry properties of the generator family.
New algorithm finds Nash equilibrium in multi-agent games.
problem Extending RL theory to multi-agent settings with large state spaces.
method Proposes an algorithm using an exploiter to find Nash equilibrium policies.
result Proves finding Nash equilibrium is possible with polynomial samples.
New algorithm for solving minimax problems over distributions converges to Nash equilibrium.
problem Solving minimax problems over probability distributions.
method Symmetric Mean-field Langevin Dynamics (MFL-AG and MFL-ABR) with weighted averaging and best response dynamics.
result Converges to mixed Nash equilibrium with average-iterate and last-iterate convergence.
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. This paper improves sample efficiency for learning equilibria in multi-player games.
problem Sample-efficient learning of equilibria in games with many players.
method Designs algorithms for learning CCE and CE with polynomial sample complexity in the number of players.
result First to show polynomial sample complexity for learning CCE and CE in multi-player games.
Novel algorithms for multi-agent reinforcement learning reduce sample complexity.
problem Efficiently learning Nash equilibria in multi-agent settings.
method Information-Directed Sampling (IDS) principles applied to multi-agent reinforcement learning.
result Sample-efficient algorithms for learning Nash equilibria in various multi-agent settings.
GANs may not have Nash equilibria, but proximal training can find solutions.
problem Existence of Nash equilibria in GANs optimization.
method Proximal training approach to find solutions.
result Proximal training finds solutions to GAN problems.
The paper solves a differential game to find optimal extraction and taxation of strategic natural resources.
problem Optimal extraction and taxation of nonrenewable natural resources under fluctuating market values.
method Formulated as a differential game with two players: mining company and government agency. Proved Nash equilibrium existence and solved Hamilton Jacobi Isaacs equations.
result Closed-form solutions for value functions, optimal extraction and taxation rates.
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.
Investors' strategic trading affects asset prices, modeled as a game.
problem Investors' trading rates influence asset prices in dynamic markets.
method Model as a non-zero sum singular stochastic differential game, establishing equivalence between best-response and auxiliary control problems.
result Unique Nash equilibrium is deterministic with a closed-form solution.
Pessimistic Minimax Value Iteration finds efficient NE policies from offline data.
problem Finding an approximate Nash equilibrium in offline Markov games with non-uniform coverage.
method Pessimistic Minimax Value Iteration (PMVI) constructs pessimistic value function estimates and solves NEs.
result Established a nearly minimax optimal result for offline Markov games with function approximation.
This paper improves GANs by ensuring local equilibria are also Nash equilibria, leading to better solutions.
problem Current GAN training methods often converge to local Nash equilibria, which may not be optimal.
method Formalizes GANs as finite games in mixed strategies, ensuring every local equilibrium is a Nash equilibrium.
result The proposed method converges to a resource-bounded Nash equilibrium, producing solutions closer to theoretical predictions.
Study Nash equilibrium between broker and trader in a lit exchange with price impact.
problem Optimizing trading strategies between informed and uninformed traders with broker's inventory penalties.
method Characterized Nash equilibrium through FBSDEs, solved explicitly.
result Explicit solution to trading strategies of broker and informed trader.
In this note, we present an existence result of a Nash equilibrium between electricity producers selling their production on an electricity market and buying CO2 emission allowances on an auction carbon market. The producers' strategies integrate the coupling of the two markets via the cost functions of the electricity…
Improved SEG method converges to Nash equilibrium in bilinear games.
problem Stochastic bilinear minimax optimization problem
method Stochastic ExtraGradient (SEG) method with constant step size, iteration averaging, and scheduled restarting.
result Provable convergence to Nash equilibrium under standard settings, optimal convergence rate in interpolation setting.
The paper analyzes RL in high-frequency market making with theoretical and practical implications.
problem Applying RL to high-frequency market making with theoretical rigor.
method Theoretical analysis bridging RL and financial economics, focusing on sampling frequency effects.
result An interesting tradeoff between error and complexity in RL algorithms as sampling frequency decreases.
Study Nash equilibrium in mean field portfolio games with random market parameters.
problem Modeling wealth and relative performance in competitive financial markets.
method Martingale optimality principle approach to characterize Nash equilibrium in mean field FBSDE.
result Unique Nash equilibrium found under weak interaction assumption and market parameters independence.
New method finds Nash equilibria faster in multiplayer games.
problem Finding Nash equilibria in multi-player games, especially in noisy environments.
method Extra-gradient with player sampling and variance reduction.
result Proves better convergence rate than full extra-gradient for noisy games.
Study analyzes market equilibrium returns with price impact and transaction costs.
problem Modeling equilibrium returns in markets with strategic order placement and transaction costs.
method Analyzes frictionless and transaction-cost markets, characterizes Nash equilibrium via FBSDEs.
result Equilibrium returns are affected by transaction costs, especially with noise traders.
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.
Study optimal stopping in non-exponential discounting, finding unique equilibrium.
problem Optimal stopping under non-exponential discounting.
method Iterative approach to find subgame perfect Nash equilibria.
result Existence and uniqueness of optimal equilibrium with higher value.
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.
PAPAL algorithm finds mixed Nash equilibria in continuous games.
problem Finding mixed Nash equilibria in non-convex, non-concave games.
method Particle-based Primal-Dual Algorithm (PAPAL) for weakly entropy-regularized min-max optimization.
result PAPAL offers non-asymptotic convergence guarantees for ε ε ε -mixed Nash equilibrium. Algorithm learns Nash equilibria in stochastic games using entropy-regularized policies.
problem Learning Nash equilibria in zero-sum stochastic games is computationally expensive.
method Entropy-regularized soft policies for Q-function updates.
result Algorithm converges to Nash equilibrium under certain conditions.
Policy gradient methods find Nash equilibrium in noisy games.
problem Finding Nash equilibrium in noisy games.
method Policy gradient methods with noise added.
result Policy gradient methods converge to Nash equilibrium in noisy games.
Paper optimizes multi-agent learning in Markov games with generative model.
problem Learning Nash or CCE equilibria in multi-agent Markov games.
method Develops \myalg~algorithm and adaptive sampling scheme using FTRL method.
result Minimax-optimal learning of CCE with minimal samples.
Paper models game theory for defending against data poisoning attacks.
problem Defending against data poisoning attacks using game theory.
method Modeling attacker-defender game, proving non-existence of pure Nash Equilibrium, proposing mixed strategy approach, and developing an algorithm to approximate Nash Equilibrium.
result Demonstrated effectiveness of mixed strategy defense in experiments.
Deep neural network solves large multi-agent games for Markovian Nash equilibrium.
problem Finding Markovian Nash equilibrium in large multi-agent stochastic differential games.
method Reformulate as decoupled decision problems, solve iteratively using deep BSDE method.
result Proposed algorithm accurately finds Nash equilibrium in large games.
RL in MFGs is as hard as solving many single-agent RL problems.
problem Learning Nash Equilibrium in Mean-Field Games (MFGs).
method Introduce P-MBED to measure model complexity, develop a novel exploration strategy, and establish polynomial sample complexity results.
result Learning Nash Equilibrium in MFGs is no more statistically challenging than solving a logarithmic number of single-agent RL problems.
Study shows how multiple traders can trade together without excessive price impact.
problem Coordination issues in trading to exploit a common signal.
method Closed-loop Nash competition model for stochastic differential games.
result Excessive trading reduced but not significantly for practical parameters.
Study Nash equilibrium between broker and informed trader in dealer and lit markets.
problem Nash equilibrium between broker and informed trader in dealer and lit markets with partial information.
method Convex analysis, FBSDEs, polynomial approximation.
result Existence and uniqueness of Nash equilibrium for short time horizons.
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. Novel approach to Nash equilibrium in mean-field stochastic games with operator resolvents.
problem Finding Nash equilibrium in mean-field stochastic games with mean-field interaction.
method Proposed a novel approach to derive Nash equilibrium semi-explicitly using operator resolvents and stochastic Fredholm equations.
result Equilibrium of the N N N -player game converges to mean-field equilibrium, and ε \varepsilon ε -Nash equilibrium derived as a by-product. New GAN formulation addresses mode collapse issue.
problem Mode collapse in GANs.
method Randomized decision rules, empirical Bayes, stochastic gradient MCMC.
result Proposed method converges to Nash equilibrium.
Investigates time-inconsistent portfolio selection under MMV preferences.
problem Time-inconsistent optimal strategies for MMV preferences.
method Nash equilibrium controls for MMV and MV preferences, solving FBSDE and HJB equations.
result MMV optimal strategies lead to higher investment amounts than MV strategies, narrowing over time.
Proves minimax sample complexity for turn-based stochastic games.
problem Proving theoretical guarantees for reinforcement learning in turn-based stochastic games.
method Developing absorbing TBSG and reward perturbation techniques to handle statistical dependence.
result Empirical Nash equilibrium strategy approximates true Nash equilibrium in turn-based stochastic games.
Transient market impact explained via Nash equilibrium in a game.
problem Understanding the transient nature of market impact.
method Analyzing a game between a trader and an arbitrageur, deriving decay kernels.
result Implied transient impact can be derived from trader behavior at Nash equilibrium.