鉴于它在提取功能表示方面的力量，对比性的自我监督学习已成功整合到（深）强化学习（RL）的实践中，从而在各种应用程序中提供了有效的政策学习。尽管取得了巨大的经验成功，但对RL的对比学习的理解仍然难以捉摸。为了缩小这样的差距，我们研究了Markov决策过程（MDP）和Markov Games（MGS）的对比度学习如何赋予RL的能力。对于这两种模型，我们建议通过最大程度地减少对比度损失来提取低级别模型的正确特征表示。此外，在在线环境下，我们提出了新颖的上限置信界（UCB）型算法，该算法将这种对比度损失与MDP或MGS的在线RL算法结合在一起。从理论上讲，我们进一步证明了我们的算法恢复了真实表示形式，并同时在学习MDP和MGS中学习最佳策略和NASH平衡方面同时实现了样本效率。我们还提供实证研究，以证明基于UCB的RL的对比度学习方法的功效。据我们所知，我们提供了第一种可证明有效的在线RL算法，该算法结合了代表学习的对比学习。我们的代码可从https://github.com/baichenjia/contrastive-ucb获得。

我们考虑在具有非线性函数近似的两名玩家零和马尔可夫游戏中学习NASH平衡，其中动作值函数通过繁殖内核Hilbert Space（RKHS）中的函数近似。关键挑战是如何在高维函数空间中进行探索。我们提出了一种新颖的在线学习算法，以最大程度地减少双重性差距来找到NASH平衡。我们算法的核心是基于不确定性的乐观原理得出的上和下置信度界限。我们证明，在非常温和的假设上，我们的算法能够获得$ O（\ sqrt {t}）$遗憾，并在对奖励功能和马尔可夫游戏的基本动态下进行多项式计算复杂性。我们还提出了我们的算法的几个扩展，包括具有伯恩斯坦型奖励的算法，可以实现更严格的遗憾，以及用于模型错误指定的另一种算法，可以应用于神经功能近似。

我们与指定为领导者的球员之一和其他球员读为追随者的球员学习多人一般汇总马尔可夫游戏。特别是，我们专注于追随者是近视的游戏，即，他们的目标是最大限度地提高他们的瞬间奖励。对于这样的游戏，我们的目标是找到一个Stackelberg-Nash均衡（SNE），这是一个策略对$（\ pi ^ *，\ nu ^ *）$，这样（i）$ \ pi ^ * $是追随者始终发挥最佳回应的领导者的最佳政策，（ii）$ \ nu ^ * $是追随者的最佳反应政策，这是由$ \ pi ^ *引起的追随者游戏的纳什均衡$。我们开发了用于在线和离线设置中的SNE解决SNE的采样高效的强化学习（RL）算法。我们的算法是最小二乘值迭代的乐观和悲观的变体，并且它们很容易能够在大状态空间的设置中结合函数近似工具。此外，对于线性函数近似的情况，我们证明我们的算法分别在线和离线设置下实现了Sublinear遗憾和次优。据我们所知，我们建立了第一种可用于解决近代Markov游戏的SNES的第一款可透明的RL算法。

尽管固定环境中的单一机构政策优化最近在增强学习社区中引起了很多研究的关注，但是当在潜在竞争性的环境中有多个代理商在玩耍时，从理论上讲，少得多。我们通过提出和分析具有结构化但未知过渡的零和Markov游戏的新的虚拟游戏策略优化算法来向前迈进。我们考虑两类的过渡结构：分类的独立过渡和单个控制器过渡。对于这两种情况，我们都证明了紧密的$ \ widetilde {\ Mathcal {o}}（\ sqrt {k}）$遗憾的范围在$ k $ eviepodes之后，在两种代理竞争的游戏场景中。每个代理人的遗憾是针对潜在的对抗对手的衡量，他们在观察完整的政策序列后可以在事后选择一个最佳政策。我们的算法在非平稳环境中同时进行政策优化的范围下，具有上置信度结合（UCB）的乐观和虚拟游戏的结合。当两个玩家都采用所提出的算法时，他们的总体最优差距为$ \ widetilde {\ Mathcal {o}}（\ sqrt {k}）$。

随着代表性学习成为一种在实践中降低增强学习（RL）样本复杂性（RL）的强大技术，对其优势的理论理解仍然是有限的。在本文中，我们从理论上表征了在低级马尔可夫决策过程（MDP）模型下表示学习的好处。我们首先研究多任务低级RL（作为上游培训），所有任务都共享一个共同的表示，并提出了一种称为加油的新型多任务奖励算法。加油站同时了解每个任务的过渡内核和近乎最佳的策略，并为下游任务输出良好的代表。我们的结果表明，只要任务总数高于一定的阈值，多任务表示学习比单独学习的样本效率要高。然后，我们研究在线和离线设置中的下游RL，在该设置中，代理商分配了一个新任务，共享与上游任务相同的表示形式。对于在线和离线设置，我们都会开发出样本效率高的算法，并表明它找到了一个近乎最佳的策略，其次要差距在上游中学习的估计误差和一个消失的术语作为数字作为数字的估计误差的范围。下游样品的大量变大。我们在线和离线RL的下游结果进一步捕获了从上游采用学习的表示形式的好处，而不是直接学习低级模型的表示。据我们所知，这是第一个理论研究，它表征了代表性学习在基于探索的无奖励多任务RL中对上游和下游任务的好处。

尽管无奖励强化学习勘探阶段的主要目标（RF-RL）是减少具有最小轨迹数量的估计模型中的不确定性时间。目前尚不清楚这种安全的探索要求如何影响相应的样本复杂性，以实现所获得的计划中所需的最佳性。在这项工作中，我们首次尝试回答这个问题。特别是，我们考虑了事先知道安全基线政策的情况，并提出了一个统一的安全奖励探索（甜蜜）框架。然后，我们将甜蜜框架专门为表格和低级MDP设置，并分别开发出算法所构成的表格甜味和低级别甜味。两种算法都利用了新引入的截短值函数的凹度和连续性，并保证在探索过程中以高概率侵犯了零约束。此外，两种算法都可以在计划阶段的任何约束中找到近乎最佳的政策。值得注意的是，算法下的样本复杂性在无限制的对应物中匹配甚至超过最恒定因素的最新情况，这证明安全约束几乎不会增加RF-RL的样本复杂性。

We study sample efficient reinforcement learning (RL) under the general framework of interactive decision making, which includes Markov decision process (MDP), partially observable Markov decision process (POMDP), and predictive state representation (PSR) as special cases. Toward finding the minimum assumption that empowers sample efficient learning, we propose a novel complexity measure, generalized eluder coefficient (GEC), which characterizes the fundamental tradeoff between exploration and exploitation in online interactive decision making. In specific, GEC captures the hardness of exploration by comparing the error of predicting the performance of the updated policy with the in-sample training error evaluated on the historical data. We show that RL problems with low GEC form a remarkably rich class, which subsumes low Bellman eluder dimension problems, bilinear class, low witness rank problems, PO-bilinear class, and generalized regular PSR, where generalized regular PSR, a new tractable PSR class identified by us, includes nearly all known tractable POMDPs. Furthermore, in terms of algorithm design, we propose a generic posterior sampling algorithm, which can be implemented in both model-free and model-based fashion, under both fully observable and partially observable settings. The proposed algorithm modifies the standard posterior sampling algorithm in two aspects: (i) we use an optimistic prior distribution that biases towards hypotheses with higher values and (ii) a loglikelihood function is set to be the empirical loss evaluated on the historical data, where the choice of loss function supports both model-free and model-based learning. We prove that the proposed algorithm is sample efficient by establishing a sublinear regret upper bound in terms of GEC. In summary, we provide a new and unified understanding of both fully observable and partially observable RL.

这项工作研究了RL中的代表性学习问题：我们如何学习紧凑的低维表示，使得在代表之上，我们可以以示例有效的方式执行诸如勘探和开发的RL程序。我们专注于低级马尔可夫决策过程（MDP），其中转换动态对应于低秩转换矩阵。与假设表示的事先作品（例如，线性MDP）不同，这里我们需要学习低秩MDP的表示。我们研究在线RL和离线RL设置。对于在线设置，在Flambe（Agarwal et.al）中使用相同的计算oracells操作，用于在低级MDP中学习表示的最先进的算法，我们提出了一种算法Rep-UCB上部置信束缚的驱动表示学习对于RL），这显着提高了$ \ widetilde {o}的样本复杂性（a ^ 9 d ^ 7 /（\ epsilon ^ {10}（1- \ gamma）^ {22}），因为flambe到$ \ widetilde {o}（a ^ 4 d ^ 4 /（\ epsilon ^ 2（1- \ gamma）^ {3}）$ d $是转换矩阵的等级（或地面真相表示的维度） ，$ a $是行动次数，而$ \ gamma $是折扣因素。值得注意的是，rep-ucb比flambe更简单，因为它直接余额余额表示学习，探索和剥削之间的相互作用，而Flambe是一种探索的探索式风格方法，并且必须逐步执行无奖励探索及时。对于离线RL设置，我们开发了一种利用悲观主义在部分覆盖条件下学习的算法：我们的算法能够与脱机分布所涵盖的策略进行竞争。

Deep latent variable models have achieved significant empirical successes in model-based reinforcement learning (RL) due to their expressiveness in modeling complex transition dynamics. On the other hand, it remains unclear theoretically and empirically how latent variable models may facilitate learning, planning, and exploration to improve the sample efficiency of RL. In this paper, we provide a representation view of the latent variable models for state-action value functions, which allows both tractable variational learning algorithm and effective implementation of the optimism/pessimism principle in the face of uncertainty for exploration. In particular, we propose a computationally efficient planning algorithm with UCB exploration by incorporating kernel embeddings of latent variable models. Theoretically, we establish the sample complexity of the proposed approach in the online and offline settings. Empirically, we demonstrate superior performance over current state-of-the-art algorithms across various benchmarks.

尽管基于模型的增强学习（RL）方法被认为是更具样本的高效，但现有算法通常依赖于复杂的规划算法与模型学习过程紧密粘合。因此，学习模型可能缺乏与更专业规划者重新使用的能力。在本文中，我们解决了这个问题，并提供了在没有奖励信号的指导的情况下有效地学习RL模型的方法。特别是，我们采取了一个插件求解器方法，我们专注于在探索阶段学习模型，并要求在学习模型上的\ emph {任何规划算法}可以给出近最佳的政策。具体而言，我们专注于线性混合MDP设置，其中概率转换矩阵是一组现有模型的（未知）凸面组合。我们表明，通过建立新的探索算法，即插即用通过\ tilde {o}来学习模型（d ^ 2h ^ 3 / epsilon ^ 2）$与环境交互，\ emph {任何} $ \ epsilon $ -optimal Planner在模型上给出$ O（\ epsilon）$ - 原始模型上的最佳政策。此示例复杂性与非插入方法的下限与下限匹配，并且是\ EMPH {统计上最佳}。我们通过利用使用伯尔斯坦不等式和指定的线性混合MDP的属性来实现仔细的最大总差异来实现这一结果。

我们研究了具有线性函数近似增强学习中的随机最短路径（SSP）问题，其中过渡内核表示为未知模型的线性混合物。我们将此类别的SSP问题称为线性混合物SSP。我们提出了一种具有Hoeffding-type置信度的新型算法，用于学习线性混合物SSP，可以获得$ \ tilde {\ Mathcal {o}}}}（d B _ {\ star}^{1.5} \ sqrt {k/c_ {k/c_ {k/c_ {k/c_ { \ min}}）$遗憾。这里$ k $是情节的数量，$ d $是混合模型中功能映射的维度，$ b _ {\ star} $限制了最佳策略的预期累积成本，$ c _ {\ min}>> 0 $是成本函数的下限。当$ c _ {\ min} = 0 $和$ \ tilde {\ mathcal {o}}}（k^{2/3}）$遗憾时，我们的算法也适用于情况。据我们所知，这是第一个具有sublrinear遗憾保证线性混合物SSP的算法。此外，我们设计了精致的伯恩斯坦型信心集并提出了改进的算法，该算法可实现$ \ tilde {\ Mathcal {o}}}（d b _ {\ star} \ sqrt {k/c/c/c {k/c _ {\ min}}） $遗憾。为了补充遗憾的上限，我们还证明了$ \ omega（db _ {\ star} \ sqrt {k}）$的下限。因此，我们的改进算法将下限匹配到$ 1/\ sqrt {c _ {\ min}} $ factor和poly-logarithmic因素，从而实现了近乎最佳的遗憾保证。

We study episodic two-player zero-sum Markov games (MGs) in the offline setting, where the goal is to find an approximate Nash equilibrium (NE) policy pair based on a dataset collected a priori. When the dataset does not have uniform coverage over all policy pairs, finding an approximate NE involves challenges in three aspects: (i) distributional shift between the behavior policy and the optimal policy, (ii) function approximation to handle large state space, and (iii) minimax optimization for equilibrium solving. We propose a pessimism-based algorithm, dubbed as pessimistic minimax value iteration (PMVI), which overcomes the distributional shift by constructing pessimistic estimates of the value functions for both players and outputs a policy pair by solving NEs based on the two value functions. Furthermore, we establish a data-dependent upper bound on the suboptimality which recovers a sublinear rate without the assumption on uniform coverage of the dataset. We also prove an information-theoretical lower bound, which suggests that the data-dependent term in the upper bound is intrinsic. Our theoretical results also highlight a notion of "relative uncertainty", which characterizes the necessary and sufficient condition for achieving sample efficiency in offline MGs. To the best of our knowledge, we provide the first nearly minimax optimal result for offline MGs with function approximation.

我们研究了马尔可夫潜在游戏（MPG）中多机构增强学习（RL）问题的策略梯度方法的全球非反应收敛属性。要学习MPG的NASH平衡，在该MPG中，状态空间的大小和/或玩家数量可能非常大，我们建议使用TANDEM所有玩家运行的新的独立政策梯度算法。当梯度评估中没有不确定性时，我们表明我们的算法找到了$ \ epsilon $ -NASH平衡，$ o（1/\ epsilon^2）$迭代复杂性并不明确取决于状态空间大小。如果没有确切的梯度，我们建立$ O（1/\ epsilon^5）$样品复杂度在潜在的无限大型状态空间中，用于利用函数近似的基于样本的算法。此外，我们确定了一类独立的政策梯度算法，这些算法都可以融合零和马尔可夫游戏和马尔可夫合作游戏，并与玩家不喜欢玩的游戏类型。最后，我们提供了计算实验来证实理论发展的优点和有效性。

我们研究了基于模型的无奖励加强学习，具有ePiSodic Markov决策过程的线性函数近似（MDP）。在此设置中，代理在两个阶段工作。在勘探阶段，代理商与环境相互作用并在没有奖励的情况下收集样品。在规划阶段，代理商给出了特定的奖励功能，并使用从勘探阶段收集的样品来学习良好的政策。我们提出了一种新的可直接有效的算法，称为UCRL-RFE在线性混合MDP假设，其中MDP的转换概率内核可以通过线性函数参数化，在状态，动作和下一个状态的三联体上定义的某些特征映射上参数化。我们展示了获得$ \ epsilon $-Optimal策略进行任意奖励函数，Ucrl-RFE需要以大多数$ \ tilde {\ mathcal {o}}来进行采样（h ^ 5d ^ 2 \ epsilon ^ { - 2}）勘探阶段期间的$派对。在这里，$ H $是集的长度，$ d $是特征映射的尺寸。我们还使用Bernstein型奖金提出了一种UCRL-RFE的变种，并表明它需要在大多数$ \ TINDE {\ MATHCAL {o}}（H ^ 4D（H + D）\ epsilon ^ { - 2}）进行样本$达到$ \ epsilon $ -optimal政策。通过构建特殊类的线性混合MDPS，我们还证明了对于任何无奖励算法，它需要至少为$ \ TINDE \ OMEGA（H ^ 2d \ epsilon ^ { - 2}）$剧集来获取$ \ epsilon $ -optimal政策。我们的上限与依赖于$ \ epsilon $的依赖性和$ d $ if $ h \ ge d $。

在阻碍强化学习（RL）到现实世界中的问题的原因之一，两个因素至关重要：与培训相比，数据有限和测试环境的不匹配。在本文中，我们试图通过分配强大的离线RL的问题同时解决这些问题。特别是，我们学习了一个从源环境中获得的历史数据，并优化了RL代理，并在扰动的环境中表现良好。此外，我们考虑将算法应用于大规模问题的线性函数近似。我们证明我们的算法可以实现$ O（1/\ sqrt {k}）$的次级临时性，具体取决于线性函数尺寸$ d $，这似乎是在此设置中使用样品复杂性保证的第一个结果。进行了不同的实验以证明我们的理论发现，显示了我们算法与非持bust算法的优越性。

We consider a multi-agent episodic MDP setup where an agent (leader) takes action at each step of the episode followed by another agent (follower). The state evolution and rewards depend on the joint action pair of the leader and the follower. Such type of interactions can find applications in many domains such as smart grids, mechanism design, security, and policymaking. We are interested in how to learn policies for both the players with provable performance guarantee under a bandit feedback setting. We focus on a setup where both the leader and followers are {\em non-myopic}, i.e., they both seek to maximize their rewards over the entire episode and consider a linear MDP which can model continuous state-space which is very common in many RL applications. We propose a {\em model-free} RL algorithm and show that $\tilde{\mathcal{O}}(\sqrt{d^3H^3T})$ regret bounds can be achieved for both the leader and the follower, where $d$ is the dimension of the feature mapping, $H$ is the length of the episode, and $T$ is the total number of steps under the bandit feedback information setup. Thus, our result holds even when the number of states becomes infinite. The algorithm relies on {\em novel} adaptation of the LSVI-UCB algorithm. Specifically, we replace the standard greedy policy (as the best response) with the soft-max policy for both the leader and the follower. This turns out to be key in establishing uniform concentration bound for the value functions. To the best of our knowledge, this is the first sub-linear regret bound guarantee for the Markov games with non-myopic followers with function approximation.

我们在面对未衡量的混杂因素时研究离线增强学习（RL）。由于缺乏与环境的在线互动，离线RL面临以下两个重大挑战：（i）代理可能会被未观察到的状态变量混淆； （ii）提前收集的离线数据不能为环境提供足够的覆盖范围。为了应对上述挑战，我们借助工具变量研究了混杂的MDP中的政策学习。具体而言，我们首先建立了基于和边缘化的重要性采样（MIS）的识别结果，以确定混杂的MDP中的预期总奖励结果。然后，通过利用悲观主义和我们的认同结果，我们提出了各种政策学习方法，并具有有限样本的次级临时性保证，可以在最小的数据覆盖范围和建模假设下找到最佳的课堂政策。最后，我们广泛的理论研究和一项由肾脏移植动机的数值研究证明了该方法的有希望的表现。

我们在一般的非线性函数近似下研究无奖励增强学习（RL），并在各种标准结构假设下建立样品效率和硬度结果。从积极的一面来看，我们提出了在最小的结构假设下进行样品有效奖励探索的Rfolive（无奖励橄榄）算法，该假设涵盖了先前研究的线性MDPS的设置（Jin等，2020b），线性完整性（线性完整性）（ Zanette等人，2020b）和低级MDP，具有未知的表示（Modi等，2021）。我们的分析表明，以前针对后两个设置的易学性或可及性假设在统计上对于无奖励探索而言并不是必需的。在负面方面，我们为在线性完整性假设下的无奖励和奖励意识探索提供统计硬度结果时，当基础特征未知时，显示了低级别和线性完整性设置之间的指数分离。

离线增强学习（RL）可以从先前收集的数据中进行有效的学习，而无需探索，这在探索昂贵甚至不可行时在现实世界应用中显示出巨大的希望。折扣因子$ \ gamma $在提高在线RL样本效率和估计准确性方面起着至关重要的作用，但是折现因子在离线RL中的作用尚未得到很好的探索。本文研究了$ \ gamma $在离线RL中的两个明显影响，并通过理论分析，即正则化效果和悲观效应。一方面，$ \ gamma $是在现有离线技术下以样本效率而定的最佳选择的监管机构。另一方面，较低的指导$ \ gamma $也可以看作是一种悲观的方式，我们在最坏的模型中优化了政策的性能。我们通过表格MDP和标准D4RL任务从经验上验证上述理论观察。结果表明，折现因子在离线RL算法的性能中起着至关重要的作用，无论是在现有的离线方法的小型数据制度下还是在没有其他保守主义的大型数据制度中。

低级MDP已成为研究强化学习中的表示和探索的重要模型。有了已知的代表，存在几种无模型的探索策略。相反，未知表示设置的所有算法都是基于模型的，因此需要对完整动力学进行建模。在这项工作中，我们介绍了低级MDP的第一个无模型表示学习算法。关键的算法贡献是一个新的Minimax表示学习目标，我们为其提供具有不同权衡的变体，其统计和计算属性不同。我们将这一表示的学习步骤与探索策略交织在一起，以无奖励的方式覆盖状态空间。所得算法可证明样品有效，并且可以适应一般函数近似以扩展到复杂的环境。