Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918520005066752 |
|---|---|
| author | Palasamudram, Amogh Svoboda, Jakub Bansal, Suguman Chatterjee, Krishnendu |
| author_facet | Palasamudram, Amogh Svoboda, Jakub Bansal, Suguman Chatterjee, Krishnendu |
| contents | Reinforcement learning (RL) for reachability specifications is fundamental in sequential decision-making, yet theoretical guarantees remain less explored. A recent work achieves asymptotic convergence to optimal policies. However, this approach provides limited insight into convergence dynamics. In this work, we present an alternative approach that provides deeper theoretical insights into convergence. Our approach builds on PAC learning with assumptions. PAC learning guarantees near-optimal policies with high confidence in finite time but requires knowing internal MDP parameters like minimum transition probability. We argue that while these parameters are unknown in RL, they can be iteratively refined and estimated with increasing accuracy. By iteratively satisfying PAC conditions, we show that exact optimality can be achieved in the limit. Empirical evaluations on standard benchmarks validate our theoretical insights into convergence dynamics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_24740 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality Palasamudram, Amogh Svoboda, Jakub Bansal, Suguman Chatterjee, Krishnendu Machine Learning Computer Science and Game Theory 68Q32 I.2.6 Reinforcement learning (RL) for reachability specifications is fundamental in sequential decision-making, yet theoretical guarantees remain less explored. A recent work achieves asymptotic convergence to optimal policies. However, this approach provides limited insight into convergence dynamics. In this work, we present an alternative approach that provides deeper theoretical insights into convergence. Our approach builds on PAC learning with assumptions. PAC learning guarantees near-optimal policies with high confidence in finite time but requires knowing internal MDP parameters like minimum transition probability. We argue that while these parameters are unknown in RL, they can be iteratively refined and estimated with increasing accuracy. By iteratively satisfying PAC conditions, we show that exact optimality can be achieved in the limit. Empirical evaluations on standard benchmarks validate our theoretical insights into convergence dynamics. |
| title | Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality |
| topic | Machine Learning Computer Science and Game Theory 68Q32 I.2.6 |
| url | https://arxiv.org/abs/2605.24740 |