Dual Representations for Dynamic Programming

• Author(s) / Creator(s)

  • Lizotte, Daniel
  • Wang, Tao
  • Bowling, Michael
  • Schuurmans, Dale

• Technical report TR08-16. We propose a dual approach to dynamic programming and reinforcement learning based on maintaining an explicit representation of visit distributions as opposed to value functions. An advantage of working in the dual is that it allows one to exploit techniques for representing, approximating, and estimating probability distributions, while also avoiding any risk of divergence. We begin by formulating a modified dual of the standard linear program that guarantees the solution is a globally normalized visit distribution. Using this alternative representation, we then derive dual forms of dynamic programming, including on-policy updating, policy improvement and off-policy updating, and furthermore show how to incorporate function approximation. We then investigate the convergence properties of these algorithms, both theoretically and empirically, and show that the dual approach remains stable in situations when primal value function approximation diverges. Overall, the dual approach offers a viable alternative to standard dynamic programming techniques and offers new avenues for developing algorithms for sequential decision making. | TRID-ID TR08-16

• Date created

  2008

• Subjects / Keywords

  • Reinforcement Learning

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3BZ6188R

• License

  Attribution 3.0 International