Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning

2020-03-15 · NeurIPS 2020 12 · Fei Feng, Ruosong Wang, Wotao Yin, Simon S. Du, Lin F. Yang

Motivated by the prevailing paradigm of using unsupervised learning for efficient exploration in reinforcement learning (RL) problems [tang2017exploration,bellemare2016unifying], we investigate when this paradigm is provably efficient. We study episodic Markov decision processes with rich observations generated from a small number of latent states. We present a general algorithmic framework that is built upon two components: an unsupervised learning algorithm and a no-regret tabular RL algorithm. Theoretically, we prove that as long as the unsupervised learning algorithm enjoys a polynomial sample complexity guarantee, we can find a near-optimal policy with sample complexity polynomial in the number of latent states, which is significantly smaller than the number of observations. Empirically, we instantiate our framework on a class of hard exploration problems to demonstrate the practicality of our theory.

📄 PDF Abstract BibTeX arXiv:2003.06898

Code (1)

FlorenceFeng/StateDecoding 공식 구현 pytorch

Tasks

Efficient Explorationreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Provably Safe PAC-MDP Exploration Using Analogies

2020-07-07 · Melrose Roderick, Vaishnavh Nagarajan, J. Zico Kolter

A key challenge in applying reinforcement learning to safety-critical domains is understanding how to balance exploration (needed to attain good performance on the task) with safety (needed to avoid catastrophic failure)…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Safe Exploration

Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning

2019-11-13 · ICML 2020 1 · Dipendra Misra, Mikael Henaff, Akshay Krishnamurthy, John Langford

We present an algorithm, HOMER, for exploration and reinforcement learning in rich observation environments that are summarizable by an unknown latent state space. The algorithm interleaves representation learning to ide…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Representation Learning

Neurosymbolic Reinforcement Learning with Formally Verified Exploration

2020-09-26 · NeurIPS 2020 12 · Greg Anderson, Abhinav Verma, Isil Dillig, Swarat Chaudhuri

We present Revel, a partially neural reinforcement learning (RL) framework for provably safe exploration in continuous state and action spaces. A key challenge for provably safe deep RL is that repeatedly verifying neura…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Safe Exploration

Provably Efficient Exploration in Policy Optimization

2019-12-12 · ICML 2020 1 · Qi Cai, Zhuoran Yang, Chi Jin, Zhaoran Wang

While policy-based reinforcement learning (RL) achieves tremendous successes in practice, it is significantly less understood in theory, especially compared with value-based RL. In particular, it remains elusive how to d…

Efficient Exploration Reinforcement Learning Reinforcement Learning (RL)

Contextual Decision Processes with Low Bellman Rank are PAC-Learnable

2016-10-29 · ICML 2017 8 · Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford 외

This paper studies systematic exploration for reinforcement learning with rich observations and function approximation. We introduce a new model called contextual decision processes, that unifies and generalizes most pri…

Efficient Exploration reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)