Approximate Dynamic Programming with Affine ADDs

The Affine ADD (AADD) is an extension of the Algebraic Decision Diagram (ADD) that compactly represents context-specific, additive and multiplicative structure in functions from a discretedomain to a real-valued range. In this paper, we introduce a novelalgorithm for efficiently finding AADD approximations that we useto develop the MADCAP algorithm for AADD-based structuredapproximate dynamic programming (ADP) with factored MDPs. MADCAP requires less time and space to achieve comparable orbetter approximate solutions than the current state-of-the-art ADD-based ADP algorithm of APRICODD and can provide approximatesolutions for problems with context-specific, additive and multiplicative structure on which APRICODD runs out of memory.

Authors

• Scott Sanner Department of Mechanical and Industrial Engineering, University of Toronto Vector Institute for AI
• William Uther
• Karina Valdivia Delgado

Keywords

No keywords are indexed for this paper.