conftrace_

2016 NeurIPS 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 - Artificial Intelligence and Reinforcement Learning

🐣 Hot Topic Early Bird - markov decision process

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 sample complexity markov decision process value function bellman operator median of mean pac exploration unbounded reward

More from NeurIPS 2016

All NeurIPS 2016 papers →

Supervised Word Mover's Distance

Fast and accurate spike sorting of high-channel count probes with KiloSort

Learning brain regions via large-scale online structured sparse dictionary learning

Active Nearest-Neighbor Learning in Metric Spaces

Learning from Small Sample Sets by Combining Unsupervised Meta-Training with CNNs

Learning Bayesian networks with ancestral constraints