首个无遗憾的LTL控制算法，让系统在未知动态下高效学习正确行为。
Regret-Free Reinforcement Learning for LTL Specifications
- 基于马尔可夫决策过程建模未知系统，设计无遗憾在线学习算法。
- 首次提供有限学习次数后的性能逼近边界，而非仅渐近保证。
- 适合需要可靠学习过程的自动驾驶、机器人等安全关键场景。
在控制理论中，如何在未知动态系统上学习满足高层时序规范的控制器是一个重要问题。本文提出首个针对线性时序逻辑（LTL）规范的无遗憾在线学习算法，假设系统动态由有限状态与动作的马尔可夫决策过程（MDP）建模。核心成果是针对无限时域可达-避免问题的无遗憾学习算法。对于一般LTL规范，我们证明其合成问题可在已知图结构后转化为可达-避免问题。此外，我们还提供一种学习图结构的算法，前提是已知最小转移概率，且该算法独立于主无遗憾算法。所提的LTL控制器合成算法给出了在有限学习轮次后与最优行为的接近程度的精确界。相比之下，以往算法仅提供渐近保证，无法反映学习过程中的瞬时表现。
原文摘要 · Abstract (English)
Learning to control an unknown dynamical system with respect to high-level temporal specifications is an important problem in control theory. We present the first regret-free online algorithm for learning a controller for linear temporal logic (LTL) specifications for systems with unknown dynamics. We assume that the underlying (unknown) dynamics is modeled by a finite-state and action Markov decision process (MDP). Our core technical result is a regret-free learning algorithm for infinite-horizon reach-avoid problems on MDPs. For general LTL specifications, we show that the synthesis problem can be reduced to a reach-avoid problem once the graph structure is known. Additionally, we provide an algorithm for learning the graph structure, assuming knowledge of a minimum transition probability, which operates independently of the main regret-free algorithm. Our LTL controller synthesis algorithm provides sharp bounds on how close we are to achieving optimal behavior after a finite number of learning episodes. In contrast, previous algorithms for LTL synthesis only provide asymptotic guarantees, which give no insight into the transient performance during the learning phase.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。