On-device research index

arXiv research

A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.

168,742 papers · 148 categories

Trend · papers per month

count % of corpus

48 results for “Markov signaling game”

Information Design in Multi-Agent Reinforcement Learningcs.GT

This research tackles information design in multi-agent reinforcement learning.

problem Designing information to influence other adaptive agents in a non-stationary environment.

method Formulated Markov signaling game, introduced signaling gradient and extended obedience constraints.

result Developed efficient algorithm for mixed-motive tasks in multi-agent reinforcement learning.

multi-agent reinforcement learning information design Markov signaling game signaling gradient extended obedience constraints

2023-05-08abs ↗pdf ↗

Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcs.LG

New algorithms for RL in Markov games with independent linear function approximation, breaking the curse of multiagents.

problem Tackles the challenge of learning Markov equilibria in large state space Markov games with multiple agents.

method Proposes independent linear Markov games and designs new algorithms for learning Markov coarse correlated equilibria and Markov correlated equilibria with polynomial sample complexity.

result Breaks the curse of multiagents by achieving sample complexity bounds that scale polynomially with each agent's function class complexity.

reinforcement learning Markov games multiagent systems function approximation Markov equilibria

2023-02-07abs ↗pdf ↗

When is Offline Two-Player Zero-Sum Markov Game Solvable?cs.LG

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.

Markov games Nash equilibrium Offline reinforcement learning Pessimism algorithm Unilateral concentration

2022-01-10abs ↗pdf ↗

Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescs.LG

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.

policy optimization zero-sum games Markov games function approximation provably efficient

2021-02-17abs ↗pdf ↗

Regret Minimization and Convergence to Equilibria in General-sum Markov Gamescs.LG

Algorithm minimizes regret and converges to equilibria in Markov games.

problem Regret minimization and convergence to equilibria in general-sum Markov games under adversarial opponents.

method Decentralized algorithm that uses policy optimization and controls path length to achieve sublinear regret.

result Sublinear regret guarantees for convergence to correlated equilibrium in Markov games.

regret minimization Markov games convergence equilibria policy optimization

2022-07-28abs ↗pdf ↗

A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcs.LG

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.

Reinforcement Learning Model-based Algorithms Multi-Agent Systems Markov Games Optimization

2020-10-04abs ↗pdf ↗

Online Learning in Unknown Markov Gamescs.LG

Study online learning in unknown Markov games with sublinear regret.

problem Online learning in unknown Markov games with unobservable opponents.

method Introduced an algorithm achieving sublinear regret against the minimax value.

result First sublinear regret bound for unknown Markov games, independent of action spaces size.

online learning Markov games regret minimization multi-agent reinforcement learning unknown opponents

2020-10-28abs ↗pdf ↗

Achieving Logarithmic Regret in KL-Regularized Zero-Sum Markov Gamescs.LG

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

that scales inversely with KL regularization strength

β

reinforcement learning game theory KL regularization logarithmic regret Markov games

2025-10-15abs ↗pdf ↗

Stationary Markov Perfect Equilibria in Discounted Stochastic Gamesmath.OC

The existence of stationary Markov perfect equilibria in stochastic games is shown under a general condition called "(decomposable) coarser transition kernels". This result covers various earlier existence results on correlated equilibria, noisy stochastic games, stochastic games with finite actions and state-independe…

2013-11-07abs ↗pdf ↗

Representation Learning for General-sum Low-rank Markov Gamescs.LG

Algorithm finds ε-equilibrium policies for multi-agent Markov games with hidden low-rank structure.

problem Designing efficient algorithms for multi-agent Markov games with unknown representation and hidden low-rank structure.

method Model-based and model-free approaches using representation learning to construct an effective representation from data.

result Achieves poly

(H,d,A,1/\varepsilon)

sample complexity for both model-based and model-free approaches.

Markov Games Representation Learning Equilibrium Policies Deep Learning Function Approximation

2022-10-30abs ↗pdf ↗

Demand-Side Scheduling Based on Multi-Agent Deep Actor-Critic Learning for Smart Gridscs.LG

Smart grid uses deep learning to optimize household energy use.

problem Optimizing household energy use under real-time pricing schemes.

method Multi-agent deep actor-critic learning for decentralized agents with partial observability.

result Deep reinforcement learning reduces peak-to-average energy consumption and costs.

smart grid deep reinforcement learning energy management partial observability real-time pricing

2020-05-05abs ↗pdf ↗

Homogenization of Multi-agent Learning Dynamics in Finite-state Markov Gamesstat.ML

The paper simplifies multi-agent RL dynamics in finite-state Markov games using homogenization.

problem Approximating complex multi-agent reinforcement learning dynamics in finite-state Markov games.

method Rescaling learning process by reducing learning rate and increasing update frequency, proving convergence to an ODE.

result The rescaled process converges to an ODE that approximates the agent's learning dynamics.

multi-agent learning reinforcement learning finite-state Markov games homogenization rescaling

2025-06-26abs ↗pdf ↗

Towards General Function Approximation in Zero-Sum Markov Gamescs.GT

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.

Markov games zero-sum general function classes model-free model-based

2021-07-30abs ↗pdf ↗

Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcs.LG

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.

multi-agent reinforcement learning Markov games Nash equilibria coarse correlated equilibria generative model

2022-08-22abs ↗pdf ↗

Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cs.LG

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.

Reinforcement Learning Stackelberg-Nash Equilibrium Myopic Followers Markov Games Optimization

2021-12-27abs ↗pdf ↗

Trading with the Crowdq-fin.TR

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.

Game theory Financial markets Stochastic differential game Mean field game Price impact

2021-06-17abs ↗pdf ↗

Offline Learning in Markov Games with General Function Approximationcs.LG

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.

offline RL Markov games Nash equilibrium Coarse Correlated Equilibrium general function approximation

2023-02-06abs ↗pdf ↗

Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescs.LG

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

ilde{O}(dH\sqrt{T})

regret bound, matching lower bound up to logarithmic factors.

reinforcement learning Markov games Nash Equilibrium UCRL Coarse Correlated Equilibrium

2021-02-15abs ↗pdf ↗

Model-Based Reinforcement Learning for Offline Zero-Sum Markov Gamescs.LG

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

\frac{C_{\mathsf{clipped}}^\star S(A+B)}{(1-γ)^3 \varepsilon^2}

, achieving minimax optimality.

reinforcement learning Markov games Nash equilibrium model-based offline data

2022-06-08abs ↗pdf ↗

Gap-Dependent Bounds for Two-Player Markov Gamescs.LG

The paper analyzes Q-learning in 2-player Markov games and provides gap-dependent logarithmic regret bounds.

problem Analyzing the cumulative regret of Nash Q-learning in 2-player turn-based stochastic Markov games.

method Proposed gap-dependent logarithmic upper bounds for cumulative regret in episodic tabular setting and discounted game setting.

result The proposed bounds match theoretical lower bounds up to a logarithmic term.

Q-learning Markov Games Cumulative Regret Nash Q-learning Logarithmic Bounds

2021-07-01abs ↗pdf ↗

Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescs.LG

New research shows no-regret learning is impossible in Markov games under certain assumptions.

problem Achieving no-regret learning in decentralized Markov games.

method Novel application of aggregation techniques from online learning to prove lower bounds.

result No polynomial-time algorithm exists for independent no-regret learning in general-sum Markov games.

Markov Games No-Regret Learning Sparse Correlated Equilibrium PPAD-hard Problems Aggregation Techniques

2023-03-22abs ↗pdf ↗

A Mean Field Game between Informed Traders and a Brokerq-fin.TR

Solves a game between brokers and informed traders using stochastic differential equations.

problem Optimizing wealth in a game between brokers and informed traders with private signals.

method Closed-form solutions to a mean-field game using forward-backward SDEs.

result Optimal trading strategies for both brokers and informed traders are found.

Mean field game Informed traders Broker Stochastic differential equations Nash equilibrium

2024-01-10abs ↗pdf ↗

Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcs.LG

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

ilde O(\sqrt{d^3 H^3 T})

on duality gap and regret.

reinforcement learning Markov games simultaneous moves optimism value iteration

2020-02-17abs ↗pdf ↗

Predicting Student Performance in an Educational Game Using a Hidden Markov Modelstat.ML

Contributions: Prior studies on education have mostly followed the model of the cross sectional study, namely, examining the pretest and the posttest scores. This paper shows that students' knowledge throughout the intervention can be estimated by time series analysis using a hidden Markov model. Background: Analyzing …

2019-04-24abs ↗pdf ↗

Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscs.LG

This work tackles learning Markov games with adversarial opponents and achieves both average reward and exploitation.

problem Achieving both average reward and exploiting adaptive opponents in Markov games.

method Develops efficient algorithms and proves hardness results for learning Markov games with adversarial opponents.

result Achieves

\sqrt{K}

-regret bounds for certain conditions on opponent policies, complemented by an exponential lower bound.

Markov games Adversarial opponents No-regret learning Regret bounds Hardness results

2022-03-14abs ↗pdf ↗

Bilevel Optimization over Saddle Points of Zero-Sum Markov Gamescs.LG

A new method solves bilevel optimization problems in competitive Markov games.

problem Capturing competitive structures in RL with multiple interacting policies.

method Penalty-augmented Nikaido-Isoda descent-ascent (PANDA) method.

result PANDA converges to stationary points without convexity assumptions.

bilevel optimization Markov games reinforcement learning penalty methods first-order policy-gradient

2026-05-26abs ↗pdf ↗

Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithmscs.LG

Study on learning strategies in adaptive Markov games with policy regret as metric.

problem Learning in dynamic Markov games with adaptive opponents is challenging.

method Introduced policy regret as a new learning metric and developed algorithms for consistent adaptive adversaries.

result Achieved

\sqrt{T}

policy regret against certain adaptive adversaries.

Markov games policy regret adaptive adversaries statistical hardness consistent adversaries

2024-11-01abs ↗pdf ↗

Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibriumcs.LG

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(\sqrt{T})

regret with polynomial complexity, under mild assumptions.

Markov Games Nash Equilibrium Function Approximation Reproducing Kernel Hilbert Space Online Learning

2022-08-10abs ↗pdf ↗

Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescs.LG

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.

Markov Games Model-Free Algorithms Zero-Sum Sample Efficiency Variance Reduction

2023-08-17abs ↗pdf ↗

When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cs.LG

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.

multi-agent reinforcement learning Markov games sample efficiency Coarse Correlated Equilibrium Correlated Equilibrium

2021-10-08abs ↗pdf ↗

Game Design for Eliciting Distinguishable Behaviorcs.LG

New game design method for better trait inference.

problem Inferring latent psychological traits from human behavior.

method Formulated as a mutual information maximization problem, solved using variational lower bound optimization.

result Designed games successfully distinguish among players with different traits, outperforming traditional methods.

trait inference behavioral games mutual information variational lower bound Markov Decision Processes

2019-12-12abs ↗pdf ↗

Hodge theoretic reward allocation for generalized cooperative games on graphsmath.PR

The paper extends game theory using Hodge theory on graphs.

problem Generalizing Shapley's value allocation formula for cooperative games on graphs.

method Connecting stochastic path integrals to Hodge-theoretic Poisson's equations on graphs.

result The value allocation operator is the solution to Poisson's equation in combinatorial Hodge theory.

Hodge theory cooperative games Markov chains graph theory value allocation

2021-07-22abs ↗pdf ↗

Multi-Agent Generative Adversarial Imitation Learningcs.LG

Imitation learning algorithms can be used to learn a policy from expert demonstrations without access to a reward signal. However, most existing approaches are not applicable in multi-agent settings due to the existence of multiple (Nash) equilibria and non-stationary environments. We propose a new framework for multi-…

2018-07-26abs ↗pdf ↗

Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescs.LG

This paper tackles sample-efficient reinforcement learning for partially observable Markov games.

problem Learning in partially observable Markov games with incomplete information.

method A simple algorithm combining optimism and Maximum Likelihood Estimation (MLE) for self-play, and a variant of optimistic MLE for adversarial opponents.

result The proposed algorithms achieve approximate Nash, correlated, and coarse correlated equilibria in polynomial samples for weakly revealing POMGs.

Reinforcement Learning Markov Games Partial Observability Optimism Maximum Likelihood Estimation

2022-06-02abs ↗pdf ↗

Minimax-Optimal Policy Regret in Partially Observable Markov Gamescs.LG

Study optimal policy regret in partially observable Markov games with adaptive opponents.

problem Optimal sequential decision-making in partially observable environments against strategic, adaptive opponents.

method An epoch-based optimistic maximum-likelihood algorithm that selects one policy per epoch using confidence sets built cumulatively from past data.

result Achieves

ilde{O}(\sqrt{T})

policy regret for fixed problem parameters, with explicit dependence on horizon, adversary memory, confidence radius, and aggregate Eluder dimension.

Markov Games Sequential Decision Making Adversarial Learning Optimistic Algorithms Partial Observability

2026-06-01abs ↗pdf ↗

Explaining Cost Overruns of Large-Scale Transportation Infrastructure Projects using a Signalling Gameq-fin.GN

Strategic behaviour is one of the main explanations for cost overruns. It can theoretically be supported by agency theory, in which strategic behaviour is the result of asymmetric information between the principal and agent. This paper gives a formal account of this relation by a signalling game. This is a game with in…

2013-07-08abs ↗pdf ↗

Mesoscopic approach to minority games in herd regimenlin.AO

We study minority games in efficient regime. By incorporating the utility function and aggregating agents with similar strategies we develop an effective mesoscale notion of state of the game. Using this approach, the game can be represented as a Markov process with substantially reduced number of states with explicitl…

2011-11-29abs ↗pdf ↗

PCGRL: Procedural Content Generation via Reinforcement Learningcs.LG

Reinforcement learning improves game level design.

problem Creating high-quality game levels with limited examples.

method Transforming level design into a Markov decision process and training with reinforcement learning.

result Trained reinforcement learning agents can generate high-quality levels quickly.

reinforcement learning game development procedural content generation level design Markov decision process

2020-01-24abs ↗pdf ↗

Competitive Policy Optimizationcs.LG

Proposes CoPO, a new policy optimization method for competitive games.

problem Designing efficient optimization methods for competitive Markov decision processes.

method Competitive policy optimization (CoPO) approach that exploits game-theoretic nature of competitive games.

result Stable optimization, convergence to sophisticated strategies, and higher scores compared to baseline methods.

policy optimization competitive games policy gradient game-theoretic Markov decision processes

2020-06-18abs ↗pdf ↗

Trade execution games in a Markovian environmentq-fin.TR

The paper analyzes trade execution strategies for large traders in a stochastic market environment.

problem Analyzing trade execution strategies in a stochastic market with price impact.

method Formulated a Markov game model and used backward induction method of dynamic programming.

result Explicit closed-form execution strategy at Markov perfect equilibrium.

trade execution Markov game stochastic market price impact dynamic programming

2024-05-12abs ↗pdf ↗

Learning in Congestion Games with Bandit Feedbackcs.GT

The paper tackles Nash-regret minimization in congestion games with bandit feedback.

problem Minimizing Nash-regret in congestion games with bandit feedback.

method Proposes centralized and decentralized algorithms for congestion games with bandit feedback, and a centralized algorithm for Markov congestion games.

result Sample complexity depends polynomially on the number of players and facilities, not the size of the action set.

Nash-regret Congestion games Bandit feedback Optimism in the face of uncertainty Frank-Wolfe method

2022-06-04abs ↗pdf ↗

Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescs.LG

Algorithm converges to Nash equilibria in competitive games.

problem Finding Nash equilibria in decentralized, competitive Markov games.

method Decentralized Optimistic Gradient Descent/Ascent with a critic.

result Converges to the set of Nash equilibria under self-play.

Markov games Nash equilibria Decentralized algorithms Optimistic Gradient Descent Ascent

2021-02-08abs ↗pdf ↗

Avoiding hashing and encouraging visual semantics in referential emergent language gamescs.LG

There has been an increasing interest in the area of emergent communication between agents which learn to play referential signalling games with realistic images. In this work, we consider the signalling game setting of Havrylov and Titov and investigate the effect of the feature extractor's weights and of the task bei…

2019-11-13abs ↗pdf ↗

Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescs.LG

DORIS algorithm achieves no-regret learning in Markov games with adversarial opponents.

problem Decentralized policy learning in Markov games with nonstationary opponents.

method DORIS algorithm using optimistic hyperpolicy mirror descent.

result Achieves

\sqrt{K}

-regret in general function approximation.

Decentralized learning Markov games No-regret Optimistic hyperpolicy Mirror descent

2022-06-03abs ↗pdf ↗

Decoding Rewards in Competitive Games: Inverse Game Theory with Entropy Regularizationcs.LG

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.

Inverse reinforcement learning Game theory Zero-sum games Entropy regularization Quantal response equilibrium

2026-01-19abs ↗pdf ↗

Disentangling Controllable Object through Video Prediction Improves Visual Reinforcement Learningcs.LG

A framework disentangles controllable objects from visual signals for improved RL.

problem Improving sample efficiency and game performance in vision-based RL.

method Action-conditioned video prediction to disentangle controllable objects.

result Improved sample efficiency and game performance in Atari games.

vision-based reinforcement learning video prediction disentanglement sample efficiency game performance

2020-02-21abs ↗pdf ↗

Near-Optimal Reinforcement Learning with Self-Playcs.LG

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(SAB)

for Nash Q-learning and

O(S(A+B))

for Nash V-learning, closing the gap with lower bounds.

reinforcement learning self-play Nash equilibrium optimistic algorithms sample complexity

2020-06-22abs ↗pdf ↗

Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcs.LG

New MARL algorithms resolve the curse of multiagency with function approximation.

problem Challenges in Multi-Agent Reinforcement Learning (MARL) due to the curse of multiagency.

method V-Learning with Policy Replay and Decentralized Optimistic Policy Mirror Descent.

result First polynomial sample complexity results for learning approximate Coarse Correlated Equilibria (CCEs) of Markov Games under decentralized linear function approximation.

Multi-Agent Reinforcement Learning Decentralized Learning Function Approximation Coarse Correlated Equilibria Markov Games

2023-02-13abs ↗pdf ↗