人工智能的神经符号方法将神经网络与经典的象征技术结合起来,正在逐渐突出,需要正式的方法来推理其正确性。我们提出了一种新型的建模形式主义,称为神经符号并发随机游戏(NS-CSGS),该游戏包括在共享的连续状态环境中相互作用的概率有限状态的概率有限状态,通过以神经网络实现的感知机制观察到。由于环境状态空间是连续的,因此我们专注于具有Borel状态空间的NS-CSG类。我们考虑了零和折扣累积奖励的问题,并证明了在Borel可测量性和对模型组件的分段限制下NS-CSG的价值的存在。从算法的角度来看,计算CSG的值和最佳策略的现有方法集中在有限状态空间上。我们首次介绍可实施的价值迭代和政策迭代算法,以求解一类无数状态空间CSG,即NS-CSG,并证明其收敛性。我们的方法通过利用基础游戏结构,然后制定NS-CSG的价值函数和策略的分段线性或恒定表示。我们通过将价值迭代的原型实施应用于动态的停车案例研究来说明我们的方法。
translated by 谷歌翻译
我们考虑了两个玩家零和游戏的问题。这个问题在文献中制定为Min-Max Markov游戏。该游戏的解决方案是从给定状态开始的最小最大收益称为状态的最小值。在这项工作中,我们使用在文献中成功应用的连续放松技术​​来计算双球员零和游戏的解决方案,以在马尔可夫决策过程的上下文中计算更快的价值迭代算法。我们将连续放松的概念扩展到两个玩家零和游戏的设置。我们表明,在游戏的特殊结构下,该技术有助于更快地计算状态的最大值。然后,我们推导出一种广义的Minimax Q学习算法,当模型信息未知时计算最佳策略。最后,我们证明了利用随机近似技术的提议的广义Minimax Q学习算法的收敛性,在迭代的界限上的假设下。通过实验,我们展示了我们所提出的算法的有效性。
translated by 谷歌翻译
我们展示了一种新颖的虚构播放动态变种,将经典虚拟游戏与Q学习进行随机游戏,分析其在双球零点随机游戏中的收敛性。我们的动态涉及在对手战略上形成信仰的球员以及他们自己的延续支付(Q-Function),并通过使用估计的延续收益来扮演贪婪的最佳回应。玩家从对对手行动的观察开始更新他们的信仰。学习动态的一个关键属性是,更新Q函数的信念发生在较慢的时间上,而不是对策略的信念的更新。我们在基于模型和无模式的情况下(不了解播放器支付功能和国家过渡概率),对策略的信念会聚到零和随机游戏的固定混合纳什均衡。
translated by 谷歌翻译
We consider learning approximate Nash equilibria for discrete-time mean-field games with nonlinear stochastic state dynamics subject to both average and discounted costs. To this end, we introduce a mean-field equilibrium (MFE) operator, whose fixed point is a mean-field equilibrium (i.e. equilibrium in the infinite population limit). We first prove that this operator is a contraction, and propose a learning algorithm to compute an approximate mean-field equilibrium by approximating the MFE operator with a random one. Moreover, using the contraction property of the MFE operator, we establish the error analysis of the proposed learning algorithm. We then show that the learned mean-field equilibrium constitutes an approximate Nash equilibrium for finite-agent games.
translated by 谷歌翻译
随机游戏的学习可以说是多功能钢筋学习(MARL)中最标准和最基本的环境。在本文中,我们考虑在非渐近制度的随机游戏中分散的Marl。特别是,我们在大量的一般总和随机游戏(SGS)中建立了完全分散的Q学习算法的有限样本复杂性 - 弱循环SGS,包括对所有代理商的普通合作MARL设置具有相同的奖励(马尔可夫团队问题是一个特例。我们专注于实用的同时具有挑战性地设置完全分散的Marl,既不奖励也没有其他药剂的作用,每个试剂都可以观察到。事实上,每个特工都完全忘记了其他决策者的存在。表格和线性函数近似情况都已考虑。在表格设置中,我们分析了分散的Q学习算法的样本复杂性,以收敛到马尔可夫完美均衡(NASH均衡)。利用线性函数近似,结果用于收敛到线性近似平衡 - 我们提出的均衡的新概念 - 这描述了每个代理的策略是线性空间内的最佳回复(到其他代理)。还提供了数值实验,用于展示结果。
translated by 谷歌翻译
我们在Isabelle定理箴言中展示了有限马尔可夫决定流程的正式化。我们专注于动态编程和使用加固学习代理所需的基础。特别是,我们从第一个原则(在标量和向量形式中)导出Bellman方程,导出产生任何策略P的预期值的向量计算,并继续证明存在一个普遍的最佳政策的存在折扣因子不到一个。最后,我们证明了价值迭代和策略迭代算法在有限的时间内工作,分别产生ePsilon - 最佳和完全最佳的政策。
translated by 谷歌翻译
我们研究了马尔可夫潜在游戏(MPG)中多机构增强学习(RL)问题的策略梯度方法的全球非反应收敛属性。要学习MPG的NASH平衡,在该MPG中,状态空间的大小和/或玩家数量可能非常大,我们建议使用TANDEM所有玩家运行的新的独立政策梯度算法。当梯度评估中没有不确定性时,我们表明我们的算法找到了$ \ epsilon $ -NASH平衡,$ o(1/\ epsilon^2)$迭代复杂性并不明确取决于状态空间大小。如果没有确切的梯度,我们建立$ O(1/\ epsilon^5)$样品复杂度在潜在的无限大型状态空间中,用于利用函数近似的基于样本的算法。此外,我们确定了一类独立的政策梯度算法,这些算法都可以融合零和马尔可夫游戏和马尔可夫合作游戏,并与玩家不喜欢玩的游戏类型。最后,我们提供了计算实验来证实理论发展的优点和有效性。
translated by 谷歌翻译
In this paper we develop a theoretical analysis of the performance of sampling-based fitted value iteration (FVI) to solve infinite state-space, discounted-reward Markovian decision processes (MDPs) under the assumption that a generative model of the environment is available. Our main results come in the form of finite-time bounds on the performance of two versions of sampling-based FVI. The convergence rate results obtained allow us to show that both versions of FVI are well behaving in the sense that by using a sufficiently large number of samples for a large class of MDPs, arbitrary good performance can be achieved with high probability. An important feature of our proof technique is that it permits the study of weighted L p -norm performance bounds. As a result, our technique applies to a large class of function-approximation methods (e.g., neural networks, adaptive regression trees, kernel machines, locally weighted learning), and our bounds scale well with the effective horizon of the MDP. The bounds show a dependence on the stochastic stability properties of the MDP: they scale with the discounted-average concentrability of the future-state distributions. They also depend on a new measure of the approximation power of the function space, the inherent Bellman residual, which reflects how well the function space is "aligned" with the dynamics and rewards of the MDP. The conditions of the main result, as well as the concepts introduced in the analysis, are extensively discussed and compared to previous theoretical results. Numerical experiments are used to substantiate the theoretical findings.
translated by 谷歌翻译
We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. Focusing on a stochastic query model that provides noisy evaluations of the operator, we analyze a variance-reduced stochastic approximation scheme, and establish non-asymptotic bounds for both the operator defect and the estimation error, measured in an arbitrary semi-norm. In contrast to worst-case guarantees, our bounds are instance-dependent, and achieve the local asymptotic minimax risk non-asymptotically. For linear operators, contractivity can be relaxed to multi-step contractivity, so that the theory can be applied to problems like average reward policy evaluation problem in reinforcement learning. We illustrate the theory via applications to stochastic shortest path problems, two-player zero-sum Markov games, as well as policy evaluation and $Q$-learning for tabular Markov decision processes.
translated by 谷歌翻译
In this paper, we introduce a regularized mean-field game and study learning of this game under an infinite-horizon discounted reward function. Regularization is introduced by adding a strongly concave regularization function to the one-stage reward function in the classical mean-field game model. We establish a value iteration based learning algorithm to this regularized mean-field game using fitted Q-learning. The regularization term in general makes reinforcement learning algorithm more robust to the system components. Moreover, it enables us to establish error analysis of the learning algorithm without imposing restrictive convexity assumptions on the system components, which are needed in the absence of a regularization term.
translated by 谷歌翻译
计算NASH平衡策略是多方面强化学习中的一个核心问题,在理论和实践中都受到广泛关注。但是,到目前为止,可证明的保证金仅限于完全竞争性或合作的场景,或者在大多数实际应用中实现难以满足的强大假设。在这项工作中,我们通过调查Infinite-Horizo​​n \ Emph {对抗性团队Markov Games},这是一场自然而充分动机的游戏,其中一组相同兴奋的玩家 - 在没有任何明确的情况下,这是一个自然而有动机的游戏,这是一场自然而有动机的游戏,而偏离了先前的结果。协调或交流 - 正在与对抗者竞争。这种设置允许对零和马尔可夫潜在游戏进行统一处理,并作为模拟更现实的战略互动的一步,这些互动具有竞争性和合作利益。我们的主要贡献是第一种计算固定$ \ epsilon $ - Approximate Nash Equilibria在对抗性团队马尔可夫游戏中具有计算复杂性的算法,在游戏的所有自然参数中都是多项式的,以及$ 1/\ epsilon $。拟议的算法特别自然和实用,它基于为团队中的每个球员执行独立的政策梯度步骤,并与对手侧面的最佳反应同时;反过来,通过解决精心构造的线性程序来获得对手的政策。我们的分析利用非标准技术来建立具有非convex约束的非线性程序的KKT最佳条件,从而导致对诱导的Lagrange乘数的自然解释。在此过程中,我们大大扩展了冯·斯坦格尔(Von Stengel)和科勒(GEB`97)引起的对抗(正常形式)团队游戏中最佳政策的重要特征。
translated by 谷歌翻译
钢筋学习(RL)最近在许多人工智能应用中取得了巨大成功。 RL的许多最前沿应用涉及多个代理,例如,下棋和去游戏,自主驾驶和机器人。不幸的是,古典RL构建的框架不适合多代理学习,因为它假设代理的环境是静止的,并且没有考虑到其他代理的适应性。在本文中,我们介绍了动态环境中的多代理学习的随机游戏模型。我们专注于随机游戏的简单和独立学习动态的发展:每个代理商都是近视,并为其他代理商的战略选择最佳响应类型的行动,而不与对手进行任何协调。为随机游戏开发收敛最佳响应类型独立学习动态有限的进展。我们展示了我们最近提出的简单和独立的学习动态,可保证零汇率随机游戏的融合,以及对此设置中的动态多代理学习的其他同时算法的审查。一路上,我们还重新审视了博弈论和RL文学的一些古典结果,以适应我们独立的学习动态的概念贡献,以及我们分析的数学诺克特。我们希望这篇审查文件成为在博弈论中研究独立和自然学习动态的重新训练的推动力,对于具有动态环境的更具挑战性的环境。
translated by 谷歌翻译
我们在无限地平线上享受多智能经纪增强学习(Marl)零汇率马尔可夫游戏。我们专注于分散的Marl的实用性但具有挑战性的环境,其中代理人在没有集中式控制员的情况下做出决定,但仅根据自己的收益和当地行动进行了协调。代理商不需要观察对手的行为或收益,可能甚至不忘记对手的存在,也不得意识到基础游戏的零金额结构,该环境也称为学习文学中的彻底解散游戏。在本文中,我们开发了一种彻底的解耦Q学习动态,既合理和收敛则:当对手遵循渐近静止战略时,学习动态会收敛于对对手战略的最佳反应;当两个代理采用学习动态时,它们会收敛到游戏的纳什均衡。这种分散的环境中的关键挑战是从代理商的角度来看环境的非公平性,因为她自己的回报和系统演变都取决于其他代理人的行为,每个代理商同时和独立地互补她的政策。要解决此问题,我们开发了两个时间尺度的学习动态,每个代理会更新她的本地Q函数和value函数估计,后者在较慢的时间内发生。
translated by 谷歌翻译
在动态编程(DP)和强化学习(RL)中,代理商学会在通过由Markov决策过程(MDP)建模的环境中顺序交互来实现预期的长期返回。更一般地在分布加强学习(DRL)中,重点是返回的整体分布,而不仅仅是其期望。虽然基于DRL的方法在RL中产生了最先进的性能,但它们涉及尚未充分理解的额外数量(与非分布设置相比)。作为第一个贡献,我们介绍了一类新的分类运营商,以及一个实用的DP算法,用于策略评估,具有强大的MDP解释。实际上,我们的方法通过增强的状态空间重新重新重新重新重新重新格式化,其中每个状态被分成最坏情况的子变量,并且最佳的子变电站,其值分别通过安全和危险的策略最大化。最后,我们派生了分配运营商和DP算法解决了一个新的控制任务:如何区分安全性的最佳动作,以便在最佳政策空间中打破联系?
translated by 谷歌翻译
Mean-field games have been used as a theoretical tool to obtain an approximate Nash equilibrium for symmetric and anonymous $N$-player games in literature. However, limiting applicability, existing theoretical results assume variations of a "population generative model", which allows arbitrary modifications of the population distribution by the learning algorithm. Instead, we show that $N$ agents running policy mirror ascent converge to the Nash equilibrium of the regularized game within $\tilde{\mathcal{O}}(\varepsilon^{-2})$ samples from a single sample trajectory without a population generative model, up to a standard $\mathcal{O}(\frac{1}{\sqrt{N}})$ error due to the mean field. Taking a divergent approach from literature, instead of working with the best-response map we first show that a policy mirror ascent map can be used to construct a contractive operator having the Nash equilibrium as its fixed point. Next, we prove that conditional TD-learning in $N$-agent games can learn value functions within $\tilde{\mathcal{O}}(\varepsilon^{-2})$ time steps. These results allow proving sample complexity guarantees in the oracle-free setting by only relying on a sample path from the $N$ agent simulator. Furthermore, we demonstrate that our methodology allows for independent learning by $N$ agents with finite sample guarantees.
translated by 谷歌翻译
最近的平均野外游戏(MFG)形式主义促进了对许多代理环境中近似NASH均衡的棘手计算。在本文中,我们考虑具有有限摩托目标目标的离散时间有限的MFG。我们表明,所有具有非恒定固定点运算符的离散时间有限的MFG无法正如现有MFG文献中通常假设的,禁止通过固定点迭代收敛。取而代之的是,我们将熵验证和玻尔兹曼策略纳入固定点迭代中。结果,我们获得了现有方法失败的近似固定点的可证明的融合,并达到了近似NASH平衡的原始目标。所有提出的方法均可在其可剥削性方面进行评估,这两个方法都具有可牵引的精确溶液和高维问题的启发性示例,在这些示例中,精确方法变得棘手。在高维场景中,我们采用了既定的深入强化学习方法,并从经验上将虚拟的游戏与我们的近似值结合在一起。
translated by 谷歌翻译
策略梯度方法适用于复杂的,不理解的,通过对参数化的策略进行随机梯度下降来控制问题。不幸的是,即使对于可以通过标准动态编程技术解决的简单控制问题,策略梯度算法也会面临非凸优化问题,并且被广泛理解为仅收敛到固定点。这项工作确定了结构属性 - 通过几个经典控制问题共享 - 确保策略梯度目标函数尽管是非凸面,但没有次优的固定点。当这些条件得到加强时,该目标满足了产生收敛速率的Polyak-lojasiewicz(梯度优势)条件。当其中一些条件放松时,我们还可以在任何固定点的最佳差距上提供界限。
translated by 谷歌翻译
We study a multi-agent reinforcement learning (MARL) problem where the agents interact over a given network. The goal of the agents is to cooperatively maximize the average of their entropy-regularized long-term rewards. To overcome the curse of dimensionality and to reduce communication, we propose a Localized Policy Iteration (LPI) algorithm that provably learns a near-globally-optimal policy using only local information. In particular, we show that, despite restricting each agent's attention to only its $\kappa$-hop neighborhood, the agents are able to learn a policy with an optimality gap that decays polynomially in $\kappa$. In addition, we show the finite-sample convergence of LPI to the global optimal policy, which explicitly captures the trade-off between optimality and computational complexity in choosing $\kappa$. Numerical simulations demonstrate the effectiveness of LPI.
translated by 谷歌翻译
我们在离散时间无限的地平线设置下引入了Markov决策问题的一般框架。通过提供动态的编程原则,我们获得了局部到全球范式,即求解本地,即一个时间步骤的强大优化问题会导致全局(即无限时步)的优化器,以及相应的最坏情况。此外,我们将此框架应用于涉及标准普尔500数据的投资组合优化。我们提出了两种不同类型的歧义集。一个由余地量围绕经验度量给出的完全数据驱动的,第二个是由多元正常分布的参数集来描述的,其中参数的相应不确定性集是从数据中估算的。事实证明,在市场波动或看跌的情况下,来自相应的健壮优化问题的最佳投资组合策略胜过没有模型不确定性的情况,表明将模型不确定性考虑到了重要性。
translated by 谷歌翻译
We propose a multi-agent reinforcement learning dynamics, and analyze its convergence properties in infinite-horizon discounted Markov potential games. We focus on the independent and decentralized setting, where players can only observe the realized state and their own reward in every stage. Players do not have knowledge of the game model, and cannot coordinate with each other. In each stage of our learning dynamics, players update their estimate of a perturbed Q-function that evaluates their total contingent payoff based on the realized one-stage reward in an asynchronous manner. Then, players independently update their policies by incorporating a smoothed optimal one-stage deviation strategy based on the estimated Q-function. A key feature of the learning dynamics is that the Q-function estimates are updated at a faster timescale than the policies. We prove that the policies induced by our learning dynamics converge to a stationary Nash equilibrium in Markov potential games with probability 1. Our results demonstrate that agents can reach a stationary Nash equilibrium in Markov potential games through simple learning dynamics under the minimum information environment.
translated by 谷歌翻译