2020

GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values

Zhang, Shangtong, Liu, Bo, Whiteson, Shimon

Understand

We present GradientDICE for estimating the density ratio between the state distribution of the target policy and the sampling distribution in off-policy reinforcement learning.

GradientDICE fixes several problems of GenDICE (Zhang et al., 2020), the state-of-the-art for estimating such density ratios.
Namely, the optimization problem in GenDICE is not a convex-concave saddle-point problem once nonlinearity in optimization variable parameterization is introduced to ensure positivity, so any primal-dual algorithm is not guaranteed to converge or find the desired solution.
However, such nonlinearity is essential to ensure the consistency of GenDICE even with a tabular representation.

Built on

Adjustment of an inverse matrix corresponding to a change in one element of a given matrix
Sherman, J. and Morrison, W. J · 1950
Earlier work this paper cites.
A stochastic approximation method
Robbins, H. and Monro, S · 1951
Earlier work this paper cites.
Learning to predict by the methods of temporal differences
Sutton, R. S · 1988
Earlier work this paper cites.
Self-improving reactive agents based on reinforcement learning, planning and teaching
Lin, L.-J · 1992
Earlier work this paper cites.
Residual algorithms: Reinforcement learning with function approximation
Baird, L · 1995
Earlier work this paper cites.
Analysis of temporal-diffference learning with function approximation
Tsitsiklis, J. N. and Van Roy, B · 1997
Earlier work this paper cites.
Least-squares temporal difference learning
Boyan, J. A · 1999
Earlier work this paper cites.
Off-policy temporal-difference learning with function approximation
Precup, D., Sutton, R. S., and Dasgupta, S · 2001
Earlier work this paper cites.
Mirror descent and nonlinear projected subgradient methods for convex optimization
Beck, A. and Teboulle, M · 2003
Earlier work this paper cites.
Convex optimization
Boyd, S. and Vandenberghe, L · 2004
Earlier work this paper cites.
Dual representations for dynamic programming and reinforcement learning
Wang, T., Bowling, M., and Schuurmans, D · 2007
Earlier work this paper cites.
Stable dual dynamic programming
Wang, T., Bowling, M., Schuurmans, D., and Lizotte, D. J · 2008
Earlier work this paper cites.

Similar

Robust stochastic approximation approach to stochastic programming
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A · 2009
Cited alongside, same era.
Rectified linear units improve restricted boltzmann machines
Nair, V. and Hinton, G. E · 2010
Cited alongside, same era.
Gradient temporal-difference learning algorithms
Maei, H. R · 2011
Cited alongside, same era.
Horde: A scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction
Sutton, R. S., Modayil, J., Delp, M., Degris, T., Pilarski, P. M., White, A., and Precup, D · 2011
Cited alongside, same era.
Matrix analysis (2nd Edition)
Horn, R. A. and Johnson, C. R · 2012
Cited alongside, same era.
Markov decision processes: discrete stochastic dynamic programming
Puterman, M. L · 2014
Cited alongside, same era.
Lectures on stochastic programming: modeling and theory
Shapiro, A., Dentcheva, D., and Ruszczyński, A · 2014
Cited alongside, same era.
Doubly robust off-policy value evaluation for reinforcement learning
Original
Jiang, N. and Li, L · 2015
Cited alongside, same era.
Finite-sample analysis of proximal gradient td algorithms
Liu, B., Liu, J., Ghavamzadeh, M., Mahadevan, S., and Petrik, M · 2015
Cited alongside, same era.
Openai gym
Original
Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W · 2016
Cited alongside, same era.
Learning from conditional distributions via dual embeddings
Original
Dai, B., He, N., Pan, Y., Boots, B., and Song, L · 2016
Cited alongside, same era.
Fast gradient-descent methods for temporal-difference learning with linear function approximation
Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E
Cited in the paper.

Then

f-gan: Training generative neural samplers using variational divergence minimization
Nowozin, S., Cseke, B., and Tomioka, R · 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
Later among the works it cites.
Consistent on-line off-policy evaluation
Hallak, A. and Mannor, S · 2017
Later among the works it cites.
Addressing function approximation error in actor-critic methods
Original
Fujimoto, S., van Hoof, H., and Meger, D · 2018
Later among the works it cites.
Linear stochastic approximation: How far does constant step-size and iterate averaging go?
Lakshminarayanan, C. and Szepesvari, C · 2018
Later among the works it cites.
Breaking the curse of horizon: Infinite-horizon off-policy estimation
Liu, Q., Li, L., Tang, Z., and Zhou, D · 2018
Later among the works it cites.
Reinforcement Learning: An Introduction (2nd Edition)
Sutton, R. S. and Barto, A. G · 2018
Later among the works it cites.
Off-policy deep reinforcement learning by bootstrapping the covariate shift
Gelada, C. and Bellemare, M. G · 2019
Later among the works it cites.
Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections
Original
Nachum, O., Chow, Y., Dai, B., and Li, L · 2019
Later among the works it cites.
Minimax weight and q-function learning for off-policy evaluation
Original
Uehara, M. and Jiang, N · 2019
Later among the works it cites.
Black-box off-policy estimation for infinite-horizon reinforcement learning
Mousavi, A., Li, L., Liu, Q., and Zhou, D · 2020
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…