Variance-aware Regret Bounds For Undiscounted Reinforcement Learning In Mdps

Abstract

The problem of reinforcement learning in an unknown and discrete Markov Decision Process (MDP) under the average-reward criterion is considered, when the learner interacts with the system in a single stream of observations, starting from an initial state without any reset. We revisit the minimax lower bound for that problem by making appear the local variance of the bias function in place of the diameter of the MDP. Furthermore, we provide a novel analysis of the KL-UCRL algorithm establishing a high-probability regret bound scaling as \(\widetilde \{\mathcal O\}\Bigl(\{\textstyle \sqrt\{S\sum_\{s,a\}\{\bf V\}^\star_\{s,a\}T\}\}\Big)\) for this algorithm for ergodic MDPs, where \(S\) denotes the number of states and where \(\{\bf V\}^\star_\{s,a\}\) is the variance of the bias function with respect to the next-state distribution following action \(a\) in state \(s\). The resulting bound improves upon the best previously known regret bound \(\widetilde \{\mathcal O\}(DS\sqrt\{AT\})\) fo

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keytalebi2018variance

Related papers

• Regret Bounds For Discounted Mdps (2020)0.00
• Sharp Variance-dependent Bounds In Reinforcement Learning: Best Of Both Worlds In Stochastic And Deterministic Environments (2023)0.00
• Value-biased Maximum Likelihood Estimation For Model-based Reinforcement Learning In Discounted Linear Mdps (2023)0.00
• Logarithmic Regret Bounds For Continuous-time Average-reward Markov Decision Processes (2022)5.24
• Regret Minimization For Reinforcement Learning By Evaluating The Optimal Bias Function (2019)0.00
• Near-optimal Optimistic Reinforcement Learning Using Empirical Bernstein Inequalities (2019)0.00
• Reinforcement Learning For Infinite-horizon Average-reward Linear Mdps Via Approximation By Discounted-reward Mdps (2024)0.00
• Regret Analysis In Deterministic Reinforcement Learning (2021)0.00