{"ID":2898993,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.01324","arxiv_id":"2507.01324","title":"An Error Bound for Aggregation in Approximate Dynamic Programming","abstract":"We consider a general aggregation framework for discounted finite-state infinite horizon dynamic programming (DP) problems. It defines an aggregate problem whose optimal cost function can be obtained off-line by exact DP and then used as a terminal cost approximation for an on-line reinforcement learning (RL) scheme. We derive a bound on the error between the optimal cost functions of the aggregate problem and the original problem. This bound was first derived by Tsitsiklis and van Roy [TvR96] for the special case of hard aggregation. Our bound is similar but applies far more broadly, including to soft aggregation and feature-based aggregation schemes.","short_abstract":"We consider a general aggregation framework for discounted finite-state infinite horizon dynamic programming (DP) problems. It defines an aggregate problem whose optimal cost function can be obtained off-line by exact DP and then used as a terminal cost approximation for an on-line reinforcement learning (RL) scheme. W...","url_abs":"https://arxiv.org/abs/2507.01324","url_pdf":"https://arxiv.org/pdf/2507.01324v2","authors":"[\"Yuchao Li\",\"Dimitri Bertsekas\"]","published":"2025-07-02T03:17:28Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"eess.SY\"]","methods":"[\"Reinforcement Learning\"]","has_code":false}