Online Regret Bounds for Undiscounted Continuous Reinforcement Learning

Ronald Ortner; Daniil Ryabko

2012 NIPS NeurIPS 2012

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 Hoelder continuity of rewards and transition probabilities.

🌉 Interdisciplinary Bridge — Machine Learning and Reinforcement Learning

🧭 Keyword Pioneer — continuous reinforcement learning

🐝 Cross-Pollinator — Artificial Intelligence, Data Science & Analytics, Deep Learning, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Reinforcement Learning, Robotics, Security & Privacy

🐣 Hot Topic Early Bird — reinforcement learning

Authors

Ronald Ortner , Daniil Ryabko

Topics

Machine Learning > Optimization & Theory > Learning Theory Reinforcement Learning > Methods Reinforcement Learning > Methods > Deep RL Reinforcement Learning > Methods > Policy Learning Machine Learning > Learning Types > Online Learning Machine Learning > Learning Types > Reinforcement Learning Machine Learning > Optimization & Theory > Online Algorithms

Keywords

reinforcement learning online learning optimal policy continuous state space continuous reinforcement learning optimism state aggregation upper confidence bound regret bound undiscounted rl

Download PDF

Related papers

Kernel Hyperalignment 2012

Fused sparsity and robust estimation for linear models with unknown variance 2012

Slice sampling normalized kernel-weighted completely random measure mixture models 2012

Scaling MPE Inference for Constrained Continuous Markov Random Fields with Consensus Optimization 2012

Matrix reconstruction with the local max norm 2012