Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

2019/06/12 by Zihan Zhang, Xiangyang Ji, Zhang, Zihan +1 · 9 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1906.05110

openalex publication_date 2019/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an algorithm based on the Optimism in the Face of Uncertainty (OFU) principle which is able to learn Reinforcement Learning (RL) modeled by Markov decision process (MDP) with finite state-action space efficiently. By evaluating the state-pair difference of the optimal bias function h^*, the proposed algorithm achieves a regret bound of O(√(SAHT))\footnoteThe symbol O means O with log factors ignored. for MDP with S states and A actions, in the case that an upper bound H on the span of h^*, i.e., sp(h^*) is known. This result outperforms the best previous regret bounds O(S√(AHT)) \citepfruit2019improved by a factor of √(S). Furthermore, this regret bound matches the lower bound of Ω(√(SAHT)) \citepjaksch2010near up to a logarithmic factor. As a consequence, we show that there is a near optimal regret bound of O(√(SADT)) for MDPs with a finite diameter D compared to the lower bound of Ω(√(SADT)) \citepjaksch2010near.

Cited by

• Finite-Time Bounds for Average-Reward Fitted Q-Iteration
• Improved Exploration in Factored Average-Reward MDPs
• Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal\n Algorithm Escaping the Curse of Horizon
• Tightening Exploration in Upper Confidence Reinforcement Learning
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation
• Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes
• Causal Markov Decision Processes: Learning Good Interventions Efficiently

Related

• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes
• Minimax Regret Bounds for Reinforcement Learning
• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs
• Posterior sampling for reinforcement learning: worst-case regret bounds