非马尔可夫强化学习：马尔可夫抽象的自动机学习方法

+v：mala2277获取更多论文非Markov决策过程Alessandro Ronca， Gabriel Paludo Licks， Giuseppe De GiacomoDIAG，罗马Sapienza大学，意大利{ronca，licks，degiacomo} @ diag.uniroma1.it摘要我们的工作旨在开发不依赖于马尔可夫假设的强化学习算法。我们考虑一类非马尔可夫决策过程，其中历史可以抽象成一个有限的状态集，同时保持动态。我们称之为马尔可夫抽象，因为它在编码非马尔可夫动态的一组状态这种现象是最近引入的规则决策过程（以及POMDP，其中只有有限数量的信念状态是可达到的）的基础在所有这些类型的决策过程中，使用马尔可夫抽象的代理可以依靠马尔可夫属性来实现最佳行为。我们证明了马尔可夫抽象可以在强化学习过程中学习。对于这两个任务，可以采用满足一些基本要求的任何算法。我们表明，我们的方法有PAC的保证时，所采用的算法有PAC的保证，我们还提供了一个实验评估。1介绍认为世界有一个当前的状态是一个有用的抽象的代理。可以根据这种状态做出决定。事实上，在强化学习（RL）的经典设置中，智能体被提供了当前状态[Sutton和Barto，2018]。这是在马尔可夫假设下的强化学习，我们称之为马尔可夫强化学习。在一个更现实的场景中，智能体没有被赋予当前状态，但可以简单地观察到对其行为的反应。我们称之为非马尔可夫RL。同样在这种情况下，代理可以尝试重新获得有用的状态抽象。然而，现在必须学习抽象，作为从代理人观察到的每个历史到代理人发明的某个状态的映射[Hutter，2009]。我们提出RL代理，学习一种特定的抽象称为马尔可夫抽象的一部分，整个学习过程。我们的方法以模块化的方式结合了自动机学习和马尔可夫RL，马尔可夫抽象作为两个模块之间的接口我们表明如何在学习过程中建立的中间自动机序列诱导部分马尔可夫抽象，可以很容易地我们的方法是可能近似正确（PAC）。[Valiant，1984]，无论何时，对于所采用的自动机和马尔可夫RL算法也是如此。通过引入马尔可夫属性保持的状态空间来解决非马尔可夫任务的想法已经可以在[Bacchuset al. ，1996]和最近在[Braf-manet al. ，2018;Icarteet al. ，2018]。在这种情况下，RL 已被考 虑[Icarteet al. ，2018; DeGiacomo etal. ，2019;Gaon and Brafman，2020;Xuet al. ，2020]。此设置比我们的更简单，因为过渡仍然被假设为成为 马 尔 科 夫 在 [Icarteet al. ， 2019;Brafman 和 DeGiacomo，2019]，RL研究在[Icarteet al. ，2019;Abadiand Brafman，2020;Ronca and DeGi-acomo，2021].这种RL技术基于自动机学习。[Ronca和De Giacomo，2021]中的方法带有PAC保证，而不是其他没有的我们的方法扩展了[Ronca和DeGiacomo，2021]中的技术，以便使用学习的自动机不仅构建最终策略，而且还指导探索。从历史到状态的抽象已经在[Hutter，2009;Maillardetal.， 2011;Venessetal.， 2011;Nguyenetal.，2013;Latestivalet al. ， 2013;Hutter ， 2016;Majeed andHutter，2018]。[Hutter，2009]介绍了从历史到状态的抽象概念。它的算法解决方案，以及一个在[Venessetal. ，2011]，比我们的更不一般，因为它假设了要考虑的历史长度的界限。这对应于自动机的一个子类。[Maillardet al. ，2011]提供了一种从给定的候选抽象的有限集合中选择抽象的技术;相反，我们考虑抽象的无限集合。[Nguyenetal. ，2013]考虑了一组抽象，而不承诺表示它们的特定方式。因此，他们不能利用所选择的表示形式主义的特定属性，在算法中也不是在分析中。相反，我们选择了自动机，这使得我们能够利用现有的自动机学习技术，特别是它们的属性，如增量结构。[Lattanet al. ，2013]研究了非马尔可夫决策过程属于紧类的情况下的非马尔可夫RL。他们的结果并不适用arXiv：2205.01053v1 [cs.LG] 2022年4月+v：mala2277获取更多论文∈∈⊆≥PH ××H × {}EHH × {}Σ|·你好ApoliccypuzzlePPPPΣΣ|∈EΣ|·你知道吗？an的值| |P||·|||·|·|PP−⟨⟩一×→∈∈∈−∈·|∪∈×∪→×→我们的情况下，因为类的决策过程承认马尔可夫抽象是不紧的。[Majeed and Hut-ter，2018]研究了具有抽象的Q学习，但它假设抽象是给定的。[Hutter，2016]提供了我们在第3节中使用的结果;然而，不需要任何一个马尔可夫抽象来保持动态，因为我们需要我们的马尔可夫抽象。即使在所谓的“精确状态聚合”的情况下2预赛对于x和z字符串，xz表示它们的连接。对于和Γ字母表，Γ表示具有σ和γΓ的所有字符串σγ的集合。对于f和g函数，fg表示它们的合成。我们写f：X~Y来表示函数f：X×Y→[0，1]，其定义概率分布f（·|x）在Y上对每个x ∈X.非马尔可夫决策过程非马尔可夫决策过程（NMDP）[Brafman and De Giacomo，2019]）是一个元组=A，O，R，R，T，R，其组件定义如下。A是一个有限的行动集，O是一个有限的观察集，RR0是一个有限的非负回报集，R是一个特殊的符号，表示情节终止。 让=（AOR）的元素称为历史，并让的元素=（AOR）A称为episodes。 然后，T：A ~（O其中，R是过渡函数，R：一O ~ R是奖励函数。 转换和奖励函数可以组合到动态函数D中：A ~（或它描述了下一对观测的概率或者奖励，或者终止，给予一定的历史和行动。即，D（或|h，a）=T（o|h，a）·R（r|h，a，o）和D（n|h，a）=T（λ|h，a）。我们经常直接把一个字母写为A，O，R，，D。一个策略是一个函数π：H~A。到目前为止的历史是h;它是qπ（h，a）=或D（o，rh，a）（r +vπ（haor））。给定历史h，动作a的最优值为q（h，a）=maxπqπ（h，a），它可以表示为q（h，a）=或D（o，r|h，a）·（r + v（haor））π是最优的，如果vπ（ε）=v<$（ε）。 对于π>0，策略π是n-最优的，如果vπ（ε）≥v<$（ε）−<$。马尔可夫决策过程马尔可夫决策过程（Markov DecisionProcess，MDP）[Bellman，1957;Puterman，1994]是一种决策过程，其中转移和奖励函数（以及动态函数）仅取决于历史中的最后一次观察，当历史为空时，将其视为任意观察。因此，观察是对事态的完整描述，习惯上称之为强调这一方面的状态。因此，我们用一组状态S来代替一组观测值O。所有历史相关函数，例如，转换和回报函数、动态、价值函数、策略--可以被看作是采用单个状态来代替历史。情节RL。给定一个决策过程和所需的准确度θ>0，情景强化学习（RL）和θ是一个代理的问题，它必须从它通过与环境交互收集的数据中学习一个最优策略互动在于代理人迭代地执行动作并作为响应接收观察和奖励，直到情节终止。具体地，在步骤i，代理根据决策过程的动态执行动作ai，接收一对观察oi和奖励ri或终止符号ri这个过程产生了一个a1o1r1a2o2r2形式的插曲。. . a n. 这些情节的集合是可供代理学习的数据。PAC为RL提供担保。关于描述决策过程的复杂性的给定数值参数集给出保证-例如，行动的数量，观察的特别是，对于每一个决定亲，统一策略πu是定义为πu（a）的策略|h）=对于P，我们有一个参数值的列表→c。一个1/A对于每个a和每个h。的动态下策略π描述了当根据策略π选择行动时，给定到目前为止的历史，事件剩余的概率;它可以递归地计算为Dπ（aore h）=π（a h）D（or h，a）Dπ（e haor），基本情况Dπ（a h）=π（a h）D（a h，a）。由于我们研究的是情景强化学习，我们要求情景以概率1终止，即，e 对于每个策略π，Dπ（e ε）=1。1这个要求确保了下面的值函数取一个有限值。在给定的条件下，历史h，写为vπ（h），是当根据π选择动作时，给定到目前为止的历史是h时，未来回报的期望总和;它可以递归地计算为vπ（h）=aorπ（a|h）·D（o，r|h，a）·（r+vπ（haor））. 任务-给定历史h的时间值为v（h）=maxπvπ（h），可以在不参考任何策略的情况下表示为v（h）=maxa（或D（o，r h，a）（r+v（haor）在给定历史h的策略π下的动作a，记为qπ（h，a），是当下一个行动是a和以下动作根据π选择，给定[1]在每一步终止的恒定概率p等于贴现因子1−p，参见[Puterman，1994]。RLagent对一类决策过程有PACguarantees，如果对任意给定的p>0和0< δ<1，存在多项式函数poly，使得对于该类中的每一个决策过程，agent有至少1 δ的概率使用由poly（→cP，1/p，ln（1/δ））渐近有界的事件数和计算步骤来解决和n的事件RL问题.自动机概率确定有限自动机（PDFA）（参见 [Balle etal. 、 2014]）是元组=Q，r，r，τ，λ，q0，其中：Q是状态的有限集合; r是有限字母表;r是不在r中的终止符号的有限集合;τ：Q=Q是（确定性）转移函数; λ：Q（r）[0，1]是概率函数，其定义了每个状态q Q在r上的概率分布λ（q）; q0Q是初始状态。迭代转移函数τ：QQ被递归地定义为τ（q，σ1. . . σ n）=τn（τ（q，σ1），σ2. . . σ n），且基本情形为τ（q，ε）=q;进一步，τ（w）表示τ（q0，w）. 对于每个状态q Q，都存在一个序列σ1，. . .，σ n，使得λ（τ∈（q，σ1. . . σi1），σ i）>0，且λ（τ（q，σ1. . .对于γ r-，σ n），γ）>0 ，以确保每个字符串以概率1终止。给定+v：mala2277获取更多论文·|·|H →|−Σ∈|−HΣP联系我们·|PD（C）|h，a）=xB（x|h）·O（OH|x，a）。政策和价值函数-一个字符串x ∈ N，该自动机表示概率分布A（·|x）在递归定义为A（σy）的环上|x）=λ（τ（x），σ）· A（y|xσ），基本情况为A（γ|x）=λ（τ（x），γ）.3马尔可夫抽象直接操作历史记录是不可取的。在情节长度中存在指数级多个历史，并且典型地每个历史被观察几次，这不允许计算准确的统计。这个问题的一个解决方案是将历史抽象为一组合理大小的状态，同时保持动态。我们修复NMDPP=A，O，R，D.定义1.有限状态集S上的马尔可夫抽象是一个函数α：S，使得对于每两个历史h1和h2，α（h1）=α（h2）意味着对于每个动作a，D（h1，a）=D（h2，a）。给定一个抽象α，它的重复应用α通过用相应的状态替换观测来转换给定的历史，如下所示：α 1（a1o1r1. . . anonrn）=s0a1s1r1。 . . 一个nsnrn，其中s=α（h）且h=a或r。. .阿尔河图1：上面是目标自动机，下面是假设自动机实边表示输入1的转换，虚边表示输入0的转换。POMDPs。部分可观测马尔可夫决策过程（POMDP）。[Kaelbling et al. ，1998]，是元组P =我我我1 1 1我我我其中：A，O，R，X，现在考虑通过边缘化获得的概率Pα（si，ri hi1，ai）为：NMDP：X是隐态的有限集，T：X×A~X是转移函数，R：X×A×O~ R是回报函数，O：X × A × ~（O≠ {R}）是观测函数，T：X × A ~X是转移函数，O：X×A×~（O≠ {R}）是观测函数。P α（si，ri|h i−1，a i）=o：α（hi−1aio）=siD（o，r i|hi−1，a i）.vation函数; x0X是初始隐藏状态。为了定义动力学函数-即，描述了下一对观测概率由于动态D（o，rih i1，ai）对于映射到相同状态的每个历史都是相同的，所以存在具有动态D α的MDP Mα，使得P α（s iri|h i−1，a i）=Dα（s i r i|α（h i−1），a i）. 导出的MDP Mα可以代替P求解。实际上，一个状态中的动作的值是以及奖励或终止，给出了观察和动作的特定历史-它需要引入置信函数B：~X，其描述了给定当前历史处于特定隐藏状态的概率。然后，动力学函数可以用置信函数表示，映射到该状态的任何历史中的操作的值[Hutter，2016，Theorem 1]. 特别地，如果π是一个π-最优的，作为D（或|h（a）= xB（x|h）·O（o|x，a）·R（r|x，a，o）和策略，则πα是P的最优策略。3.1决策过程我们讨论如何马尔可夫抽象与现有的决策过程类。MDP。MDP可以被描述为NMDP类，其中历史可以抽象为它们的最后一次观察。也就是说，他们承认α（haor）=o是一个马尔可夫抽象。RDP。规则决策过程（RDP）可以根据有限迹LDLf上的时间逻辑[Braf-man和De Giacomo，2019]或根据有限换能器[Ronca和De Giacomo，2021]来定义。前一种情况下减少到后者的LDLf和有限自动机之间的著名的对应关系。就有限换能器而言，RDP是NMDP =A，O，R，N，D其动力学函数可用有限变换器T表示，T在每个历史h上输出函数Dh：A ~（ORζ）当它的第一个参数是h时由D诱导。在这里，我们观察到T的转移函数的迭代版本是马尔可夫抽象。因此，最优性的概念与NMDPs一样。对于每个历史h，隐藏状态上的概率分布B（h）被称为置信状态。从上面给出的动力学函数的表达式中可以清楚地看出下面的定理。定理1. 如果POMDP具有有限的可达置信状态集，则将每个历史映射到其置信状态的函数是马尔可夫抽象。4我们的非马尔可夫RL我们的方法将自动机学习与Markov RL相结合。我们首先分别描述这两个模块，然后提出结合它们的RL算法。对于这一节，我们固定NMDP=A，O，R，R，D，并假设它允许状态S上的马尔可夫抽象α。4.1第一个模块：自动机学习马尔可夫抽象可以通过自动机学习，由于以下定理。+v：mala2277获取更多论文×→⟨⟩P|·||·|一M≥A ≤ A A A.A.· ||AA一 · · ·≤AAA定理2. 过渡函数τ：SAORS和初始状态s0存在，使得对于S上的每个马尔可夫策略π，的动态Dπα对于某个概率函数λ由自动机S，AOR，A π，τ，λ，s0表示。此外，τ= α。素描证明。初始状态是s0=α（ε）。转移函数定义为τ（s，aor）=α（hs aor）其中hs是任意选择的历史，使得α（hs）= s。 显然τ =α。然后，概率函数被定义为λ（s，aor）=π（a s）D（或h s a）和λ（s，a r）=π（a s）D（h s a）。 可以通过归纳证明，由此产生的自动机捕获了Dπα与代表性历史hs的选择无关，因为映射到相同状态的所有历史确定相同的动力学函数。我们提出了一个通用的PDFA学习算法的非正式描述，捕捉的基本特征的al-计算时间以样本和目标自动机的大小为界。由于假设自动机i包含候选状态，这些候选状态没有输出转移，因此作为其转移函数的迭代τi获得的马尔可夫抽象α i不是完全的马尔可夫抽象，而是部分的马尔可夫抽象。 因此，αi诱导的MDPi也是部分的. 具体地说，它包含不能继续的状态，这些状态来自候选节点。4.2第二个模块：Markov RL当马尔可夫RL代理被限制在MDP状态的子集S'第一个结果是它可以找到一个对整个MDP接近最优的策略，忽略不在S′中的状态。否则，有一个政策，导致一个在S'中的状态不足够频繁。这是第一次。[在[Ronet al. ，1998;Clark和Thol-探索或利用引理 Kearns和Singh，2002年]。lard ， 2004;Palmer and Goldberg ， 2007;Balleet al. ，2013;Balleet al. ，2014]。我们将强调对RL算法的其余部分有影响的特征。为了帮助演示，请考虑图1。该图显示了一个目标自动机的过渡图，以及到目前为止由算法构建的假设图。在假设图中，我们区分了安全和候选。安全节点在图中它们与目标中的节点一一对应，它们定义了所有转换，并且不会更改。候选节点是图中的正方形。它们的转换没有定义，因此它们形成了图的学习部分的边界。通过提升或合并候选项来扩展图。如果假设检验出候选节点对应于假设中还没有安全节点的目标节点，则将其提升为安全节点。在提升时，为来自刚提升的安全节点的每个可能的转换这有效地扩展了自动机，推动了边界。如果算法测试到候选节点等同于假设中已经存在的安全节点，则通过删除它并将其所有传入边重定向到安全节点，将其合并到安全节点中。因此，算法的统计核心在于测试。两个节点之间的测试基于具有分别映射到这两个节点的前缀的输入字符串。假设所有的测试都产生正确的结果，很容易看出从每个假设图到下一个假设图以及到目标图都存在同态我们表示同态的存在性，1至2作为12、作为12.另外，表示两个自动机是不同的。 综上所述，我们期待以下几点--在自动机学习算法的运行中降低保持的条件。条件1. 自动机学习算法建立假设1，. . .，n，使得以下条件成立：（健全性）1n; （ 完 备性）存在K 0，使得每个候选者s在具有映射到s的前缀的K个字符串内被提升或合并;（有界性）曾经创建的节点的数量至多是n× n，用于表示输入字母表，n是目标的状态的数量;（计算成本）该属性在E3算法中显式使用[Kearns和Singh，2002]，在RMax等算法中更隐式地使用[Brafman和Tennenholtz，2002]。总结一下，我们将依赖于以下条件为真。条件2. 两个条件：（探索或利用）在一定数量的情节N，要么智能体找到一个最优策略或访问一个候选状态K次;（计算成本）处理情节的计算时间是有界的情节和底层MDP的大小。因此，我们将有一个马尔可夫代理在部分抽象诱导的MDP中运行，以便找到一个接近最优的策略（当抽象足够完整时）或访问候选状态（收集字符串以扩展抽象）。我们不假设Markov RL al-taxms本身能够以在线方式处理底层MDP当发生变化时，我们可以重新启动马尔可夫RL算法。然而，更有效的技术是可能的。如果马尔可夫RL算法是基于模型的，即，它估计动态函数，然后当候选者被提升时，它不需要做任何事情，并且它可以通过将合并状态的统计信息合并到我们合并到的安全状态的统计信息中来重新计算统计信息4.3总体方法算法1使用AutomataLearning和MarkovRL模块来解决非马尔可夫RL。它从一个空的抽象α（第1行）开始，然后循环，每次迭代处理一个事件。第3行对应于一个情节的开始，因此算法设置当前的his-历史的空洞。第4-8行具体来说，首先向代理第9-12行处理插曲的剩余部分，我们还没有抽象。首先，根据统一策略πu（第10行）选择一个动作，该动作是然后执行（第11行），并扩展当前历史记录+v：mala2277获取更多论文←←←←→P← ∅||· | | ·| | ·||算法1：NonMarkovRL1α;2环3h ε;4当α（h）是安全的，发作未结束时，5aMarkovRL。return（）;6o，r执行动作a;7MarkovRL. 观察（α（h），a，r，α（haor））;8小时←haor;第9集还没结束呢10a←根据πu选择一个动作;11o，r←执行动作a;12h←haor;13α，m自动学习。return（h）;14MarkovRL. return（m）;（第12行）。第13在第13行中，自动机学习算法被赋予情节，并且它返回可能更新的抽象α以及函数m：S指定候选项合并到安全的国家。最后，在第14行中，马尔可夫代理被赋予合并函数m，它可以用来更新模型或决定重新启动。算法的正确性和性能遵循关于模块的条件1和条件2。定理3. 如果满足条件1和条件2，则算法1使用模块所花费的时间加上事件长度之和的时间多项式，并且使用以下量，在N S AOR事件内找到最优策略：|S|、|一|、|O|、|R|.证据该算法的执行可以分成多个阶段，每个假设自动机有一个阶段在有界条件下，最多存在S AOR阶段. 考虑一个任意的阶段。在N个情节中，马尔可夫代理要么利用，要么探索。如果它利用，即，它为当前部分抽象αi所导致的MDP找到一个π-最优策略π，则παi是π-最优的。关于计算时间，请注意，算法在每个事件中执行一次迭代，它在每次迭代中对一个事件进行操作，并且抽象可以在时间多项式中进行评估，|S|以及剧集长度。该 定 理 直 接 意 味 着 ， 当 我 们 有 条 件 1 和 条 件 2 的guarantees满足一定的概率，保证我们的算法成立。推论1（PAC）。 如果条件1和条件2以至少1-δ的概率满足，并且模块的每个调用都需要一些量C的时间多项式，则以至少1-δ的概率，算法1在N内找到最优策略。|S| · |AOR|情节，在C中的量中使用时间多项式，在情节长度的总和中，以及在|S|、|一|、|O|、|R|.5实证评价我们展示了一个实验评估非马尔可夫rein-person学习与马尔可夫抽象。2我们采用最先进的流PDFA学习算法[Balleet al. ， 2014] 用 于 自 动 机 学 习 模 块 ， RMax[Brafman 和Tennenholtz，2002]代理用于Markov RL模块。流PDFA学习器和RMax算法都有PAC保证;可以说它们在运行中以很高的概率满足条件1和2我们显示在各种领域的结果。 我们包括[Abadi和Brafman，2020]中介绍的域：旋转MAB、故障MAB、欺骗MAB和旋转迷宫。我们包括[Ronca和De Giacomo，2021]中介绍的敌人走廊域。我们包括两个新的领域：旋转MAB的第二个版本，和闪烁的网格。所有这些都是非马尔可夫域，其中最优的搜索需要学习对过去的依赖性。我们在附录B中描述了每个域。域由k参数化，这使得域更复杂，因为它被分配了更大的值。图2显示了我们在所考虑的领域中的性能评估。图包括三种不同的方法。首先，我们展示了我们的方法，称为RMax抽象，即，马尔可夫抽象提供的RMax马尔可夫代理。其次，我们展示了一种随机抽样方法，与[Ronca和De Giacomo，2021]中提出的方法相当，即，一种类似于本文中提出的方法，但是依赖于随机均匀采样的历史。最后，我们将RMax代理作为这些领域中纯马尔可夫代理的性能的基线，而不依赖于马尔可夫抽象。每种方法的结果在5次训练中取平均值，并显示标准偏差。在每次训练中，每15k训练集对智能体进行评估。每个评估是50集的平均值，其中对于每个集，我们测量的是奖励除以所采取的步骤数。请注意，代理在尚未定义马尔可夫抽象的历史上随机一致地采取行动，否则根据价值函数随机采取行动。我们在图2a-2g中报告的结果表明，我们的方法在除旋转迷宫和故障MAB之外的所有领域都收敛。在这两个领域中的低性能的来源是由于流PDFA学习算法所使用的可扩展性参数。可预测性的值根据预测所需的步骤数量而减少，以声明两个状态是否表示相同的分布。虽然流PDFA学习算法保证找到正确的模型，但较低的可扩展性值需要2本文中显示的结果是可重复的，我们的实验定义在源代码中提供，以及精确的参数和随机种子来重现结果，以及具有所有代码要求的虚拟环境。我们的实验是在运行Ubuntu 18.04.5LTS的服务器上进行的，具有512 GB RAM和80个核心型号Intel Xeon E5-2698 2.20GHz。每个训练运行需要一个核心，所需的计算量和时间主要取决于为训练设置的剧集数量。+v：mala2277获取更多论文k=3 RMaxk=3随机k=3 RMax抽象k=5RMaxk=5随机k=5 RMax抽象k=8 RMaxk=8随机k=8 RMax抽象k=2 RMaxk=4 RMaxk=8 RMaxk=16 RMaxk=32 RMaxk=64 RMaxk=2随机k=4随机k=8随机k=16 随机k=32 随机k=64 随机k=2 RMax抽象k=4RMax抽象k=8 RMax抽象k=16 RMax抽象k=32RMax抽象k=64 RMax抽象Rmax随机RMax抽象平均报酬75809017.570708065607060506015.012.510.05040300 1 2 3 4 5 67Epperimeter（单位=105）(a) 旋转MAB555045400 1 2 3 4Epperimeter（单位=105）(b) MAB故障4030200 5 10 15 20 2530Epperimeter（单位=105）(c) 作弊MAB7.55.02.50.00 2 4 6 810121416Epperimeter（单位=105）(d) 旋转迷宫908080707017.515.0 3012.52010.06050607.5105.0402.5050300.00 10 20 30 4050Epperimeter（单位=105）0 255075100125埃普利（单位=103）1501750 2 4 6 8 10 1214Epperimeter（单位=105）100 2 4 6 8 10Epperimeter（单位=105）(e) 旋转MAB v2(f) 敌人走廊(g) 闪烁网格(h) 安全州与候选州图2：马尔可夫抽象的经验评估。更高的样本量，以便正确地区分状态，因为对区分历史进行采样的机会在每一步呈指数下降。总体而言，流PDFA学习器能够在区分度较高的域中快速学习，例如旋转MAB、敌人Corridor和闪烁网格。我们表明，无论域的大小如何，我们的方法都可以在可扩展性高的域中扩展，特别是在敌人走廊域中（图2f），我们能够在k=[2，4，8，16，32，64]的范围内增加走廊大小。相比之下，dom抽样方法[Ronca和De Giacomo，2021]，我们表明使用更智能的探索策略在具有终端状态的域中学习时有益，即，旋转迷宫和闪烁网格，目标是代理必须到达的坐标。在马尔可夫抽象仍在学习的同时，更聪明的探索有助于收集与当前目标相关的学习状态的信息片段。在其他域上，随机采样方法的性能接近或等同于RMax 抽 象（ 其 中 一条 线 在某 个 点处 与 另 一条 线 重叠），但是它并不优于RMax抽象。在图2h中，我们绘制了安全状态的数量与候选状态的数量，其中代理在闪烁网格域中训练期间在每个事件中访问。该图清楚地说明了学习马尔可夫抽象的增量过程，因为候选状态的数量在第一集期间很高，并且随着收集更多的历史和通过流PDFA学习算法学习更多的安全状态而随着时间的推移而减少。一旦抽象足够完整，它提供了必要的状态，使智能体朝着目标前进，智能体收敛并停止访问候选状态。我们尝试与[Abadi和Brafman，2020]进行比较。作者介绍了一种方法，结合自动化学习与历史聚类，建立一个Mealy机器，代表了潜在的决策过程，而采用MCTS来计算用于所学习的模型的策略在他们的工作中，报告了旋转MAB、故障MAB、欺骗MAB和旋转迷宫域的结果。我们从作者那里获得了原始代码，并试图重现其结果。成功再现了旋转MAB的结果，但未再现其余区域的结果。用于产生论文中报告的结果的参数没有公布，也没有在源代码中提供，除了在代码中没有设置随机种子之外。由于运行代码所需的计算时间，参数搜索也是不切实际的，特别是当来自环境的样本数量增加总的来说，我们决定不在我们的图中包含不完整的数据。从原始论文中报告的图来看，我们的方法在收敛前所需的环境样本数量方面然而，他们的方法仅限于较小的剧集长度，如[Ronca和DeGiacomo，2021]的附录C所示，说明了敌人走廊域的情况。 我们已经进行了比较的方法[Icarte等人。，2019]，也基于自动机学习。作者提供了源代码，他们的结果是可重复的。我们不能在他们的论文中提出的域中收敛，以及他们不能在我们在本文中显示的域中收敛。禁忌搜索，作者用于学习奖励机器的方法，高度依赖于状态的数量和每个状态的可能转换，即，在旋转迷宫中运行禁忌搜索在计算上是不切实际的，因为这个域有192个状态，而他们的论文中介绍的域需要少于10个状态的机器。最后，实验评估表明，该方法的可行性。与随机探索基线的比较显示了基于自动机的智能探索的优势，的k=2 RMaxk=2随机k=2 RMax抽象k=4RMaxk=4随机k=4 RMax抽象k=6RMaxk=6随机k=6 RMax抽象k=3 RMaxk=3随机k=3 RMax抽象k=4RMaxk=4随机k=4 RMax抽象k=1 RMaxk=2 RMaxk=3 RMaxk=1随机k=2随机k=3随机k=1RMax 抽 象 k=2RMax抽象k=3 RMax抽象候选国安全状态平均报酬平均报酬平均报酬平均报酬平均报酬情节长度平均报酬+v：mala2277获取更多论文MAB域突出了学习的困难时，distinguishability是低的问题，底层自动机学习算法。与此同时，敌人走廊显示了良好的可扩展性的整体方法时，可分辨性仍然很高。与最新技术水平的比较仅部分可行，因为我们无法重现[Abadi和Brafman，2020]中的结果。根据已经发表的评价，我们的方法在它们的领域中的性能较差。然而，有理 由 相 信 ， 这 将 超 过 他 们 在 敌 人 走 廊 的 做 法 。 与[Icarteet al. 2019年]表明，这两种方法都不比另一种更好。我们的算法的可扩展性很低，而他们的算法的禁忌搜索性能变化很大。致谢这 项 工 作 得 到 了 ERC 高 级 资 助 WhiteMech （ 编 号834228 ） 、 欧 盟 ICT-48 2020 项 目 TAILOR （ 编 号952215）、PRIN项目RIPER（编号20203 FFYLK）和摩根大通人工智能学院研究奖“基于弹性的广义规划和战略推理”的部分支持引用[阿巴迪和布拉夫曼，2020年]伊登阿巴迪和罗恩我。布拉夫人。学习和解决常规决策过程。在IJCAI，2020年。[Bacchus et al. Fahiem Bacchus ， Craig Boutilier ， andAdam J. Grove.奖励行为。在AAAI，1996年。[Balle et al. Borja Balle，Jorge Castro，and Ricard G avald a`. 学习概率自动机：状态可重复性研究Theor.Comput. Sci. ，2013年。[Balle et al. Borja Balle，Jorge Castro，and Ricard G avald a`. 从数据流中自适应学习概率确定马赫学习. ，2014年。[贝尔曼，1957年]理查德贝尔曼。马尔可夫决策过程J.Math. Mech. ，1957年。[Brafman和De Giacomo，2019] Ronen I.布拉夫曼和朱塞佩·德·贾科莫。Regular Decision Processes：A Modelfor Non-Markovian Domains.在IJCAI，2019年。[Brafman and Tennenholtz，2002] Ronen I.布拉夫曼和摩西Tennenholtz。R-MAX：一种近似最优强化学习的通用多项式时间算法。JMLR，2002年。[Brafman et al. ，2018] Ronen I.布拉夫曼，朱塞佩·德·吉亚科莫，法比奥·帕特里齐. LTLf/LDLf非马尔可夫回报。在AAAI，2018年。[Clark and Thollard ， 2004] Alexander Clark and FranckThollard.概率确定有限状态自动机的PAC可学习性。J·马赫。学习. Res. ，2004年。[De Giacomo et al. Giuseppe De Giacomo，Luca Ioc-chi，Marco Favorito，and Fabio Patrizi.约束螺栓的基础：使用LTLf/LDLf约束规范的强化学习在ICAPS，2019年。[Gaon和Brafman，2020] Maor Gaon和Ronen I。布拉夫人。非马尔可夫奖励强化学习。在AAAI，2020年。[Hutter，2009] Marcus Hutter.特征强化学习：第一部分。非结构化MDPs。 J. 第将军内特尔，2009年。[Hutter，2016] Marcus Hutter马尔可夫决策过程的极端状态聚合。Theor. Comput. Sci. ，2016年。[Icarte et al. Rodrigo Toro Icarte ， Toryn Q. Klassen ，Richard Anthony Valenzano，and Sheila A.麦克莱斯在强化学习中使用奖励机进行高级任务规范和分解。2018年在ICML[Icarte et al. ，2019] Rodrigo Toro Icarte，Ethan Waldie，To- ryn Q.Klassen ， Richard Anthony Valenzano ，Margarita P. Castro，and Sheila A.麦克莱斯学习奖励机器用于部分可观察强化学习。2019年在NeurIPS[Kaelbling et al. [Leslie Pack Kaelbling ， Michael L.Littman，and Anthony R.卡桑德拉在部分可观察的随机域中进行规划和行动。第内特尔，1998年。[Kearns and Singh，2002] Michael J. Kearns and SatinderP. Singh. 多项式时间内的近优强化学习马赫学习. ，2002年。[Lattan et al. Tor Latestival ， Marcus Hutter ， and PeterSunehag.一般约束学习的样本复杂性。InICML，2013.[Maillardetal. ，2011年]Odalric-Ambrym梅拉德我是穆诺斯和丹尼尔·里亚布科。强化学习中状态表示的选择. InNeurIPS，2011.[Majeed and Hutter ， 2018] Sultan Javed Majeed andMarcus Hutter.非马氏决策过程的Q-学习收敛性。在IJCAI，2018年。[Nguyenetal. 2013 年 ]Nguyen ， Odalric-AmbrymMaillard，Daniil Ryabko和Ronald Ortner。在强化学习中与无限的模型集InAISTATS，2013.[Palmer and Goldberg，2007] Nick Palmer and Paul W.戈德堡。概率确定有限状态自动机的变差距离PAC可学习性。Theor. Comput. Sci. ，2007年。[Puterman，1994] Martin L.普特曼马尔可夫决策过程：离散随机动态规划。Wiley，1994年。[Ron et al. Dana Ron，Yoram Singer，and Naftali Tishby.非循环概率有限自动机的可学习性和应用。J.计算机系统科学，1998年。[Ronca 和 De Giacomo ， 2021] Alessandro Ronca 和Giuseppe De Giacomo。常规决策过程中的高效PAC强化学习。在IJCAI，2021年。[Sutton和Barto，2018] Richard S.