2019

A Geometric Perspective on Optimal Representations for Reinforcement Learning

Bellemare, Marc G., Dabney, Will, Dadashi, Robert et al.

Understand

We propose a new perspective on representation learning in reinforcement learning based on geometric properties of the space of value functions.

We leverage this perspective to provide formal evidence regarding the usefulness of value functions as auxiliary tasks.
Our formulation considers adapting the representation to minimize the (linear) approximation of the value function of all stationary policies for a given environment.
We show that this optimization reduces to making accurate predictions regarding a special class of value functions which we call adversarial value functions (AVFs).

Built on

Dynamic programming
Bellman, R. E. (1957) · 1957
Earlier work this paper cites.
Some studies in machine learning using the game of checkers
Samuel, A. L. (1959) · 1959
Earlier work this paper cites.
Pandemonium: A paradigm for learning
Selfridge, O. (1959) · 1959
Earlier work this paper cites.
Improving generalisation for temporal difference learning: The successor representation
Dayan, P. (1993) · 1993
Earlier work this paper cites.
Markov Decision Processes: Discrete stochastic dynamic programming
Puterman, M. L. (1994) · 1994
Earlier work this paper cites.
On-line Q-learning using connectionist systems
Rummery, G. A. and Niranjan, M. (1994) · 1994
Earlier work this paper cites.
TD models: Modeling the world at a mixture of time scales
Sutton, R. S. (1995) · 1995
Earlier work this paper cites.
Temporal difference learning and TD-Gammon
Tesauro, G. (1995) · 1995
Earlier work this paper cites.
Generalization in reinforcement learning: Successful examples using sparse coarse coding
Sutton, R. S. (1996) · 1996
Earlier work this paper cites.
Reinforcement learning: An introduction
Sutton, R. S. and Barto, A. G. (1998) · 1998
Earlier work this paper cites.
Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning
Sutton, R. S., Precup, D., and Singh, S. P. (1999) · 1999
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
Sutton, R. S., McAllester, D. A., Singh, S. P., and Mansour, Y. (2000) · 2000
Earlier work this paper cites.
Structure in the space of value functions
Foster, D. and Dayan, P. (2002) · 2002
Earlier work this paper cites.
Predictive representations of state
Littman, M. L., Sutton, R. S., and Singh, S. (2002) · 2002
Earlier work this paper cites.
Least-squares policy iteration
Lagoudakis, M. and Parr, R. (2003) · 2003
Earlier work this paper cites.
Error bounds for approximate policy iteration
Munos, R. (2003) · 2003
Earlier work this paper cites.
Convex optimization
Boyd, S. and Vandenberghe, L. (2004) · 2004
Earlier work this paper cites.
Sparse distributed memories for on-line value-based reinforcement learning
Ratitch, B. and Precup, D. (2004) · 2004
Earlier work this paper cites.
Combinatorial optimization: Theory and algorithms
Bernhard, K. and Vygen, J. (2008) · 2005
Earlier work this paper cites.
Tree-based batch mode reinforcement learning
Ernst, D., Geurts, P., and Wehenkel, L. (2005) · 2005
Earlier work this paper cites.
Basis function adaptation in temporal difference reinforcement learning
Menache, I., Mannor, S., and Shimkin, N. (2005) · 2005
Earlier work this paper cites.
Automatic basis function construction for approximate dynamic programming and reinforcement learning
Keller, P. W., Mannor, S., and Precup, D. (2006) · 2006
Earlier work this paper cites.
Towards a unified theory of state abstraction for MDPs
Li, L., Walsh, T., and Littman, M. (2006) · 2006
Earlier work this paper cites.
Proto-value functions: A Laplacian framework for learning representation and control in Markov decision processes
Mahadevan, S. and Maggioni, M. (2007) · 2007
Earlier work this paper cites.

Similar

Performance bounds in l_p-norm for approximate value iteration
Munos, R. (2007) · 2007
Cited alongside, same era.
Analyzing feature generation for value-function approximation
Parr, R., Painter-Wakefield, C., Li, L., and Littman, M. (2007) · 2007
Cited alongside, same era.
An analysis of Laplacian methods for value function approximation in MDPs
Petrik, M. (2007) · 2007
Cited alongside, same era.
An analysis of linear models, linear value-function approximation, and feature selection for reinforcement learning
Parr, R., Li, L., Taylor, G., Painter-Wakefield, C., and Littman, M. L. (2008) · 2008
Cited alongside, same era.
Feature reinforcement learning: Part I. Unstructured MDPs
Hutter, M. (2009) · 2009
Cited alongside, same era.
Variational analysis
Rockafellar, R. T. and Wets, R. J.-B. (2009) · 2009
Cited alongside, same era.
Basis function adaptation methods for cost approximation in mdp
Yu, H. and Bertsekas, D. P. (2009) · 2009
Cited alongside, same era.
Basis construction from power series expansions of value functions
Mahadevan, S. and Liu, B. (2010) · 2010
Cited alongside, same era.
Robust approximate bilinear programming for value function approximation
Petrik, M. and Zilberstein, S. (2011) · 2011
Cited alongside, same era.
Horde: A scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction
Sutton, R., Modayil, J., Delp, M., Degris, T., Pilarski, P., White, A., and Precup, D. (2011) · 2011
Cited alongside, same era.
Dynamic Programming and Optimal Control, Vol. II: Approximate Dynamic Programming
Bertsekas, D. P. (2012) · 2012
Cited alongside, same era.
RmsProp: Divide the gradient by a running average of its recent magnitude
Tieleman, T. and Hinton, G. (2012) · 2012
Cited alongside, same era.

Then

Linear feature encoding for reinforcement learning
Song, Z., Parr, R., Liao, X., and Carin, L. (2016) · 2016
Later among the works it cites.
An emphatic approach to the problem of off-policy temporal-difference learning
Sutton, R. S., Mahmood, A. R., and White, M. (2016) · 2016
Later among the works it cites.
Hindsight experience replay
Andrychowicz, M., Wolski, F., Ray, A., Schneider, J., Fong, R., Welinder, P., McGrew, B., Tobin, J., Abbeel, O. P., and Zaremba, W. (2017) · 2017
Later among the works it cites.
Successor features for transfer in reinforcement learning
Barreto, A., Dabney, W., Munos, R., Hunt, J. J., Schaul, T., van Hasselt, H. P., and Silver, D. (2017) · 2017
Later among the works it cites.
A distributional perspective on reinforcement learning
Bellemare, M. G., Dabney, W., and Munos, R. (2017) · 2017
Later among the works it cites.
Learning to act by predicting the future
Dosovitskiy, A. and Koltun, V. (2017) · 2017
Later among the works it cites.
Reinforcement learning with unsupervised auxiliary tasks
Jaderberg, M., Mnih, V., Czarnecki, W. M., Schaul, T., Leibo, J. Z., Silver, D., and Kavukcuoglu, K. (2017) · 2017
Later among the works it cites.
Shallow updates for deep reinforcement learning
Levine, N., Zahavy, T., Mankowitz, D., Tamar, A., and Mannor, S. (2017) · 2017
Later among the works it cites.
A Laplacian framework for option discovery in reinforcement learning
Machado, M. C., Bellemare, M. G., and Bowling, M. (2017) · 2017
Later among the works it cites.
Boosted fitted q-iteration
Tosatto, S., Pirotta, M., D’Eramo, C., and Restelli, M. (2017) · 2017
Later among the works it cites.
Feature selection by singular value decomposition for reinforcement learning
Behzadian, B. and Petrik, M. (2018) · 2018
Later among the works it cites.
Feature-based aggregation and deep reinforcement learning: A survey and some new implementations
Bertsekas, D. P. (2018) · 2018
Later among the works it cites.
Dopamine: A research framework for deep reinforcement learning
Castro, P. S., Moitra, S., Gelada, C., Kumar, S., and Bellemare, M. G. (2018) · 2018
Later among the works it cites.
Combined reinforcement learning via abstract representations
François-Lavet, V., Bengio, Y., Precup, D., and Pineau, J. (2018) · 2018
Later among the works it cites.
Eigenoption discovery through the deep successor representation
Machado, M. C., Rosenbaum, C., Guo, X., Liu, M., Tesauro, G., and Campbell, M. (2018) · 2018
Later among the works it cites.
Representation learning with contrastive predictive coding
van den Oord, A., Li, Y., and Vinyals, O. (2018) · 2018
Later among the works it cites.
Deep reinforcement learning and the deadly triad
van Hasselt, H., Doron, Y., Strub, F., Hessel, M., Sonnerat, N., and Modayil, J. (2018) · 2018
Later among the works it cites.
Two-timescale networks for nonlinear value function approximation
Chung, W., Nath, S., Joseph, A. G., and White, M. (2019) · 2019
Closest in time.
The value function polytope in reinforcement learning
Dadashi, R., Taïga, A. A., Roux, N. L., Schuurmans, D., and Bellemare, M. G. (2019) · 2019
Closest in time.
DeepMDP: Learning continuous latent space modelsfor representation learning
Gelada, C., Kumar, S., Buckman, J., Nachum, O., and Bellemare, M. G. (2019) · 2019
Closest in time.
Near-optimal representation learning for hierarchical reinforcement learning
Nachum, O., Gu, S., Lee, H., and Levine, S. (2019) · 2019
Closest in time.
An Atari model zoo for analyzing, visualizing, and comparing deep reinforcement learning agents
Such, F. P., Madhavan, V., Liu, R., Wang, R., Castro, P. S., Li, Y., Schubert, L., Bellemare, M. G., Clune, J., and Lehman, J. (2019) · 2019
Closest in time.
The laplacian in rl: Learning representations with efficient approximations
Wu, Y., Tucker, G., and Nachum, O. (2019) · 2019
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…