CoChat
Sign Up
PreprintCited by 5Reinforcement Learning in RoboticsMachine Learning and AlgorithmsAdvanced Bandit Algorithms Research

The DOI matches its DataCite record.

On Value Functions and the Agent-Environment Boundary

Open access
Jiang, Nan·2019·arXiv
DOI 10.48550/arxiv.1905.13341arXiv 1905.13341
Open this paper in CoChat — free accountOpen PDF

Abstract

When function approximation is deployed in reinforcement learning (RL), the same problem may be formulated in different ways, often by treating a pre-processing step as a part of the environment or as part of the agent. As a consequence, fundamental concepts in RL, such as (optimal) value functions, are not uniquely defined as they depend on where we draw this agent-environment boundary, causing problems in theoretical analyses that provide optimality guarantees. We address this issue via a simple and novel boundary-invariant analysis of Fitted Q-Iteration, a representative RL algorithm, where the assumptions and the guarantees are invariant to the choice of boundary. We also discuss closely related issues on state resetting and Monte-Carlo Tree Search, deterministic vs stochastic systems, imitation learning, and the verifiability of theoretical assumptions from data.

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.1905.13341

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?

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: 29

  1. Andr´ as Antos, Csaba Szepesv´ ari, and R´ emi Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning , 71(1):89-129, 2008.
  2. Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995 , pages 30-37. Elsevier, 1995.
  3. Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research , 47:253-279, 2013.
  4. Jinglin Chen and Nan Jiang. Information-theoretic considerations in batch reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning , pages 1042-1051, 2019.
  5. Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Conference on Machine Learning , pages 1133-1142, 2018.
  6. Christoph Dann, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. On Oracle-Efficient PAC RL with Rich Observations. In Advances in Neural Information Processing Systems , pages 1429-1439, 2018.
  7. Damien Ernst, Pierre Geurts, and Louis Wehenkel. Treebased batch mode reinforcement learning. Journal of Machine Learning Research , 6:503-556, 2005.
  8. Amir-massoud Farahmand, Csaba Szepesv´ ari, and R´ emi Munos. Error Propagation for Approximate Policy and Value Iteration. In Advances in Neural Information Processing Systems , pages 568-576, 2010.
  9. Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep q-learning algorithms. In Proceedings of the 36th International Conference on Machine Learning , pages 2021-2030, 2019.
  10. Geoffrey J Gordon. Stable function approximation in dynamic programming. In Proceedings of the twelfth international conference on machine learning , pages 261-268, 1995.
  11. Xiaoxiao Guo, Satinder Singh, Honglak Lee, Richard L Lewis, and Xiaoshi Wang. Deep learning for real-time atari game play using offline monte-carlo tree search planning. In Advances in neural information processing systems , pages 3338-3346, 2014.
  12. Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In International Conference on Machine Learning , 2017.
  13. Sham Kakade and John Langford. Approximately Optimal Approximate Reinforcement Learning. In Proceedings of the 19th International Conference on Machine Learning , volume 2, pages 267-274, 2002.
  14. Michael Kearns, Yishay Mansour, and Andrew Y Ng. A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Machine Learning , 49 (2-3):193-208, 2002.
  15. Levente Kocsis and Csaba Szepesv´ ari. Bandit based montecarlo planning. In Machine Learning: ECML 2006 , pages 282-293. Springer Berlin Heidelberg, 2006.
  16. John Langford and Tong Zhang. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems , pages 817-824, 2008.
  17. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature , 518(7540):529-533, 2015.
  18. R´ emi Munos. Error bounds for approximate policy iteration. In ICML , volume 3, pages 560-567, 2003.
  19. Andrew Y Ng and Michael Jordan. PEGASUS: A policy search method for large MDPs and POMDPs. In Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence , pages 406-415. Morgan Kaufmann Publishers Inc., 2000.
  20. MLPuterman. Markov Decision Processes. Jhon Wiley & Sons, New Jersey , 1994.
  21. Stephane Ross and J Andrew Bagnell. Reinforcement and imitation learning via interactive no-regret learning. arXiv preprint arXiv:1406.5979 , 2014. · arXiv
  22. St´ ephane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics , pages 627-635, 2011.
  23. David Silver and Joel Veness. Monte-Carlo planning in large POMDPs. In Advances in Neural Information Processing Systems , pages 2164-2172, 2010.
  24. Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction . MIT press, 2018.
  25. Csaba Szepesv´ ari. Algorithms for reinforcement learning. Synthesis lectures on artificial intelligence and machine learning , 4(1):1-103, 2010.
  26. Csaba Szepesv´ ari and R´ emi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning , pages 880-887. ACM, 2005.
  27. John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE TRANSACTIONS ON AUTOMATIC CONTROL , 42(5), 1997.
  28. Benjamin Van Roy. Feature-based methods for large scale dynamic programming . PhD thesis, Massachusetts Institute of Technology, 1994.
  29. David H Wolpert. The lack of a priori distinctions between learning algorithms. Neural computation , 8(7): 1341-1390, 1996.

Cited by

Sorted by citations

Metadata

Authors
Jiang, N.
Corresponding author
Jiang, Nan
Venue
arXiv
Publisher
arXiv
Published
2019
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1905.13341
arXiv
1905.13341
OpenAlex
W2946911039
Cited by
5
References
0
Citations by year
2024: 1 · 2022: 2 · 2020: 1 · 2019: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
Keywords
value function, fitted Q-iteration, function approximation, optimality guarantees, Monte Carlo tree search, imitation 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