← Back to papers
2016 NIPS NeurIPS 2016

Improving PAC Exploration Using the Median Of Means

Abstract

We present the first application of the median of means in a PAC exploration algorithm for MDPs. Using the median of means allows us to significantly reduce the dependence of our bounds on the range of values that the value function can take, while introducing a dependence on the (potentially much smaller) variance of the Bellman operator. Additionally, our algorithm is the first algorithm with PAC bounds that can be applied to MDPs with unbounded rewards.

🌉 Interdisciplinary Bridge — Machine Learning and Reinforcement Learning
📈 Trend Setter — Exploration-Exploitation
🧭 Keyword Pioneer — median of mean
🐣 Hot Topic Early Bird — reinforcement learning
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio

Authors

Jason Pazis , Ronald E Parr , Jonathan P How

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Stochastic Processes Reinforcement Learning > Methods > Deep RL Machine Learning > Learning Types > Reinforcement Learning Machine Learning > Learning Types > Exploration-Exploitation

Keywords

reinforcement learning markov decision process value function bellman operator median of mean pac exploration unbounded reward
Download PDF

Related papers

Bayesian Intermittent Demand Forecasting for Large Inventories 2016
Dynamic Network Surgery for Efficient DNNs 2016
Beyond Exchangeability: The Chinese Voting Process 2016
Safe and Efficient Off-Policy Reinforcement Learning 2016
Tagger: Deep Unsupervised Perceptual Grouping 2016