CoChat
Sign Up
PreprintCited by 3Reinforcement Learning in RoboticsAdvanced Bandit Algorithms ResearchMachine Learning and Algorithms

The DOI matches its DataCite record.

Reinforcement Learning with Trajectory Feedback

Open access
Efroni, Yonathan, Merlis, Nadav, Mannor, Shie·2020·arXiv
DOI 10.48550/arxiv.2008.06036arXiv 2008.06036
Open this paper in CoChat — free account

Abstract

The standard feedback model of reinforcement learning requires revealing the reward of every visited state-action pair. However, in practice, it is often the case that such frequent feedback is not available. In this work, we take a first step towards relaxing this assumption and require a weaker form of feedback, which we refer to as \emph{trajectory feedback}. Instead of observing the reward obtained after every action, we assume we only receive a score that represents the quality of the whole trajectory observed by the agent, namely, the sum of all rewards obtained over this trajectory. We extend reinforcement learning algorithms to this setting, based on least-squares estimation of the unknown reward, for both the known and unknown transition model cases, and study the performance of these algorithms by analyzing their regret. For cases where the transition model is unknown, we offer a hybrid optimistic-Thompson Sampling approach that results in a tractable algorithm.

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

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?

  • With probability greater than 1−δ, the expected cumulative visitation bound stated in Lemma E.7 holds.

    “Lemma E.7 (Expected Cumulative Visitation Bound, Lemma 22, Efroni et al. (2020), adapted to DCMDPs) . Let {F k } K k =1 be the natural filtration. Then, with probability greater than 1 -δ it holds that”

    From Reinforcement Learning with History-Dependent Dynamic Contexts (2023) · cites this paper as Efroni et al. (2020)

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

  1. Abbasi-Yadkori, Y.; P´ al, D.; and Szepesv´ ari, C. 2011. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems , 2312-2320.
  2. Abeille, M.; Lazaric, A.; et al. 2017. Linear thompson sampling revisited. Electronic Journal of Statistics 11(2): 51655197.
  3. Agarwal, A.; Kakade, S. M.; Lee, J. D.; and Mahajan, G. 2020. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory , 64-66. PMLR.
  4. Agrawal, S.; and Goyal, N. 2013. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning , 127-135.
  5. Altman, E. 1999. Constrained Markov decision processes , volume 7. CRC Press.
  6. Atamt¨ urk, A.; and G´ omez, A. 2017. Maximizing a class of utility functions over the vertices of a polytope. Operations Research 65(2): 433-445.
  7. Azar, M. G.; Osband, I.; and Munos, R. 2017. Minimax regret bounds for reinforcement learning. arXiv preprint arXiv:1703.05449 . · arXiv
  8. Bartlett, M. S. 1951. An inverse matrix adjustment arising in discriminant analysis. The Annals of Mathematical Statistics 22(1).
  9. Beygelzimer, A.; Langford, J.; Li, L.; Reyzin, L.; and Schapire, R. 2011. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , 19-26.
  10. Borjesson, P.; and Sundberg, C.-E. 1979. Simple approximations of the error function Q (x) for communications applications. IEEE Transactions on Communications 27(3): 639-643.
  11. Chu, W.; Li, L.; Reyzin, L.; and Schapire, R. 2011. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , 208-214.
  12. Dani, V.; Hayes, T.; and Kakade, S. 2008. Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Annual Conference on Learning Theory (COLT) . Citeseer.
  13. Dann, C.; and Brunskill, E. 2015. Sample complexity of episodic fixed-horizon reinforcement learning. In Advances in Neural Information Processing Systems , 2818-2826.
  14. Dann, C.; Lattimore, T.; and Brunskill, E. 2017. Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems , 5713-5723.
  15. Dann, C.; Li, L.; Wei, W.; and Brunskill, E. 2019. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning , 1507-1516.
  16. Efroni, Y.; Merlis, N.; Ghavamzadeh, M.; and Mannor, S. 2019. Tight regret bounds for model-based reinforcement learning with greedy policies. In Advances in Neural Information Processing Systems , 12224-12234.
  17. Filippi, S.; Cappe, O.; Garivier, A.; and Szepesv´ ari, C. 2010. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems , 586-594.
  18. Gopalan, A.; and Mannor, S. 2015. Thompson sampling for learning parameterized Markov decision processes. In Conference on Learning Theory , 861-898.
  19. Jaksch, T.; Ortner, R.; and Auer, P. 2010. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research 11(Apr): 1563-1600.
  20. Jin, C.; Allen-Zhu, Z.; Bubeck, S.; and Jordan, M. I. 2018. Is Q-learning provably efficient? In Advances in Neural Information Processing Systems , 4863-4873.
  21. Jin, T.; and Luo, H. 2019. Learning adversarial mdps with bandit feedback and unknown transition. arXiv preprint arXiv:1912.01192 . · arXiv
  22. Kveton, B.; Zaheer, M.; Szepesvari, C.; Li, L.; Ghavamzadeh, M.; and Boutilier, C. 2020. Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statistics , 2066-2076.
  23. Laurent, B.; and Massart, P. 2000. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics 1302-1338.
  24. Levine, S.; Finn, C.; Darrell, T.; and Abbeel, P. 2016. Endto-end training of deep visuomotor policies. Journal of Machine Learning Research 17(1): 1334-1373.
  25. Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M.; Graves, A.; Riedmiller, M.; Fidjeland, A.; Ostrovski, G.; et al. 2015. Human-level control through deep reinforcement learning. Nature 518(7540): 529.
  26. Osband, I.; Russo, D.; and Van Roy, B. 2013. (More) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems , 30033011.
  27. Osband, I.; and Van Roy, B. 2016. On lower bounds for regret in reinforcement learning. arXiv preprint arXiv:1608.02732 . · arXiv
  28. Osband, I.; and Van Roy, B. 2017. Why is posterior sampling better than optimism for reinforcement learning? In International Conference on Machine Learning , 2701-2710.
  29. Puterman, M. L. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley & Sons, Inc.
  30. Rosenberg, A.; and Mansour, Y. 2019. Online convex optimization in adversarial markov decision processes. arXiv preprint arXiv:1905.07773 . · arXiv
  31. Russo, D. 2019. Worst-case regret bounds for exploration via randomized value functions. In Advances in Neural Information Processing Systems , 14433-14443.
  32. Silver, D.; Schrittwieser, J.; Simonyan, K.; Antonoglou, I.; Huang, A.; Guez, A.; Hubert, T.; Baker, L.; Lai, M.; Bolton, A.; et al. 2017. Mastering the game of Go without human knowledge. Nature 550(7676): 354.
  33. Simchowitz, M.; and Jamieson, K. G. 2019. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Advances in Neural Information Processing Systems , 1153-1162.
  34. Williams, R. J. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning 8(3-4): 229-256.
  35. Zanette, A.; and Brunskill, E. 2019. Tighter problemdependent regret bounds in reinforcement learning without domain knowledge using value function bounds. arXiv preprint arXiv:1901.00210 . · arXiv
  36. Zimin, A.; and Neu, G. 2013. Online learning in episodic Markovian decision processes by relative entropy policy search. In NIPS , 1583-1591.

Cited by

Sorted by citations

Metadata

Authors
Efroni, Y., Merlis, N., & Mannor, S.
Affiliations
Technion – Israel Institute of Technology (IL)
ORCID
Mannor, Shie
Venue
arXiv
Publisher
arXiv
Published
2020
Volume
35
Issue
8
Pages
7288-7295
ISSN
2159-5399 (ISSN-L)
DOI
10.48550/arxiv.2008.06036
arXiv
2008.06036
OpenAlex
W3048454540
Cited by
3
References
0
Citations by year
2023: 3
FWCI
0.35
Type
conference paper
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • Proceedings of the AAAI Conference on Artificial Intelligence (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
Israel Science Foundation
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
Keywords
reinforcement learning, partial feedback, reward estimation, least squares estimation, regret analysis, Thompson sampling, online 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