Search papers, labs, and topics across Lattice.
This paper addresses the challenges of model-free reinforcement learning for co-safe linear temporal logic (sc-LTL) objectives in finite Markov decision processes, which often struggle with convergence due to the noncontractive nature of the Bellman equation. The authors introduce a novel two-step method that first identifies a clamp set using a discounted surrogate, which resolves the nonuniqueness issue, followed by undiscounted policy evaluation and greedy improvement. Their approach guarantees almost-sure convergence and finite termination at an optimal policy, validated through experiments in a stochastic grid world.
A new two-step method for model-free reinforcement learning guarantees optimal policy convergence for co-safe LTL objectives, overcoming significant challenges in traditional approaches.
This work studies model-free reinforcement learning for co-safe linear temporal logic (sc-LTL) objectives in finite Markov decision processes, which can be reduced to maximal reachability objectives via the standard product construction. For this problem, direct sample-based bootstrap methods (e.g., TD or Q-learning) may fail to converge to optimal policies due to the noncontractive nature and nonuniqueness of solutions to the Bellman equation. We develop a new two-step model-free reinforcement learning method that first uses a discounted surrogate to identify a clamp set that resolves this nonuniqueness, and then applies undiscounted policy evaluation and greedy policy improvement with guarantees of finding an optimal solution. We prove almost-sure convergence of the policy evaluation step and finite termination of the policy iteration algorithm at an optimal policy. These theoretical results are validated through numerical experiments on a stochastic grid world.
