2022

Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward

Xu, Tengyu, Wang, Yue, Zou, Shaofeng et al.

Understand

The remarkable success of reinforcement learning (RL) heavily relies on observing the reward of every visited state-action pair.

In many real world applications, however, an agent can observe only a score that represents the quality of the whole trajectory, which is referred to as the {\em trajectory-wise reward}.
In such a situation, it is difficult for standard RL methods to well utilize trajectory-wise reward, and large bias and variance errors can be incurred in policy evaluation.
In this work, we propose a novel offline RL algorithm, called Pessimistic vAlue iteRaTion with rEward Decomposition (PARTED), which decomposes the trajectory return into per-step proxy rewards via least-squares-based reward redistribution, and then performs pessimistic value iteration based on the learned proxy reward.

Built on

S. Hochreiter and J. Schmidhuber, “Long short-term memory,” Neural Computation
1997
Earlier work this paper cites.
H. Rahmandad, N. Repenning, and J. Sterman, “Effects of feedback delay on learning,” System Dynamics Review
2009
Earlier work this paper cites.
PhD thesis, University of Alberta, 2011
H. R. Maei, Gradient temporal-difference learning algorithms · 2011
Earlier work this paper cites.
M. Valko, N. Korda, R. Munos, I. Flaounas, and N. Cristianini, “Finite-time analysis of kernelised contextual bandits,” arXiv preprint arXiv:1309.6869
Original
2013
Earlier work this paper cites.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al
2015
Earlier work this paper cites.
J. A. Tropp, “An introduction to matrix concentration inequalities,” arXiv preprint arXiv:1501.01571
Original
2015
Earlier work this paper cites.
S. Levine, C. Finn, T. Darrell, and P. Abbeel, “End-to-end training of deep visuomotor policies,” The Journal of Machine Learning Research
2016
Earlier work this paper cites.
S. Shalev-Shwartz, S. Shammah, and A. Shashua, “Safe, multi-agent, reinforcement learning for autonomous driving,” arXiv preprint arXiv:1610.03295
Original
2016
Earlier work this paper cites.
D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al
2017
Earlier work this paper cites.
M. Olivecrona, T. Blaschke, O. Engkvist, and H. Chen, “Molecular de-novo design through deep reinforcement learning,” Journal of Cheminformatics
2017
Earlier work this paper cites.
D. Hein, S. Depeweg, M. Tokic, S. Udluft, A. Hentschel, T. A. Runkler, and V. Sterzing, “A benchmark environment motivated by industrial control problems,” in Proc. Symposium Series on Computational Intelligence (SSCI)
2017
Earlier work this paper cites.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2017
Earlier work this paper cites.
S. R. Chowdhury and A. Gopalan, “On kernelized multi-armed bandits,” in Proc. International Conference on Machine Learning (ICML)
2017
Earlier work this paper cites.
MIT press, 2018
R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction · 2018
Earlier work this paper cites.
K. Lin, R. Zhao, Z. Xu, and J. Zhou, “Efficient large-scale fleet management via multi-agent deep reinforcement learning,” in Proc. International Conference on Knowledge Discovery & Data Mining
2018
Earlier work this paper cites.
Z. Zheng, J. Oh, and S. Singh, “On learning intrinsic rewards for policy gradient methods,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2018
Earlier work this paper cites.
J. Oh, Y. Guo, S. Singh, and H. Lee, “Self-imitation learning,” in Proc. International Conference on Machine Learning (ICML)
2018
Earlier work this paper cites.
A. Jacot, F. Gabriel, and C. Hongler, “Neural tangent kernel: convergence and generalization in neural networks,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2018
Earlier work this paper cites.
Cambridge university press, 2018
R. Vershynin, High-dimensional probability: An introduction with applications in data science · 2018
Earlier work this paper cites.
MIT press, 2018
M. Mohri, A. Rostamizadeh, and A. Talwalkar, Foundations of machine learning · 2018
Earlier work this paper cites.
Y. Gong, M. Abdel-Aty, Q. Cai, and M. S. Rahman, “Decentralized network level adaptive signal control by multi-agent deep reinforcement learning,” Transportation Research Interdisciplinary Perspectives
2019
Earlier work this paper cites.
J. A. Arjona-Medina, M. Gillhofer, M. Widrich, T. Unterthiner, J. Brandstetter, and S. Hochreiter, “Rudder: return decomposition for delayed rewards,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2019
Earlier work this paper cites.
Y. Liu, Y. Luo, Y. Zhong, X. Chen, Q. Liu, and J. Peng, “Sequence modeling of temporal credit assignment for episodic reinforcement learning,” arXiv preprint arXiv:1905.13420
Original
2019
Earlier work this paper cites.
O. Gottesman, F. Johansson, M. Komorowski, A. Faisal, D. Sontag, F. Doshi-Velez, and L. A. Celi, “Guidelines for reinforcement learning in healthcare,” Nature medicine
2019
Earlier work this paper cites.

Similar

S. Fujimoto, D. Meger, and D. Precup, “Off-policy deep reinforcement learning without exploration,” in Proc. International Conference on Machine Learning (ICML)
2019
Cited alongside, same era.
S. Fujimoto, E. Conti, M. Ghavamzadeh, and J. Pineau, “Benchmarking batch deep reinforcement learning algorithms,” arXiv preprint arXiv:1910.01708
Original
2019
Cited alongside, same era.
R. Gao, T. Cai, H. Li, C.-J. Hsieh, L. Wang, and J. D. Lee, “Convergence of adversarial training in overparametrized neural networks,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2019
Cited alongside, same era.
Y. Bai and J. D. Lee, “Beyond linearization: on quadratic and higher-order approximation of wide neural networks,” arXiv preprint arXiv:1910.01619
Original
2019
Cited alongside, same era.
Q. Cai, Z. Yang, J. D. Lee, and Z. Wang, “Neural temporal-difference and q-learning provably converge to global optima,” arXiv preprint arXiv:1905.10027
Original
2019
Cited alongside, same era.
L. Wang, Q. Cai, Z. Yang, and Z. Wang, “Neural policy gradient methods: Global optimality and rates of convergence,” arXiv preprint arXiv:1909.01150
Original
2019
Cited alongside, same era.
L. Yang and M. Wang, “Sample-optimal parametric q-learning using linearly additive features,” in Proc. International Conference on Machine Learning (ICML)
2019
Cited alongside, same era.
A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun, “Reinforcement learning: theory and algorithms,” CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep
2019
Cited alongside, same era.
Z. Allen-Zhu, Y. Li, and Z. Song, “A convergence theory for deep learning via over-parameterization,” in Proc. International Conference on Machine Learning (ICML)
2019
Cited alongside, same era.
A. W. Senior, R. Evans, J. Jumper, J. Kirkpatrick, L. Sifre, T. Green, C. Qin, A. Žídek, A. W. Nelson, A. Bridgland, et al
2020
Cited alongside, same era.
T. Gangwani, Y. Zhou, and J. Peng, “Learning guidance rewards with trajectory-space smoothing,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2020
Cited alongside, same era.
R. Wang, D. P. Foster, and S. M. Kakade, “What are the statistical limits of offline rl with linear function approximation?,” arXiv preprint arXiv:2010.11895
Original
2020
Cited alongside, same era.

Then

Z. Ren, R. Guo, Y. Zhou, and J. Peng, “Learning long-term reward redistribution via randomized return decomposition,” arXiv preprint arXiv:2111.13485
Original
2021
Later among the works it cites.
Y. Efroni, N. Merlis, and S. Mannor, “Reinforcement learning with trajectory feedback,” in Proc. AAAI Conference on Artificial Intelligence
2021
Later among the works it cites.
B. Han, Z. Ren, Z. Wu, Y. Zhou, and J. Peng, “Off-policy reinforcement learning with delayed rewards,” arXiv preprint arXiv:2106.11854
Original
2021
Later among the works it cites.
Y. Jin, Z. Yang, and Z. Wang, “Is pessimism provably efficient for offline rl?,” in Proc. International Conference on Machine Learning (ICML)
2021
Later among the works it cites.
M. Yin, Y. Bai, and Y.-X. Wang, “Near-optimal offline reinforcement learning via double variance reduction,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2021
Later among the works it cites.
M. Yin and Y.-X. Wang, “Towards instance-optimal offline reinforcement learning with pessimism,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2021
Later among the works it cites.
A. Cohen, H. Kaplan, T. Koren, and Y. Mansour, “Online markov decision processes with aggregate bandit feedback,” in Proc. Conference on Learning Theory (COLT)
2021
Later among the works it cites.
R. Dadashi, S. Rezaeifar, N. Vieillard, L. Hussenot, O. Pietquin, and M. Geist, “Offline reinforcement learning with pseudometric learning,” in Proc. International Conference on Machine Learning (ICML)
2021
Later among the works it cites.
S. Fujimoto and S. S. Gu, “A minimalist approach to offline reinforcement learning,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2021
Later among the works it cites.
M. Yin and Y.-X. Wang, “Optimal uniform ope and model-based offline reinforcement learning in time-homogeneous, reward-free and task-agnostic settings,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2021
Later among the works it cites.
T. Ren, J. Li, B. Dai, S. S. Du, and S. Sanghavi, “Nearly horizon-free offline reinforcement learning,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2021
Later among the works it cites.
T. Xie, N. Jiang, H. Wang, C. Xiong, and Y. Bai, “Policy finetuning: Bridging sample-efficient offline and online reinforcement learning,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2021
Later among the works it cites.
P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell, “Bridging offline reinforcement learning and imitation learning: A tale of pessimism,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2021
Later among the works it cites.
T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal, “Bellman-consistent pessimism for offline reinforcement learning,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2021
Later among the works it cites.
A. Zanette, M. J. Wainwright, and E. Brunskill, “Provable benefits of actor-critic methods for offline reinforcement learning,” Proc. Advances in Neural Information Processing Systems (NeurIPS)
2021
Later among the works it cites.
A. Zanette, “Exponential lower bounds for batch reinforcement learning: batch rl can be exponentially harder than online rl,” in Proc. International Conference on Machine Learning (ICML)
2021
Later among the works it cites.
D. J. Foster, A. Krishnamurthy, D. Simchi-Levi, and Y. Xu, “Offline reinforcement learning: fundamental barriers for value function approximation,” arXiv preprint arXiv:2111.10919
Original
2021
Later among the works it cites.
T. Xu, Y. Liang, and G. Lan, “Crpo: A new approach for safe reinforcement learning with convergence guarantee,” in Proc. International Conference on Machine Learning (ICML)
2021
Later among the works it cites.
S. Qiu, J. Ye, Z. Wang, and Z. Yang, “On reward-free rl with kernel and neural function approximations: single-agent mdp and markov game,” in Proc. International Conference on Machine Learning (ICML)
2021
Later among the works it cites.
M. Yin, Y. Duan, M. Wang, and Y.-X. Wang, “Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism,” arXiv preprint arXiv:2203.05804
Original
2022
Closest in time.
L. Shi, G. Li, Y. Wei, Y. Chen, and Y. Chi, “Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity,” arXiv preprint arXiv:2202.13890
Original
2022
Closest in time.
Y. Yan, G. Li, Y. Chen, and J. Fan, “The efficacy of pessimism in asynchronous q-learning,” arXiv preprint arXiv:2203.07368
Original
2022
Closest in time.
G. Li, L. Shi, Y. Chen, Y. Chi, and Y. Wei, “Settling the sample complexity of model-based offline reinforcement learning,” arXiv preprint arXiv:2204.05275
Original
2022
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…