Online Regret Bounds for Undiscounted Continuous Reinforcement Learning

Abstract

We derive sublinear regret bounds for undiscounted reinforcement learning in continuous state space. The proposed algorithm combines state aggregation with the use of upper confidence bounds for implementing optimism in the face of uncertainty. Beside the existence of an optimal policy which satisfies the Poisson equation, the only assumptions made are Holder continuity of rewards and transition probabilities.

References in corpus (3)

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Regret Bounds for Restless Markov Bandits
• Optimal Regret Bounds for Selecting the State Representation in Reinforcement Learning

Cited by in corpus (22)

• Generalization and Exploration via Randomized Value Functions
• Model-based Reinforcement Learning and the Eluder Dimension
• Online Stochastic Optimization under Correlated Bandit Feedback
• Optimal Regret Bounds for Selecting the State Representation in Reinforcement Learning
• Efficient Model-free Reinforcement Learning in Metric Spaces
• Cover Tree Bayesian Reinforcement Learning
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration
• From self-tuning regulators to reinforcement learning and back again
• Learning to Control in Metric Space with Optimal Regret
• Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces
• Regime Switching Bandits
• A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
• Off-Policy Estimation of Long-Term Average Outcomes with Applications to Mobile Health
• Rebounding Bandits for Modeling Satiation Effects
• A Survey of Exploration Methods in Reinforcement Learning
• Provably adaptive reinforcement learning in metric spaces
• Online Learning in Kernelized Markov Decision Processes
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis
• Fundamental Limits of Reinforcement Learning in Environment with Endogeneous and Exogeneous Uncertainty
• Screening for an Infectious Disease as a Problem in Stochastic Control
• Success Probability of Exploration: a Concrete Analysis of Learning Efficiency
• Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalization