An Error Bound for Aggregation in Approximate Dynamic Programming
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910191201550336 |
|---|---|
| author | Li, Yuchao Bertsekas, Dimitri |
| author_facet | Li, Yuchao Bertsekas, Dimitri |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_01324 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Error Bound for Aggregation in Approximate Dynamic Programming Li, Yuchao Bertsekas, Dimitri Optimization and Control Systems and Control 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. |
| title | An Error Bound for Aggregation in Approximate Dynamic Programming |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2507.01324 |