This paper tackles global Nash equilibrium in non-convex multi-player games.
problem Challenges in finding global Nash equilibrium due to non-convexity.
method Conjugate transformation and variational inequality formulation to prove existence and design algorithms.
result Designs an ODE-based algorithm with exponential convergence rate and proves its effectiveness in practical scenarios.
Optimistic Thompson Sampling reduces regret in unknown multi-player games.
problem Navigating uncertainty in unknown multi-player games with strategic decision-making.
method Introduces Thompson Sampling algorithms that exploit opponents' actions and reward structures.
result Achieves over tenfold improvements in experimental budgets with logarithmic regret bound.
Gradient-based Nikaido-Isoda function helps find Nash equilibria efficiently.
problem Efficient computation of Nash equilibria in multi-player games.
method Gradient-based Nikaido-Isoda (GNI) function for computing first-order stationary points.
result Gradient descent converges sublinearly to a first-order stationary point of the GNI function.
The in-game economies of massively multi-player online games (MMOGs) are complex systems that have to be carefully designed and managed. This paper presents the results of an analysis of auction house data from the MMOG Glitch, across a 14 month time period, the entire lifetime of the game. The data comprise almost 3 m…
We consider a symmetric multi-players zero-sum game with two strategic variables. There are n n n players, n ≥ 3 n\geq 3 n ≥ 3 . Each player is denoted by i i i . Two strategic variables are t i t_i t i and s i s_i s i , i ∈ { 1 , … , n } i\in \{1, \dots, n\} i ∈ { 1 , … , n } . They are related by invertible functions. Using the minimax theorem by \cite{sion} we will show that Nas…
This paper shows how to learn variational inequalities fast with strong monotonicity.
problem Learning variational inequalities efficiently.
method Extending convex optimization techniques to variational inequalities with strong monotonicity.
result Fast generalization rates of Θ ( 1 / ε ) Θ(1/ε) Θ ( 1/ ε ) for learning variational inequalities. 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.
Cross-dimensional neural networks improve AI in Catan game.
problem Challenging to build AI agents for Catan game using RL.
method Introduced cross-dimensional neural networks to handle game complexities.
result RL agent outperforms best heuristic agent in Catan.
We introduce CSE for MLSF games and devise online learning algorithms for achieving no-external Stackelberg-regret.
problem Learning equilibrium in leader-follower games with noisy bandit feedback.
method Proposed Correlated Stackelberg Equilibrium (CSE) and online learning algorithms balancing exploration and exploitation.
result Achieves no-external Stackelberg-regret, converging to approximate CSE.
Game theory models how agents trade in a risky asset considering price impact and a common signal.
problem Modeling how financial agents liquidate assets in a risky market with price impact and a common signal.
method Formulated and solved a multi-player stochastic differential game and mean field game.
result Equilibrium strategies reveal how agents adjust the predictive trading signal to price impact.
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.
New learning dynamics adapt to corrupted games, improving performance in real-world scenarios.
problem Learning dynamics in games are limited to honest players, ignoring real-world corruption.
method Adaptive learning dynamics that adapt to player deviations from prescribed algorithms.
result Learning dynamics achieve better performance in corrupted games, matching honest regime bounds.
Motivated by the scarcity of accurate payoff feedback in practical applications of game theory, we examine a class of learning dynamics where players adjust their choices based on past payoff observations that are subject to noise and random disturbances. First, in the single-player case (corresponding to an agent tryi…
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.
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.
Algorithm solves online binary classification and infinite games using ERM oracle.
problem Online learning and solving infinite games with computationally inefficient oracles.
method Proposes an algorithm relying solely on ERM oracle calls for online binary classification and nonparametric games.
result Achieves finite and sublinearly growing regret in various settings.
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 proposes a mean-field gradient descent for zero-sum games, proving convergence to Nash equilibrium.
problem Finding mixed Nash equilibria in zero-sum games with multiple players.
method Mean-field gradient descent dynamics with time-averaging, incorporating exponentially discounted gradients.
result Exponential convergence rate to mixed Nash equilibrium with respect to total variation metric.
Models analyze strategic risk-taking in continuous action games.
problem Strategic risk-taking dynamics in continuous action games.
method Normal form game, multi-player scenarios, regret minimization algorithms, numerical algorithm for calculation.
result Nash equilibrium also serves as a correlated equilibrium in continuous games.
Extends trading framework to incorporate real-world constraints.
problem Trading strategies in multi-player non-cooperative games with constraints.
method Re-framed as quadratic programming problem, constraints readily incorporated.
result Two-trader equilibria calculated dynamically.
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.
New algorithm for multi-player bandits without needing lower bounds or scaling inversely.
problem Multi-player bandits without collision sensing information.
method Proposes a novel algorithm that circumvents two problems of existing algorithms.
result Proves a theoretical regret upper bound and shows superior performance in practice.
New algorithm for multi-player bandits in changing environments.
problem Sequential action selection with collisions and adversarial losses.
method First provable Multi-player Bandit algorithm for changing environments.
result Resolves open problem in adversarial multi-player settings.
Algorithm reduces regret in multi-player bandits with unknown collision rewards.
problem Reducing regret in multi-player multi-armed bandits with unknown collision rewards.
method Proposes an algorithm that combines a modified successive elimination strategy with a communication protocol to estimate suboptimality gaps and coordinate among players.
result Achieves logarithmic regret for the problem when collision reward is unknown.
ViZDoom competition tests AI in Doom using only visual input.
problem Creating AI bots that play Doom effectively from raw visual data.
method Multi-player deathmatch in Doom; bots make decisions based on screen buffer.
result Reinforcement learning can produce capable bots but not competitive against humans.
New algorithm reduces regret in multi-player bandits with collision information.
problem Optimizing decisions in multi-player bandits with collision penalties.
method Developed an algorithm with optimal T \sqrt{T} T regret under collision announcements, and sublinear regret without collision info. result First T \sqrt{T} T -type regret guarantee for non-stochastic multi-player multi-armed bandits with collision information. Study combines chit-chat and goal-oriented dialogue in fantasy games.
problem Combining naturalistic chit-chat with goal-oriented tasks in fantasy games.
method Trained a goal-oriented model with reinforcement learning against an imitation-learned chit-chat model using two approaches.
result Both models outperform a baseline and can converse naturally to achieve goals.
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.
We introduce a new type of graphical model called a "cumulative distribution network" (CDN), which expresses a joint cumulative distribution as a product of local functions. Each local function can be viewed as providing evidence about possible orderings, or rankings, of variables. Interestingly, we find that the condi…
New strategy achieves optimal regret without communication or collisions in multi-player bandit.
problem Cooperative multi-player stochastic multi-armed bandit with shared randomness.
method Combination of combinatorial approach to generalize geometric intuition.
result Achieves near-optimal regret i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) for any number of players and arms without collisions. 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.
New algorithm tackles multi-player bandit problems with limited access to arms.
problem Limited access to dynamic local subsets of arms in multi-player multi-armed bandit problems.
method Adopted Upper Confidence Bound (UCB) for exploration-exploitation and distributed optimization for collisions.
result Proposes a decentralized algorithm with near-optimal regret guarantee.
Proves exponential sample complexity separations in local differential privacy.
problem Sample complexity in locally private protocols.
method Connection between communication complexity and sample complexity, using specific lower bounds for two problems.
result Exponential separations between differentially private protocols.
A new algorithm reduces regret in multi-player bandits without collision info.
problem Decentralized multi-player multi-armed bandits with no collision info.
method EC-SIC algorithm using optimal error correction coding for reward statistics.
result Regret approaches that of centralized with collision info.
New algorithm outperforms existing ones in multi-player bandit problems without sensing.
problem Decentralized multi-player multi-armed bandit problem without collision or sensing info.
method Randomized Selfish KL-UCB, inspired by Selfish KL-UCB, with low complexity.
result Randomized Selfish KL-UCB outperforms state-of-the-art algorithms in almost all environments.
A new algorithm RESYNC for defenders against malicious attackers in multi-player bandits.
problem Malicious players colliding with cooperative players to prevent rewards.
method Decentralized and robust algorithm RESYNC for defenders.
result RESYNC algorithm is order-optimal, performing gracefully as the number of collisions increases.
A policy for near-optimal multi-player bandits with non-zero collision rewards.
problem Decentralized multi-player bandits with heterogeneous rewards and collisions.
method A policy achieving near-optimal regret in a non-communicative setting.
result Near order-optimal expected regret of O ( log 1 + δ T ) O(\log^{1 + δ} T) O ( log 1 + δ T ) for 0 < δ < 1 0 < δ< 1 0 < δ < 1 . New algorithms tackle adversarial multi-player bandits with forced-collision communication.
problem No-sensing adversarial multi-player multi-armed bandits (MP-MAB) problem.
method Adversary-Adaptive Collision-Communication (A2C2) algorithms, attackability-aware and unaware settings, information-theoretic tools, error-correction coding.
result Asymptotic attackability-dependent sublinear regret achieved, with or without knowing attackability.
Two new algorithms reduce group regret in abruptly changing multi-player bandit problems.
problem Reducing group regret in multi-player bandit problems in environments that change suddenly.
method Design of two novel algorithms: RR-SW-UCB# and SW-DLP.
result Expected cumulative group regret converges to zero over time.
New algorithm for multi-player bandits with collision-dependent rewards.
problem Stochastic multi-player multi-armed bandits with collision-dependent reward distributions.
method Error-Correction Collision Communication (EC3) algorithm.
result EC3 algorithm achieves optimal regret approaching centralized MP-MAB regret.
We consider a variant of the stochastic multi-armed bandit problem, where multiple players simultaneously choose from the same set of arms and may collide, receiving no reward. This setting has been motivated by problems arising in cognitive radio networks, and is especially challenging under the realistic assumption t…
First sample-efficient algorithm for learning EFCE in bandit feedback settings.
problem Learning EFCE in bandit feedback settings for IIEFGs.
method Proposed K K K -EFCE and uncoupled no-regret algorithm with wide-range regret minimization. result First sample-efficient algorithm for learning EFCE from bandit feedback.
Multi-player Multi-Armed Bandits (MAB) have been extensively studied in the literature, motivated by applications to Cognitive Radio systems. Driven by such applications as well, we motivate the introduction of several levels of feedback for multi-player MAB algorithms. Most existing work assume that sensing informatio…
New algorithm for multi-player bandits with selfish players, achieving logarithmic regret.
problem Challenges of robustness to selfish players in multi-player bandits.
method First algorithm robust to selfish players achieving logarithmic regret, with or without collision observation.
result Achieved logarithmic regret for robust algorithms to selfish players in multi-player bandits.
No communication allows optimal instance-dependent regret guarantees in multi-player bandits.
problem Achieving optimal instance-dependent regret in multi-player multi-armed bandits without communication.
method Characterization of Pareto optimal trade-offs and development of an algorithm.
result Achieving optimal instance-dependent regret requires strict sub-optimality in other regimes.
A multi-player bandit system resists adversarial attacks with near-optimal regret.
problem Adversaries attempt to manipulate rewards in a multi-player multi-armed bandit game.
method Players communicate a single bit to resist attacks, achieving near-optimal regret.
result Achieves near-optimal regret of O ( log 1 + δ T + W ) O(\log^{1+δ}T + W) O ( log 1 + δ T + W ) , where W W W is the total time of adversarial attacks. New NPG variants ensure parameter convergence in multi-agent learning.
problem Non-convergence of parameters in NPG for multi-agent learning.
method Proposed variants of NPG for multi-agent learning scenarios.
result Global last-iterate parameter convergence guarantees in various multi-agent learning settings.
New trekking approach reduces collisions in multi-player bandits.
problem Stochastic multi-armed bandits with many unknown players.
method Trekking approach to minimize collisions and regret.
result Guaranteed constant and sub-linear regret for static and dynamic scenarios.