39 citations · 96 across the 15 of their papers we have counts for
17 papers
On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
Non-ergodic convergence of learning dynamics in games is widely studied recently because of its importance in both theory and practice. Recent work (Cai et al., 2024) showed that a…
Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games, both in theory and practice. Particularly popular algorithms include optimi…
Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret Matching (RM). Despite their widespread use for solving rea…
Context-lumpable stochastic bandits
Chung-Wei Lee, Qinghua Liu, Yasin Abbasi-Yadkori +3
We consider a contextual bandit problem with contexts and actions. In each round , the learner observes a random context and chooses an action based on its pas…
Regret Matching+: (In)Stability and Fast Convergence in Games
Gabriele Farina, Julien Grand-Clément, Christian Kroer +2
Regret Matching+ (RM+) and its variants are important algorithms for solving large-scale games. However, a theoretical understanding of their success in practice is still a mystery…
Clairvoyant Regret Minimization: Equivalence with Nemirovski's Conceptual Prox Method and Extension to General Convex Games
Gabriele Farina, Christian Kroer, Chung-Wei Lee +1
A recent paper by Piliouras et al. [2021, 2022] introduces an uncoupled learning algorithm for normal-form games -- called Clairvoyant MWU (CMWU). In this note we show that CMWU is…
Uncoupled Learning Dynamics with Swap Regret in Multiplayer Games
Ioannis Anagnostides, Gabriele Farina, Christian Kroer +3
In this paper we establish efficient and \emph{uncoupled} learning dynamics so that, when employed by all players in a general-sum multiplayer game, the \emph{swap regret} of each…
Kernelized Multiplicative Weights for 0/1-Polyhedral Games: Bridging the Gap Between Learning in Extensive-Form and Normal-Form Games
Gabriele Farina, Chung-Wei Lee, Haipeng Luo +1
While extensive-form games (EFGs) can be converted into normal-form games (NFGs), doing so comes at the cost of an exponential blowup of the strategy space. So, progress on NFGs an…
Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
Haipeng Luo, Chen-Yu Wei, Chung-Wei Lee
Policy optimization is a widely-used method in reinforcement learning. Due to its local-search nature, however, theoretical guarantees on global optimality often rely on extra assu…
Last-iterate Convergence in Extensive-Form Games
Chung-Wei Lee, Christian Kroer, Haipeng Luo
Regret-based algorithms are highly efficient at finding approximate Nash equilibria in sequential games such as poker games. However, most regret-based algorithms, including counte…
Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei +2
In this work, we develop linear bandit algorithms that automatically adapt to different environments. By plugging a novel loss estimator into the optimization problem that characte…
Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang +1
We study infinite-horizon discounted two-player zero-sum Markov games, and develop a decentralized algorithm that provably converges to the set of Nash equilibria under self-play.…
Linear Last-iterate Convergence in Constrained Saddle-point Optimization
Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang +1
Optimistic Gradient Descent Ascent (OGDA) and Optimistic Multiplicative Weights Update (OMWU) for saddle-point optimization have received growing attention due to their favorable l…
Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs
Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei +1
We develop a new approach to obtaining high probability regret bounds for online learning with bandit feedback against an adaptive adversary. While existing approaches all require…
A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
Chung-Wei Lee, Haipeng Luo, Mengxiao Zhang
We study small-loss bounds for adversarial multi-armed bandits with graph feedback, that is, adaptive regret bounds that depend on the loss of the best arm or related quantities, i…
A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
Yifang Chen, Chung-Wei Lee, Haipeng Luo +1
We propose the first contextual bandit algorithm that is parameter-free, efficient, and optimal in terms of dynamic regret. Specifically, our algorithm achieves dynamic regret $\ma…
Multi-Label Zero-Shot Learning with Structured Knowledge Graphs
Chung-Wei Lee, Wei Fang, Chih-Kuan Yeh +1
In this paper, we propose a novel deep learning architecture for multi-label zero-shot learning (ML-ZSL), which is able to predict multiple unseen class labels for each input insta…