我们研究了设计AI代理商的问题,该代理可以学习有效地与潜在的次优伴侣有效合作,同时无法访问联合奖励功能。这个问题被建模为合作焦论双代理马尔可夫决策过程。我们假设仅在游戏的Stackelberg制定中的两个代理中的第一个控制,其中第二代理正在作用,以便在鉴于第一代理的政策给出预期的效用。第一个代理人应该如何尽快学习联合奖励功能,因此联合政策尽可能接近最佳?在本文中,我们分析了如何在这一交互式的两个代理方案中获得对奖励函数的知识。我们展示当学习代理的策略对转换函数有显着影响时,可以有效地学习奖励功能。
translated by 谷歌翻译
逆增强学习(IRL)是从专家演示中推断奖励功能的强大范式。许多IRL算法都需要已知的过渡模型,有时甚至是已知的专家政策,或者至少需要访问生成模型。但是,对于许多现实世界应用,这些假设太强了,在这些应用程序中,只能通过顺序相互作用访问环境。我们提出了一种新颖的IRL算法:逆增强学习(ACEIRL)的积极探索,该探索积极探索未知的环境和专家政策,以快速学习专家的奖励功能并确定良好的政策。 Aceirl使用以前的观察来构建置信区间,以捕获合理的奖励功能,并找到关注环境最有用区域的勘探政策。 Aceirl是使用样品复杂性界限的第一种活动IRL的方法,不需要环境的生成模型。在最坏情况下,Aceirl与活性IRL的样品复杂性与生成模型匹配。此外,我们建立了一个与问题相关的结合,该结合将Aceirl的样品复杂性与给定IRL问题的次级隔离间隙联系起来。我们在模拟中对Aceirl进行了经验评估,发现它的表现明显优于更幼稚的探索策略。
translated by 谷歌翻译
强化学习(RL)旨在在给定环境中从奖励功能中训练代理商,但逆增强学习(IRL)试图从观察专家的行为中恢复奖励功能。众所周知,总的来说,各种奖励功能会导致相同的最佳政策,因此,IRL定义不明。但是,(Cao等,2021)表明,如果我们观察到两个或多个具有不同折现因子或在不同环境中起作用的专家,则可以在某些条件下确定奖励功能,直至常数。这项工作首先根据等级条件显示了表格MDP的多位专家的等效可识别性声明,该声明易于验证,也被证明是必要的。然后,我们将结果扩展到各种不同的方案,即,在奖励函数可以表示为给定特征的线性组合,使其更容易解释,或者当我们可以访问近似过渡矩阵时,我们会表征奖励可识别性。即使奖励无法识别,我们也提供了特征的条件,当给定环境中的多个专家的数据允许在新环境中概括和训练最佳代理。在各种数值实验中,我们对奖励可识别性和概括性的理论结果得到了验证。
translated by 谷歌翻译
零和游戏中的理想策略不仅应授予玩家的平均奖励,不少于NASH均衡的价值,而且还应在次优时利用(自适应)对手。尽管马尔可夫游戏中的大多数现有作品都专注于以前的目标,但我们是否可以同时实现这两个目标仍然开放。为了解决这个问题,这项工作在马尔可夫游戏中与对抗对手进行了无重组学习,当时与事后最佳的固定政策竞争时。沿着这个方向,我们提出了一组新的正面和负面结果:当每个情节结束时对手的政策被揭示时,我们提出了实现$ \ sqrt {k} $的新的有效算法 - 遗憾的是(遗憾的是) 1)基线政策类别很小或(2)对手的政策类别很小。当两种条件不正确时,这与指数下限相辅相成。当未揭示对手的政策时,即使在最有利的情况下,当两者都是正确的情况下,我们也会证明统计硬度结果。我们的硬度结果比仅涉及计算硬度或需要进一步限制算法的现有硬度结果要强得多。
translated by 谷歌翻译
奖励是加强学习代理的动力。本文致力于了解奖励的表现,作为捕获我们希望代理人执行的任务的一种方式。我们在这项研究中涉及三个新的抽象概念“任务”,可能是可取的:(1)一组可接受的行为,(2)部分排序,或者(3)通过轨迹的部分排序。我们的主要结果证明,虽然奖励可以表达许多这些任务,但每个任务类型的实例都没有Markov奖励函数可以捕获。然后,我们提供一组多项式时间算法,其构造Markov奖励函数,允许代理优化这三种类型中的每种类型的任务,并正确确定何时不存在这种奖励功能。我们得出结论,具有证实和说明我们的理论发现的实证研究。
translated by 谷歌翻译
Epsilon-Greedy,SoftMax或Gaussian噪声等近视探索政策在某些强化学习任务中无法有效探索,但是在许多其他方面,它们的表现都很好。实际上,实际上,由于简单性,它们通常被选为最佳选择。但是,对于哪些任务执行此类政策成功?我们可以为他们的有利表现提供理论保证吗?尽管这些政策具有显着的实际重要性,但这些关键问题几乎没有得到研究。本文介绍了对此类政策的理论分析,并为通过近视探索提供了对增强学习的首次遗憾和样本复杂性。我们的结果适用于具有有限的Bellman Eluder维度的情节MDP中的基于价值功能的算法。我们提出了一种新的复杂度度量,称为近视探索差距,用Alpha表示,该差距捕获了MDP的结构属性,勘探策略和给定的值函数类别。我们表明,近视探索的样品复杂性与该数量的倒数1 / alpha^2二次地量表。我们通过具体的例子进一步证明,由于相应的动态和奖励结构,在近视探索成功的几项任务中,近视探索差距确实是有利的。
translated by 谷歌翻译
当他们更喜欢$ \ texit {exploit} $时,您如何激励自我兴趣的代理到$ \ texit {探索} $?我们考虑复杂的探索问题,其中每个代理面临相同(但未知)MDP。与传统的加固学习配方相比,代理商控制了政策的选择,而算法只能发出建议。然而,该算法控制信息流,并且可以通过信息不对称激励代理探索。我们设计一种算法,探讨MDP中的所有可达状态。我们达到了类似于先前研究的静态,无国籍探索问题中激励探索的保证担保。据我们所知,这是第一个考虑在有状态,强化学习环境中设计的工作。
translated by 谷歌翻译
大部分强化学习理论都建立在计算上难以实施的甲板上。专门用于在部分可观察到的马尔可夫决策过程(POMDP)中学习近乎最佳的政策,现有算法要么需要对模型动态(例如确定性过渡)做出强有力的假设,要么假设访问甲骨文作为解决艰难的计划或估算问题的访问子例程。在这项工作中,我们在合理的假设下开发了第一个用于POMDP的无Oracle学习算法。具体而言,我们给出了一种用于在“可观察” pomdps中学习的准化性时间端到端算法,其中可观察性是一个假设,即对国家而言,分离良好的分布诱导了分离良好的分布分布而不是观察。我们的技术规定了在不确定性下使用乐观原则来促进探索的更传统的方法,而是在构建策略涵盖的情况下提供了一种新颖的barycentric跨度应用。
translated by 谷歌翻译
我们介绍了一种改进政策改进的方法,该方法在基于价值的强化学习(RL)的贪婪方法与基于模型的RL的典型计划方法之间进行了插值。新方法建立在几何视野模型(GHM,也称为伽马模型)的概念上,该模型对给定策略的折现状态验证分布进行了建模。我们表明,我们可以通过仔细的基本策略GHM的仔细组成,而无需任何其他学习,可以评估任何非马尔科夫策略,以固定的概率在一组基本马尔可夫策略之间切换。然后,我们可以将广义政策改进(GPI)应用于此类非马尔科夫政策的收集,以获得新的马尔可夫政策,通常将其表现优于其先驱。我们对这种方法提供了彻底的理论分析,开发了转移和标准RL的应用,并在经验上证明了其对标准GPI的有效性,对充满挑战的深度RL连续控制任务。我们还提供了GHM培训方法的分析,证明了关于先前提出的方法的新型收敛结果,并显示了如何在深度RL设置中稳定训练这些模型。
translated by 谷歌翻译
逆钢筋学习尝试在马尔可夫决策问题中重建奖励功能,使用代理操作的观察。正如Russell [1998]在Russell [1998]的那样,问题均为不良,即使在存在有关最佳行为的完美信息的情况下,奖励功能也无法识别。我们为熵正则化的问题提供了解决这种不可识别性的分辨率。对于给定的环境,我们完全表征了导致给定政策的奖励函数,并证明,在两个不同的折扣因子下或在足够的不同环境下给出了相同奖励的行动的示范,可以恢复不可观察的奖励。我们还向有限视野进行时间均匀奖励的一般性和充分条件,以及行动无关的奖励,概括Kim等人的最新结果。[2021]和Fu等人。[2018]。
translated by 谷歌翻译
在过去的十年中,多智能经纪人强化学习(Marl)已经有了重大进展,但仍存在许多挑战,例如高样本复杂性和慢趋同稳定的政策,在广泛的部署之前需要克服,这是可能的。然而,在实践中,许多现实世界的环境已经部署了用于生成策略的次优或启发式方法。一个有趣的问题是如何最好地使用这些方法作为顾问,以帮助改善多代理领域的加强学习。在本文中,我们提供了一个原则的框架,用于将动作建议纳入多代理设置中的在线次优顾问。我们描述了在非传记通用随机游戏环境中提供多种智能强化代理(海军上将)的问题,并提出了两种新的基于Q学习的算法:海军上将决策(海军DM)和海军上将 - 顾问评估(Admiral-AE) ,这使我们能够通过适当地纳入顾问(Admiral-DM)的建议来改善学习,并评估顾问(Admiral-AE)的有效性。我们从理论上分析了算法,并在一般加上随机游戏中提供了关于他们学习的定点保证。此外,广泛的实验说明了这些算法:可以在各种环境中使用,具有对其他相关基线的有利相比的性能,可以扩展到大状态行动空间,并且对来自顾问的不良建议具有稳健性。
translated by 谷歌翻译
我们考虑非平稳马尔可夫决策过程中的无模型增强学习(RL)。只要其累积变化不超过某些变化预算,奖励功能和国家过渡功能都可以随时间随时间变化。我们提出了重新启动的Q学习,以上置信度范围(RestartQ-UCB),这是第一个用于非平稳RL的无模型算法,并表明它在动态遗憾方面优于现有的解决方案。具体而言,带有freedman型奖励项的restartq-ucb实现了$ \ widetilde {o}(s^{\ frac {1} {3}} {\ frac {\ frac {1} {1} {3}} {3}} {3}} {3}} {3}} {3}} {3}} {3}} {\ delta ^{\ frac {1} {3}} h t^{\ frac {2} {3}}} $,其中$ s $和$ a $分别是$ \ delta> 0 $的状态和动作的数字是变化预算,$ h $是每集的时间步数,而$ t $是时间步长的总数。我们进一步提出了一种名为Double-Restart Q-UCB的无参数算法,该算法不需要事先了解变化预算。我们证明我们的算法是\ emph {几乎是最佳},通过建立$ \ omega的信息理论下限(s^{\ frac {1} {1} {3}}} a^{\ frac {1} {1} {3}}}}}} \ delta^{\ frac {1} {3}} h^{\ frac {2} {3}}}} t^{\ frac {2} {3}}} $,是非稳态RL中的第一个下下限。数值实验可以根据累积奖励和计算效率来验证RISTARTQ-UCB的优势。我们在相关产品的多代理RL和库存控制的示例中证明了我们的结果的力量。
translated by 谷歌翻译
在学徒学习(AL)中,我们在没有获得成本函数的情况下给予马尔可夫决策过程(MDP)。相反,我们观察由根据某些政策执行的专家采样的轨迹。目标是找到一个与专家对某些预定义的成本函数的性能相匹配的策略。我们介绍了AL的在线变体(在线学徒学习; OAL),其中代理商预计与环境相互作用,在与环境互动的同时相互表现。我们表明,通过组合两名镜面血缘无遗憾的算法可以有效地解决了OAL问题:一个用于策略优化,另一个用于学习最坏情况的成本。通过采用乐观的探索,我们使用$ O(\ SQRT {k})$后悔派生算法,其中$ k $是与MDP的交互数量以及额外的线性错误术语,其取决于专家轨迹的数量可用的。重要的是,我们的算法避免了在每次迭代时求解MDP的需要,与先前的AL方法相比,更实用。最后,我们实现了我们算法的深层变体,该算法与Gail \ Cite {Ho2016Generative}共享了一些相似之处,但在鉴别者被替换为OAL问题的成本。我们的模拟表明OAL在高维控制问题中表现良好。
translated by 谷歌翻译
We develop an extension of posterior sampling for reinforcement learning (PSRL) that is suited for a continuing agent-environment interface and integrates naturally into agent designs that scale to complex environments. The approach maintains a statistically plausible model of the environment and follows a policy that maximizes expected $\gamma$-discounted return in that model. At each time, with probability $1-\gamma$, the model is replaced by a sample from the posterior distribution over environments. For a suitable schedule of $\gamma$, we establish an $\tilde{O}(\tau S \sqrt{A T})$ bound on the Bayesian regret, where $S$ is the number of environment states, $A$ is the number of actions, and $\tau$ denotes the reward averaging time, which is a bound on the duration required to accurately estimate the average reward of any policy.
translated by 谷歌翻译
Inferring reward functions from human behavior is at the center of value alignment - aligning AI objectives with what we, humans, actually want. But doing so relies on models of how humans behave given their objectives. After decades of research in cognitive science, neuroscience, and behavioral economics, obtaining accurate human models remains an open research topic. This begs the question: how accurate do these models need to be in order for the reward inference to be accurate? On the one hand, if small errors in the model can lead to catastrophic error in inference, the entire framework of reward learning seems ill-fated, as we will never have perfect models of human behavior. On the other hand, if as our models improve, we can have a guarantee that reward accuracy also improves, this would show the benefit of more work on the modeling side. We study this question both theoretically and empirically. We do show that it is unfortunately possible to construct small adversarial biases in behavior that lead to arbitrarily large errors in the inferred reward. However, and arguably more importantly, we are also able to identify reasonable assumptions under which the reward inference error can be bounded linearly in the error in the human model. Finally, we verify our theoretical insights in discrete and continuous control tasks with simulated and human data.
translated by 谷歌翻译
一种简单自然的增强学习算法(RL)是蒙特卡洛探索开始(MCES),通过平均蒙特卡洛回报来估算Q功能,并通过选择最大化Q当前估计的行动来改进策略。 -功能。探索是通过“探索开始”来执行的,即每个情节以随机选择的状态和动作开始,然后遵循当前的策略到终端状态。在Sutton&Barto(2018)的RL经典书中,据说建立MCES算法的收敛是RL中最重要的剩余理论问题之一。但是,MCE的收敛问题证明是非常细微的。 Bertsekas&Tsitsiklis(1996)提供了一个反例,表明MCES算法不一定会收敛。 TSITSIKLIS(2002)进一步表明,如果修改了原始MCES算法,以使Q-功能估计值以所有状态行动对以相同的速率更新,并且折现因子严格少于一个,则MCES算法收敛。在本文中,我们通过Sutton&Barto(1998)中给出的原始,更有效的MCES算法取得进展政策。这样的MDP包括大量的环境,例如所有确定性环境和所有具有时间步长的情节环境或作为状态的任何单调变化的值。与以前使用随机近似的证据不同,我们引入了一种新型的感应方法,该方法非常简单,仅利用大量的强规律。
translated by 谷歌翻译
强化学习理论集中在两个基本问题上:实现低遗憾,并确定$ \ epsilon $ - 最佳政策。虽然简单的减少允许人们应用低温算法来获得$ \ epsilon $ - 最佳政策并达到最坏的最佳速率,但尚不清楚低regret算法是否可以获得实例 - 最佳率的策略识别率。我们表明这是不可能的 - 在遗憾和确定$ \ epsilon $ - 最佳政策之间以最佳的利率确定了基本的权衡。由于我们的负面发现,我们提出了针对PAC表格增强学习实例依赖性样本复杂性的新量度,该方法明确说明了基础MDP中可达到的国家访问分布。然后,我们提出和分析一种基于计划的新型算法,该算法达到了这种样本的复杂性 - 产生的复杂性会随着次要差距和状态的“可达到性”而缩放。我们显示我们的算法几乎是最小的最佳选择,并且在一些示例中,我们实例依赖性样品复杂性比最差案例界限可显着改善。
translated by 谷歌翻译
平均野外游戏(MFGS)提供了一个可在数学上拖动的框架,用于通过利用平均场理论来简化代理之间的相互作用来建模大规模多代理系统。它使应用逆增强学习(IRL)能够通过从展示的行为中恢复奖励信号来预测大人群的行为。但是,现有的MFG的IRL方法无能为力,无法确定各个代理的行为中的不确定性。本文提出了一个新颖的框架,平均场对抗IRL(MF-AIRL),该框架能够解决示范中的不确定性。我们在最大熵IRL和新的平衡概念上建立MF-AIRL。我们通过不完美的演示评估了对模拟任务的方法。实验结果证明了MF-AIRL比奖励恢复中现有方法的优越性。
translated by 谷歌翻译
随机游戏的学习可以说是多功能钢筋学习(MARL)中最标准和最基本的环境。在本文中,我们考虑在非渐近制度的随机游戏中分散的Marl。特别是,我们在大量的一般总和随机游戏(SGS)中建立了完全分散的Q学习算法的有限样本复杂性 - 弱循环SGS,包括对所有代理商的普通合作MARL设置具有相同的奖励(马尔可夫团队问题是一个特例。我们专注于实用的同时具有挑战性地设置完全分散的Marl,既不奖励也没有其他药剂的作用,每个试剂都可以观察到。事实上,每个特工都完全忘记了其他决策者的存在。表格和线性函数近似情况都已考虑。在表格设置中,我们分析了分散的Q学习算法的样本复杂性,以收敛到马尔可夫完美均衡(NASH均衡)。利用线性函数近似,结果用于收敛到线性近似平衡 - 我们提出的均衡的新概念 - 这描述了每个代理的策略是线性空间内的最佳回复(到其他代理)。还提供了数值实验,用于展示结果。
translated by 谷歌翻译
在线强化学习(RL)中的挑战之一是代理人需要促进对环境的探索和对样品的利用来优化其行为。无论我们是否优化遗憾,采样复杂性,状态空间覆盖范围或模型估计,我们都需要攻击不同的勘探开发权衡。在本文中,我们建议在分离方法组成的探索 - 剥削问题:1)“客观特定”算法(自适应)规定哪些样本以收集到哪些状态,似乎它可以访问a生成模型(即环境的模拟器); 2)负责尽可能快地生成规定样品的“客观无关的”样品收集勘探策略。建立最近在随机最短路径问题中进行探索的方法,我们首先提供一种算法,它给出了每个状态动作对所需的样本$ B(S,a)$的样本数量,需要$ \ tilde {o} (bd + d ^ {3/2} s ^ 2 a)收集$ b = \ sum_ {s,a} b(s,a)$所需样本的$时间步骤,以$ s $各国,$ a $行动和直径$ d $。然后我们展示了这种通用探索算法如何与“客观特定的”策略配对,这些策略规定了解决各种设置的样本要求 - 例如,模型估计,稀疏奖励发现,无需无成本勘探沟通MDP - 我们获得改进或新颖的样本复杂性保证。
translated by 谷歌翻译