2018

Efficient Exploration through Bayesian Deep Q-Networks

Azizzadenesheli, Kamyar, Anandkumar, Animashree

Understand

We study reinforcement learning (RL) in high dimensional episodic Markov decision processes (MDP).

We consider value-based RL when the optimal Q-value is a linear function of d-dimensional state-action feature representation.
For instance, in deep-Q networks (DQN), the Q-value is a linear function of the feature representation layer (output layer).
We propose two algorithms, one based on optimism, LINUCB, and another based on posterior sampling, LINPSRL.

Built on

Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws
de la Pena, V. H., Klass, M. J., and Lai, T. L. (2004) · 1933
Earlier work this paper cites.
On the likelihood that one unknown probability exceeds another in view of the evidence of two samples
Thompson, W. R. (1933) · 1933
Earlier work this paper cites.
Generalized polynomial approximations in markovian decision processes
Schweitzer, P. J. and Seidmann, A. (1985) · 1985
Earlier work this paper cites.
Temporal difference learning and td-gammon
Tesauro, G. (1995) · 1995
Earlier work this paper cites.
Bayesian q-learning
Dearden, R., Friedman, N., and Russell, S. (1998) · 1998
Earlier work this paper cites.
A bayesian framework for reinforcement learning
Strens, M. (2000) · 2000
Earlier work this paper cites.
Near-optimal reinforcement learning in polynomial time
Kearns, M. and Singh, S. (2002) · 2002
Earlier work this paper cites.
Using confidence bounds for exploitation-exploration trade-offs
Auer, P. (2003) · 2003
Earlier work this paper cites.
R-max-a general polynomial time algorithm for near-optimal reinforcement learning
Brafman, R. I. and Tennenholtz, M. (2003) · 2003
Earlier work this paper cites.
Bayes meets bellman: The gaussian process approach to temporal difference learning
Engel, Y., Mannor, S., and Meir, R. (2003) · 2003
Earlier work this paper cites.
Exploration in metric state spaces
Kakade, S., Kearns, M. J., and Langford, J. (2003) · 2003
Earlier work this paper cites.
Least-squares policy iteration
Lagoudakis, M. G. and Parr, R. (2003) · 2003
Earlier work this paper cites.
Gaussian processes for machine learning
Rasmussen, C. E. and Williams, C. K. (2006) · 2006
Earlier work this paper cites.
Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path
Antos, A., Szepesvári, C., and Munos, R. (2008) · 2008
Earlier work this paper cites.
Stochastic linear optimization under bandit feedback
Dani, V., Hayes, T. P., and Kakade, S. M. (2008) · 2008
Earlier work this paper cites.
A bayesian sampling approach to exploration in reinforcement learning
Asmuth, J., Li, L., Littman, M. L., Nouri, A., and Wingate, D. (2009) · 2009
Earlier work this paper cites.
Self-normalized processes: Limit theory and Statistical Applications
Peña, V. H., Lai, T. L., and Shao, Q.-M. (2009) · 2009
Earlier work this paper cites.
Near-optimal regret bounds for reinforcement learning
Jaksch, T., Ortner, R., and Auer, P. (2010) · 2010
Earlier work this paper cites.
Finite-sample analysis of lstd
Lazaric, A., Ghavamzadeh, M., and Munos, R. (2010) · 2010
Earlier work this paper cites.

Similar

A contextual-bandit approach to personalized news article recommendation
Li, L., Chu, W., Langford, J., and Schapire, R. E. (2010) · 2010
Cited alongside, same era.
Linearly parameterized bandits
Rusmevichientong, P. and Tsitsiklis, J. N. (2010) · 2010
Cited alongside, same era.
Improved algorithms for linear stochastic bandits
Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011) · 2011
Cited alongside, same era.
Regret bounds for the adaptive control of linear quadratic systems
Abbasi-Yadkori, Y. and Szepesvári, C. (2011) · 2011
Cited alongside, same era.
An empirical evaluation of thompson sampling
Chapelle, O. and Li, L. (2011) · 2011
Cited alongside, same era.
Contextual bandits with linear payoff functions
Chu, W., Li, L., Reyzin, L., and Schapire, R. (2011) · 2011
Cited alongside, same era.
Analysis of thompson sampling for the multi-armed bandit problem
Agrawal, S. and Goyal, N. (2012) · 2012
Cited alongside, same era.
Random design analysis of ridge regression
Hsu, D., Kakade, S. M., and Zhang, T. (2012) · 2012
Cited alongside, same era.
Online regret bounds for undiscounted continuous reinforcement learning
Ortner, R. and Ryabko, D. (2012) · 2012
Cited alongside, same era.
Thompson sampling for contextual bandits with linear payoffs
Agrawal, S. and Goyal, N. (2013) · 2013
Cited alongside, same era.
The arcade learning environment: An evaluation platform for general agents
Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M. (2013) · 2013
Cited alongside, same era.
(more) efficient reinforcement learning via posterior sampling
Osband, I., Russo, D., and Van Roy, B. (2013) · 2013
Cited alongside, same era.

Then

Bayesian reinforcement learning: A survey
Ghavamzadeh, M., Mannor, S., Pineau, J., Tamar, A., et al. (2015) · 2015
Later among the works it cites.
Human-level control through deep reinforcement learning
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015) · 2015
Later among the works it cites.
Exploratory gradient boosting for reinforcement learning in complex domains
Abel, D., Agarwal, A., Diaz, F., Krishnamurthy, A., and Schapire, R. E. (2016) · 2016
Later among the works it cites.
Unifying count-based exploration and intrinsic motivation
Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. (2016) · 2016
Later among the works it cites.
Openai gym
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016) · 2016
Later among the works it cites.
Dropout as a bayesian approximation: Representing model uncertainty in deep learning
Gal, Y. and Ghahramani, Z. (2016) · 2016
Later among the works it cites.
Contextual decision processes with low bellman rank are pac-learnable
Jiang, N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. (2016) · 2016
Later among the works it cites.
End-to-end training of deep visuomotor policies
Levine et al., S. (2016) · 2016
Later among the works it cites.
Deep exploration via bootstrapped dqn
Osband, I., Blundell, C., Pritzel, A., and Van Roy, B. (2016) · 2016
Later among the works it cites.
Safe, multi-agent, reinforcement learning for autonomous driving
Shalev-Shwartz, S., Shammah, S., and Shashua, A. (2016) · 2016
Later among the works it cites.
Deep reinforcement learning with double q-learning
Van Hasselt, H., Guez, A., and Silver, D. (2016) · 2016
Later among the works it cites.
Linear thompson sampling revisited
Abeille, M. and Lazaric, A. (2017) · 2017
Later among the works it cites.
Noisy networks for exploration
Fortunato, M., Azar, M. G., Piot, B., Menick, J., Osband, I., Graves, A., Mnih, V., Munos, R., Hassabis, D., Pietquin, O., et al. (2017) · 2017
Later among the works it cites.
Deep reinforcement learning that matters
Henderson, P., Islam, R., Bachman, P., Pineau, J., Precup, D., and Meger, D. (2017) · 2017
Later among the works it cites.
Shallow updates for deep reinforcement learning
Levine, N., Zahavy, T., Mankowitz, D. J., Tamar, A., and Mannor, S. (2017) · 2017
Later among the works it cites.
Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents
Original
Machado, M. C., Bellemare, M. G., Talvitie, E., Veness, J., Hausknecht, M., and Bowling, M. (2017) · 2017
Later among the works it cites.
Count-based exploration with neural density models
Ostrovski, G., Bellemare, M. G., Oord, A. v. d., and Munos, R. (2017) · 2017
Later among the works it cites.
Mastering the game of go without human knowledge
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al. (2017) · 2017
Later among the works it cites.
Stochastic activation pruning for robust adversarial defense
Original
Dhillon, G. S., Azizzadenesheli, K., Lipton, Z. C., Bernstein, J., Kossaifi, J., Khanna, A., and Anandkumar, A. (2018) · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…