Bounded Optimal Exploration in MDP

By Kenji Kawaguchi. 2016

15 citations recorded by the source corpus.

Within the framework of probably approximately correct Markov decision processes (PAC-MDP), much theoretical work has focused on methods to attain near optimality after a relatively long period of learning and exploration. However, practical concerns require the attainment of satisfactory behavior within a short period of time. In this paper, we relax the PAC-MDP conditions to reconcile theoretically driven exploration methods and practical needs. We propose simple algorithms for discrete and continuous state spaces, and illustrate the benefits of our proposed relaxation via theoretical analyses and numerical examples. Our algorithms also maintain anytime error bounds and average loss bounds. Our approach accommodates both Bayesian and non-Bayesian methods.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Chao Yu
2. Jiming Liu
3. Shamim Nemati
4. Leslie Pack Kaelbling
5. Yoshua Bengio
6. Kenji Kawaguchi
7. Guoqi Ren
8. Ruslan Salakhutdinov

In Management Science and Operations Research

1. Leslie Pack Kaelbling
2. Yoshua Bengio
3. Chao Yu
4. Jiming Liu
5. Shamim Nemati
6. Kenji Kawaguchi

Citations in the corpus

• Reinforcement Learning in Healthcare: A Survey (2019, background): “rning performance in HIV treatment. Pazis et al. [153] introduced an algorithm for PAC optimal exploration in continuous state spaces. Kawaguchi considered the time bound in a PAC exploration process [154]. Results in both studies showed that the exploration algorithm could achieve far better strate”
• Generalization in Deep Learning (2017, methodology): “…for each practical problem instance q ∈ Q , the size of the set Q that had been analyzed in theory for optimal exploration in Markov decision processes (MDPs) were demonstrated to be frequently too pessimistic, and a methodology to partially mitigate the issue was proposed (Kawaguchi, 2016b).”
• Incorporating causal factors into reinforcement learning for dynamic treatment regimes in HIV (2019, background): “This is a critical problem since HIV treatment has long been recognized as a well-known testbed for evaluating advanced exploration algorithms in RL research [18, 19].”