Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality

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.

Reinforcement learning (RL) using logic specifications is essential for agents to make good decisions. Current algorithms require constraints or hidden knowledge of the environment/system to be effective. In our work, we introduce a different method that gives deeper mathematical insight into the learning progress. Our approach updates a standard framework called "probably approximately correct" (PAC) learning. This framework guarantees a near-perfect strategy within a fixed timeframe. However, it normally requires knowing hidden rules of the environment beforehand, such as the lowest possible odds of a specific event happening. We argue that even though these hidden rules are unknown at the start, our algorithm can estimate them and steadily improve its accuracy through practice. By repeatedly meeting the framework's conditions through these estimates, we prove that our algorithm eventually achieves absolute perfection. Testing our method on standard industry benchmarks confirms our mathematical insights regarding how the algorithm learns over time.