CoChat
Sign Up
PreprintCited by 5Reinforcement Learning in RoboticsAdaptive Dynamic Programming ControlMachine Learning and Algorithms

The DOI matches its DataCite record.

Generalised Policy Improvement with Geometric Policy Composition

Open access
Thakoor, Shantanu, Rowland, Mark, Borsa, Diana, Dabney, Will, Munos, Rémi, Barreto, André·2022·arXiv
DOI 10.48550/arxiv.2206.08736arXiv 2206.08736
Open this paper in CoChat — free accountOpen PDF

Abstract

We introduce a method for policy improvement that interpolates between the greedy approach of value-based reinforcement learning (RL) and the full planning approach typical of model-based RL. The new method builds on the concept of a geometric horizon model (GHM, also known as a gamma-model), which models the discounted state-visitation distribution of a given policy. We show that we can evaluate any non-Markov policy that switches between a set of base Markov policies with fixed probability by a careful composition of the base policy GHMs, without any additional learning. We can then apply generalised policy improvement (GPI) to collections of such non-Markov policies to obtain a new Markov policy that will in general outperform its precursors. We provide a thorough theoretical analysis of this approach, develop applications to transfer and standard RL, and empirically demonstrate its effectiveness over standard GPI on a challenging deep RL continuous control task. We also provide an analysis of GHM training methods, proving a novel convergence result regarding previously proposed methods and showing how to train these models stably in deep RL settings.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2206.08736

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • The SM can be estimated with density estimation techniques such as generative adversarial learning, variational inference, and contrastive learning.

    “As we will discuss in §3.2, we can estimate the SM with density estimation techniques such as generative adversarial learning Janner et al. (2020), variational inference (Thakoor et al., 2022), and contrastive learning (Eysenbach et al., 2020; Zheng et al., 2023).”

    From Predictive Representations: Building Blocks of Intelligence (2024) · cites this paper as Thakoor et al. (2022)

  • Sampling from the SM can be useful for policy evaluation and model-based control.

    “This can be useful for policy evaluation and model-based control (Thakoor et al., 2022).”

    From Predictive Representations: Building Blocks of Intelligence (2024) · cites this paper as Thakoor et al., 2022

  • Learning an SM that can be sampled from is useful for evaluating a policy, evaluating a sequence of policies, and in model-based control.

    “Learning an SM that can be sampled from is useful for evaluating a policy (Eq. 26), evaluating a sequence of policies (Thakoor et al., 2022), and in model-based control (Janner et al., 2020).”

    From Predictive Representations: Building Blocks of Intelligence (2024) · cites this paper as Thakoor et al., 2022

  • The most recent promising method for learning Eq. 46 has been to leverage a variational autoencoder.

    “The most recent promising method for learning Eq. 46 has been to leverage a variational autoencoder (Thakoor et al., 2022).”

    From Predictive Representations: Building Blocks of Intelligence (2024) · cites this paper as Thakoor et al., 2022

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 84

  1. Abdolmaleki, A., Springenberg, J. T., Tassa, Y., Munos, R., Heess, N., and Riedmiller, M. Maximum a posteriori policy optimisation. In Proceedings of the International Conference on Learning Representations, 2018.
  2. Agrawal, S. and Jia, R. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In Ad- vances in Neural Information Processing Systems, 2017.
  3. Alver, S. and Precup, D. Constructing a good behavior basis for transfer using generalized policy updates. In Proceedings of the International Conference on Learning Representations, 2022.
  4. Andrychowicz, M., Wolski, F., Ray, A., Schneider, J., Fong, R., Welinder, P., McGrew, B., Tobin, J., Abbeel, P., and Zaremba, W. Hindsight experience replay. In Advances in Neural Information Processing Systems, 2017.
  5. Ba, J. L., Kiros, J. R., and Hinton, G. E. Layer normalization. arXiv, 2016.
  6. Barreto, A., Dabney, W., Munos, R., Hunt, J. J., Schaul, T., Van Hasselt, H., and Silver, D. Successor features for transfer in reinforcement learning. In Advances in Neural Information Processing Systems, 2017.
  7. Barreto, A., Borsa, D., Quan, J., Schaul, T., Silver, D., Hessel, M., Mankowitz, D., Zidek, A., and Munos, R. Transfer in deep reinforcement learning using successor features and generalised policy improvement. In Pro- ceedings of the International Conference on Machine Learning, 2018.
  8. Barreto, A., Borsa, D., Hou, S., Comanici, G., Aygün, E., Hamel, P., Toyama, D., Hunt, J. J., Mourad, S., Silver, D., and Precup, D. The option keyboard: Combining skills in reinforcement learning. In Advances in Neural Information Processing Systems, 2019.
  9. Barreto, A., Hou, S., Borsa, D., Silver, D., and Precup, D. Fast reinforcement learning with generalized policy up- dates. Proceedings of the National Academy of Sciences, 117(48):30079-30087, 2020. ISSN 0027-8424.
  10. Blier, L., Tallec, C., and Ollivier, Y. Learning successor states and goal-dependent values: A mathematical view- point. arXiv, 2021.
  11. Borsa, D., Barreto, A., Quan, J., Mankowitz, D. J., van Has- selt, H., Munos, R., Silver, D., and Schaul, T. Universal successor features approximators. In Proceedings of the International Conference on Learning Representations, 2019.
  12. Brunskill, E. and Li, L. PAC-inspired option discovery in lifelong reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2014.
  13. Bus ¸oniu, L. and Munos, R. Optimistic planning for Markov decision processes. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2012.
  14. Bus ¸oniu, L., Munos, R., and Babuška, R. A survey of opti- mistic planning in Markov decision processes. In Lewis, F. L. and Liu, D. (eds.), Reinforcement Learning and Adaptive Dynamic Programming for Feedback Control, chapter 22, pp. 494-516.
  15. Dabney, W., Ostrovski, G., and Barreto, A. Temporally- extended -greedy exploration. In Proceedings of the International Conference on Learning Representations, 2021.
  16. Dalal, G., Hallak, A., Dalton, S., Frosio, I., Mannor, S., and Chechik, G. Improve agents without retraining: Parallel tree search with off-policy correction. In Advances in Neural Information Processing Systems, 2021.
  17. Dayan, P. Improving generalization for temporal difference learning: The successor representation. Neural Computa- tion, 5(4):613-624, 1993.
  18. Dinh, L., Sohl-Dickstein, J., and Bengio, S. Density estima- tion using real NVP. In Proceedings of the International Conference on Learning Representations, 2017.
  19. Durkan, C., Bekasov, A., Murray, I., and Papamakarios, G. Neural spline flows. In Advances in Neural Information Processing Systems, 2019.
  20. Efroni, Y., Dalal, G., Scherrer, B., and Mannor, S. Beyond the one step greedy approach in reinforcement learning. In Proceedings of the International Conference on Ma- chine Learning, 2018a.
  21. Efroni, Y., Dalal, G., Scherrer, B., and Mannor, S. Multiple- step greedy policies in online and approximate reinforce- ment learning. In Advances in Neural Information Pro- cessing Systems, 2018b.
  22. Efroni, Y., Dalal, G., Scherrer, B., and Mannor, S. How to combine tree-search methods in reinforcement learn- ing. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
  23. Eysenbach, B., Salakhutdinov, R., and Levine, S. C- learning: Learning to achieve goals via recursive classifi- cation. In Proceedings of the International Conference on Learning Representations, 2021.
  24. Feldman, Z. and Domshlak, C. Monte-Carlo planning: The- oretically fast convergence meets practical efficiency. In Proceedings of the Conference on Uncertainty in Artifi- cial Intelligence, 2013.
  25. Feldman, Z. and Domshlak, C. On MABs and separation of concerns in Monte-Carlo planning for MDPs. In Pro- ceedings of the International Conference on Automated Planning and Scheduling, 2014a.
  26. Feldman, Z. and Domshlak, C. Simple regret optimization in online planning for Markov decision processes. Journal of Artificial Intelligence Research, 51:165-205, 2014b.
  27. Fujimoto, S., Meger, D., and Precup, D. A deep reinforce- ment learning approach to marginalized importance sam- pling with the successor representation. In Proceedings of the International Conference on Machine Learning, 2021.
  28. Grimm, C., Higgins, I., Barreto, A., Teplyashin, D., Wulfmeier, M., Hertweck, T., Hadsell, R., and Singh, S. Disentangled cumulants help successor representations transfer new tasks. arXiv, 2019.
  29. Hansen, S., Dabney, W., Barreto, A., de Wiele, T. V., Warde- Farley, D., and Mnih, V. Fast task inference with varia- tional intrinsic successor features. In Proceedings of the International Conference on Learning Representations, 2020.
  30. Harb, J., Bacon, P.-L., Klissarov, M., and Precup, D. When waiting is not an option: Learning options with a delib- eration cost. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
  31. Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., Kern, R., Picus, M., Hoyer, S., van Kerkwijk, M. H., Brett, M., Haldane, A., del Río, J. F., Wiebe, M., Peterson, P., Gérard-Marchant, P., Sheppard, K., Reddy, T., Weckesser, W., Abbasi, H., Gohlke, C., and Oliphant, T. E. Array programming with NumPy. Nature, 585(7825):357-362, September 2020.
  32. Harutyunyan, A., Dabney, W., Borsa, D., Heess, N., Munos, R., and Precup, D. The termination critic. In Proceedings of the International Conference on Artificial Intelligence and Statistics, 2019.
  33. Higgins, I., Matthey, L., Pal, A., Burgess, C., Glorot, X., Botvinick, M., Mohamed, S., and Lerchner, A. beta-VAE: Learning basic visual concepts with a constrained vari- ational framework. In Proceedings of the International Conference on Learning Representations, 2016.
  34. Hunt, J., Barreto, A., Lillicrap, T., and Heess, N. Com- posing entropic policies using divergence correction. In Proceedings of the International Conference on Machine Learning, 2019.
  35. Hunter, J. D. Matplotlib: A 2d graphics environment. Com- puting in Science & Engineering, 9(3):90-95, 2007.
  36. Janner, M., Mordatch, I., and Levine, S. Gamma-models: Generative temporal difference learning for infinite- horizon prediction. In Advances in Neural Information Processing Systems, 2020.
  37. Kaelbling, L. P. Learning to achieve goals. In Proceed- ings of the International Joint Conference on Artificial Intelligence, 1993.
  38. Kingma, D. P. and Ba, J. Adam: A method for stochastic op- timization. Proceedings of the International Conference on Learning Representations, 2015.
  39. Kingma, D. P. and Dhariwal, P. Glow: Generative flow with invertible 1x1 convolutions. In Advances in Neural Information Processing Systems, 2018.
  40. Kingma, D. P. and Welling, M. Auto-encoding variational Bayes. In Proceedings of the International Conference on Learning Representations, 2014.
  41. Kulkarni, T. D., Narasimhan, K., Saeedi, A., and Tenen- baum, J. Hierarchical deep reinforcement learning: In- tegrating temporal abstraction and intrinsic motivation. In Advances in Neural Information Processing Systems, 2016a.
  42. Kulkarni, T. D., Saeedi, A., Gautam, S., and Gershman, S. J. Deep successor reinforcement learning. arXiv, 2016b.
  43. Kushner, H. and Yin, G. G. Stochastic Approximation and Recursive Algorithms and Applications. Springer, 2003.
  44. Lehnert, L. and Littman, M. L. Successor features combine elements of model-free and model-based reinforcement learning. Journal of Machine Learning Research, 21: 196:1-196:53, 2020.
  45. Lesner, B. and Scherrer, B. Non-stationary approximate modified policy iteration. In Proceedings of the Interna- tional Conference on Machine Learning, 2015.
  46. Machado, M. C., Bellemare, M. G., and Bowling, M. A Laplacian framework for option discovery in reinforce- ment learning. In Proceedings of the International Con- ference on Machine Learning, 2017.
  47. McGovern, A. and Barto, A. G. Automatic discovery of sub- goals in reinforcement learning using diverse density. In Proceedings of the International Conference on Machine Learning, 2001.
  48. Menache, I., Mannor, S., and Shimkin, N. Q-cut -dynamic discovery of sub-goals in reinforcement learning. In Proceedings of the European Conference on Machine Learning, 2002.
  49. Meyn, S. Control Systems and Reinforcement Learning. Cambridge University Press, 2022.
  50. Munos, R. From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning. Foundations and Trends® in Machine Learning, 7(1): 1-129, 2014.
  51. Nemecek, M. and Parr, R. Policy caches with successor features. In Proceedings of the International Conference on Machine Learning, 2021.
  52. Norris, J. R. Markov Chains. Cambridge University Press, 1998.
  53. Osband, I., Russo, D., and Van Roy, B. (more) efficient rein- forcement learning via posterior sampling. In Advances in Neural Information Processing Systems, 2013.
  54. Perron, O. Zur Theorie der Matrices. Mathematische An- nalen, 64(2):248-263, 1907.
  55. Pong, V., Gu, S., Dalal, M., and Levine, S. Temporal dif- ference models: Model-free deep RL for model-based control. In Proceedings of the International Conference on Learning Representations, 2018.
  56. Precup, D. Temporal abstraction in reinforcement learning. PhD thesis, University of Massachusetts Amherst, 2000.
  57. Precup, D., Sutton, R. S., and Singh, S. Multi-time models for temporally abstract planning. In Advances in Neural Information Processing Systems, 1998a.
  58. Precup, D., Sutton, R. S., and Singh, S. Theoretical results on reinforcement learning with temporally abstract op- tions. In Proceedings of the European Conference on Machine Learning, 1998b.
  59. Precup, D., Sutton, R. S., and Singh, S. P. Eligibility traces for off-policy policy evaluation. In Proceedings of the International Conference on Machine Learning, 2000.
  60. Puterman, M. L. Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014.
  61. Rezende, D. and Mohamed, S. Variational inference with normalizing flows. In Proceedings of the International Conference on Machine Learning, 2015.
  62. Rezende, D. J., Mohamed, S., and Wierstra, D. Stochas- tic backpropagation and approximate inference in deep generative models. In Proceedings of the International Conference on Machine Learning, 2014.
  63. Robbins, H. and Siegmund, D. A convergence theorem for non negative almost supermartingales and some applica- tions. In Optimizing methods in statistics, pp. 233-257. Elsevier, 1971.
  64. Russo, D. J., Van Roy, B., Kazerouni, A., Osband, I., Wen, Z., et al. A tutorial on Thompson sampling. Foundations and Trends® in Machine Learning, 11(1):1-96, 2018.
  65. Schaul, T., Horgan, D., Gregor, K., and Silver, D. Universal value function approximators. In Proceedings of the International Conference on Machine Learning, 2015.
  66. Scherrer, B. and Lesner, B. On the use of non-stationary policies for stationary infinite-horizon Markov decision processes. In Advances in Neural Information Processing Systems, 2012.
  67. Schulman, J., Moritz, P., Levine, S., Jordan, M., and Abbeel, P. High-dimensional continuous control using generalized advantage estimation. In Proceedings of the International Conference on Learning Representations, 2016.
  68. Seneta, E. Non-Negative Matrices and Markov Chains. Springer Science & Business Media, 2006.
  69. Silver, D. and Ciosek, K. Compositional planning using op- timal option models. In Proceedings of the International Conference on Machine Learning, 2012.
  70. S ¸ims ¸ek, Ö. and Barto, A. G. Using relative novelty to identify useful temporal abstractions in reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2004.
  71. Sohn, K., Lee, H., and Yan, X. Learning structured output representation using deep conditional generative models. In Advances in Neural Information Processing Systems, 2015.
  72. Strens, M. A Bayesian framework for reinforcement learn- ing. In Proceedings of the International Conference on Machine Learning, 2000.
  73. Sutton, R. S. TD models: Modeling the world at a mix- ture of time scales. In Proceedings of the International Conference on Machine Learning, 1995.
  74. Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT Press, 2018.
  75. Sutton, R. S., Precup, D., and Singh, S. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2): 181-211, 1999.
  76. Szörényi, B., Kedenburg, G., and Munos, R. Optimistic planning in Markov decision processes using a generative model. In Advances in Neural Information Processing Systems, 2014.
  77. Todorov, E., Erez, T., and Tassa, Y. MuJoCo: A physics engine for model-based control. In Proceedings of the IEEE International Conference on Intelligent Robots and Systems, 2012.
  78. Tomar, M., Efroni, Y., and Ghavamzadeh, M. Multi-step greedy reinforcement learning algorithms. In Proceedings of the International Conference on Machine Learning, 2020.
  79. Touati, A. and Ollivier, Y. Learning one representation to optimize all rewards. In Advances in Neural Information Processing Systems, 2021.
  80. Toussaint, M. and Storkey, A. Probabilistic inference for computing optimal policies in MDPs. In NIPS Work- shop on Game Theory, Machine Learning and Reasoning under Uncertainty, 2005.
  81. Toussaint, M. and Storkey, A. Probabilistic inference for solving discrete and continuous state Markov decision processes. In Proceedings of the International Conference on Machine Learning, 2006.
  82. Wulfmeier, M., Rao, D., Hafner, R., Lampe, T., Abdol- maleki, A., Hertweck, T., Neunert, M., Tirumala, D., Siegel, N., Heess, N., and Riedmiller, M. Data-efficient hindsight off-policy option learning. In Proceedings of the International Conference on Machine Learning, 2021.
  83. Yao, H., Szepesvári, Cs., Sutton, R. S., Modayil, J., and Bhatnagar, S. Universal option models. In Advances in Neural Information Processing Systems, 2014.
  84. Zahavy, T., Barreto, A., Mankowitz, D. J., Hou, S., O'Donoghue, B., Kemaev, I., and Singh, S. Discovering a set of policies for the worst case reward. In Proceedings of the International Conference on Learning Representa- tions, 2021.

Cited by

Sorted by citations

Metadata

Authors
Thakoor, S., Rowland, M., Borsa, D., Dabney, W., Munos, R., & Barreto, A.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2022
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2206.08736
arXiv
2206.08736
OpenAlex
W4320473926
Cited by
5
References
0
Citations by year
2026: 1 · 2025: 1 · 2024: 1 · 2023: 1 · 2022: 1
Type
posted content
Language
en
Open access
Licence
creativecommons.org/licenses/by/4.0/legalcode
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
  • Physical Sciences › Engineering › Control and Systems Engineering › Adaptive Dynamic Programming Control
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
Keywords
gamma model, policy composition, value-based reinforcement learning, model-based reinforcement learning, transfer learning, continuous control, convergence analysis, deep reinforcement learning

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review