6 papers
Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret
Shinji Ito, Haipeng Luo, Arnab Maiti +2
Learning to play zero-sum games is a fundamental problem in game theory and machine learning. While significant progress has been made in minimizing external regret in the self-pla…
Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
Shinji Ito, Kevin Jamieson, Haipeng Luo +2
We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model, where the learner observes only the cumu…
Tight Regret Upper and Lower Bounds for Optimistic Hedge in Two-Player Zero-Sum Games
Taira Tsuchiya
In two-player zero-sum games, the learning dynamic based on optimistic Hedge achieves one of the best-known regret upper bounds among strongly-uncoupled learning dynamics. With an…
Reinforcement Learning from Adversarial Preferences in Tabular MDPs
Taira Tsuchiya, Shinji Ito, Haipeng Luo
We introduce a new framework of episodic tabular Markov decision processes (MDPs) with adversarial preferences, which we refer to as preference-based MDPs (PbMDPs). Unlike standard…
Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback
Shinji Ito, Haipeng Luo, Taira Tsuchiya +1
No-regret self-play learning dynamics have become one of the premier ways to solve large-scale games in practice. Accelerating their convergence via improving the regret of the pla…
Corrupted Learning Dynamics in Games
Taira Tsuchiya, Shinji Ito, Haipeng Luo
Learning in games refers to scenarios where multiple players interact in a shared environment, each aiming to minimize their regret. An equilibrium can be computed at a fast rate o…