106 citations · 996 across the 72 of their papers we have counts for
11 papers · 1 filter
Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP
Liyu Chen, Rahul Jain, Haipeng Luo
We introduce two new no-regret algorithms for the stochastic shortest path (SSP) problem with a linear MDP that significantly improve over the only existing results of (Vial et al.…
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…
Online Learning for Stochastic Shortest Path Model via Posterior Sampling
Mehdi Jafarnia-Jahromi, Liyu Chen, Rahul Jain +1
We consider the problem of online reinforcement learning for the Stochastic Shortest Path (SSP) problem modeled as an unknown MDP with an absorbing state. We propose PSRL-SSP, a si…
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…
Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms for Stochastic Shortest Path
Liyu Chen, Mehdi Jafarnia-Jahromi, Rahul Jain +1
We introduce a generic template for developing regret minimization algorithms in the Stochastic Shortest Path (SSP) model, which achieves minimax optimal regret as long as certain…
The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition
Tiancheng Jin, Longbo Huang, Haipeng Luo
We consider the best-of-both-worlds problem for learning an episodic Markov Decision Process through episodes, with the goal of achieving re…
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…
Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
Chen-Yu Wei, Haipeng Luo
We propose a black-box reduction that turns a certain reinforcement learning algorithm with optimal regret in a (near-)stationary environment into another algorithm with optimal dy…
Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
Liyu Chen, Haipeng Luo
We make significant progress toward the stochastic shortest path problem with adversarial costs and unknown transition. Specifically, we develop algorithms that achieve $\widetilde…
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.…
Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications
Liyu Chen, Haipeng Luo, Chen-Yu Wei
We resolve the long-standing "impossible tuning" issue for the classic expert problem and show that, it is in fact possible to achieve regret $O\left(\sqrt{(\ln d)\sum_t \ell_{t,i}…