我们研究了一个名为“战略MDP”的新型模型下的离线增强学习，该模型表征了本金和一系列与私有类型的近视药物之间的战略相互作用。由于双层结构和私人类型，战略MDP涉及主体与代理之间的信息不对称。我们专注于离线RL问题，其目标是基于由历史互动组成的预采用数据集学习委托人的最佳政策。未观察到的私人类型混淆了这样的数据集，因为它们会影响委托人收到的奖励和观察结果。我们提出了一种新颖的算法，具有算法工具（计划）的悲观政策学习，该算法利用仪器变量回归的思想和悲观主义原则在一般功能近似的背景下学习近乎最佳的原理政策。我们的算法是基于批判性观察，即主体的行为是有效的工具变量。特别是，在离线数据集中的部分覆盖范围假设下，我们证明计划输出$ 1 / \ sqrt {k} $ - 最佳策略，$ k $是收集的轨迹数量。我们进一步将框架应用于一些特殊的战略MDP案例，包括战略回归，战略强盗和推荐系统中的不合规性。

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

Motivated by the human-machine interaction such as training chatbots for improving customer satisfaction, we study human-guided human-machine interaction involving private information. We model this interaction as a two-player turn-based game, where one player (Alice, a human) guides the other player (Bob, a machine) towards a common goal. Specifically, we focus on offline reinforcement learning (RL) in this game, where the goal is to find a policy pair for Alice and Bob that maximizes their expected total rewards based on an offline dataset collected a priori. The offline setting presents two challenges: (i) We cannot collect Bob's private information, leading to a confounding bias when using standard RL methods, and (ii) a distributional mismatch between the behavior policy used to collect data and the desired policy we aim to learn. To tackle the confounding bias, we treat Bob's previous action as an instrumental variable for Alice's current decision making so as to adjust for the unmeasured confounding. We develop a novel identification result and use it to propose a new off-policy evaluation (OPE) method for evaluating policy pairs in this two-player turn-based game. To tackle the distributional mismatch, we leverage the idea of pessimism and use our OPE method to develop an off-policy learning algorithm for finding a desirable policy pair for both Alice and Bob. Finally, we prove that under mild assumptions such as partial coverage of the offline data, the policy pair obtained through our method converges to the optimal one at a satisfactory rate.

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.

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

我们研究了具有连续状态的可观察到的马尔可夫决策过程（POMDPS）的非政策评估问题（OPE）。由最近提出的近端因果推理框架的动机，我们开发了一个非参数识别结果，以通过时间依赖性代理变量的帮助通过所谓的V-bridge函数来估算策略值。然后，我们开发一种拟合的Q评估类型算法来递归估算V桥功能，其中每个步骤都解决了非参数仪器变量（NPIV）问题。通过分析这个具有挑战性的顺序NPIV问题，我们建立了用于估计V桥功能的有限样本误差界限，并因此根据样本量，地平线和所谓（本地）度量来评估策略值，以评估策略值每个步骤都不适。据我们所知，这是非参数模型下POMDP中OPE绑定的第一个有限样本误差。

我们研究了用线性函数近似的加固学习中的违规评估（OPE）问题，旨在根据行为策略收集的脱机数据来估计目标策略的价值函数。我们建议纳入价值函数的方差信息以提高ope的样本效率。更具体地说，对于时间不均匀的epiSodic线性马尔可夫决策过程（MDP），我们提出了一种算法VA-OPE，它使用价值函数的估计方差重新重量拟合Q迭代中的Bellman残差。我们表明我们的算法达到了比最着名的结果绑定的更紧密的误差。我们还提供了行为政策与目标政策之间的分布转移的细粒度。广泛的数值实验证实了我们的理论。

强化学习（RL）的显着成功在很大程度上依赖于观察每个访问的州行动对的奖励。但是，在许多现实世界应用中，代理只能观察一个代表整个轨迹质量的分数，该分数称为{\ em轨迹方面的奖励}。在这种情况下，标准RL方法很难很好地利用轨迹的奖励，并且在政策评估中可能会产生巨大的偏见和方差错误。在这项工作中，我们提出了一种新颖的离线RL算法，称为悲观的价值迭代，奖励分解（分开），该算法将轨迹返回分解为每个步骤代理奖励，通过基于最小二乘的奖励重新分配，然后执行基于基于基于基于基于的价值迭代的迭代价值迭代的迭代迭代率关于博学的代理奖励。为了确保由分开构建的价值功能对最佳函数始终是悲观的，我们设计了一个新的罚款术语来抵消代理奖励的不确定性。对于具有较大状态空间的一般情节MDP，我们表明与过度参数化的神经网络函数近似近似能够实现$ \ tilde {\ Mathcal {o}}}（d _ {\ text {eff}}} h^2/\ sqrt {n}） $ suboftimality，其中$ h $是情节的长度，$ n $是样本总数，而$ d _ {\ text {eff}} $是神经切线核矩阵的有效维度。为了进一步说明结果，我们表明分开实现了$ \ tilde {\ mathcal {o}}}（dh^3/\ sqrt {n}）$ subiptimation fi linearem mdps，其中$ d $是特征尺寸，匹配功能维度使用神经网络功能近似，当$ d _ {\ text {eff}} = dh $时。据我们所知，分开是第一种离线RL算法，在MDP总体上，轨迹奖励的效率非常有效。

在马尔可夫决策过程（MDP）中，可能存在不可观察的混杂因素并对数据生成过程产生影响，因此经典的非政策评估（OPE）估计器可能无法识别目标策略的真实价值函数。在本文中，我们研究了与可观察的仪器变量混杂的MDP中OPE的统计特性。具体而言，我们根据仪器变量提出了一个两阶段估计器，并在具有线性结构的混杂MDP中建立了其统计属性。对于非反应分析，我们证明了一个$ \ Mathcal {o}（n^{ - 1/2}）$ - 错误绑定了$ n $是样本的数量。对于渐近分析，我们证明了两阶段估计量在渐近正常上，典型速率为$ n^{1/2} $。据我们所知，我们是第一个通过仪器变量显示混合线性MDP的两阶段估计量的统计结果。

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.

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

我们研究了具有无限观察和状态空间的部分观察到的马尔可夫决策过程（POMDP）的强化学习，理论上仍然不太研究。为此，我们首次尝试弥合具有线性结构的一类POMDP的部分可观察性和功能近似。详细说明，我们建议在$ O（1/\ Epsilon^2）$情节中获得$ \ epsilon $ - 最佳策略的增强学习算法（通过对抗积分方程或操作装置的乐观探索）。特别是，样品复杂性在线性结构的固有维度上缩放，并且独立于观测和状态空间的大小。 Op-Tenet的样品效率由一系列成分启用：（i）具有有限内存的钟形操作员，该操作员以递归方式表示值函数，（ii）通过对抗性积分对此类操作员的识别和估计方程式具有针对线性结构量身定制的平滑歧视器，以及（iii）通过乐观探索观察和状态空间，该探索基于量化对抗性积分方程的不确定性。

We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic $Q$-Learning (VO$Q$L), based on $Q$-learning and bound its regret assuming completeness and bounded Eluder dimension for the regression function class. As a special case, VO$Q$L achieves $\tilde{O}(d\sqrt{HT}+d^6H^{5})$ regret over $T$ episodes for a horizon $H$ MDP under ($d$-dimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.

Offline reinforcement learning (RL) concerns pursuing an optimal policy for sequential decision-making from a pre-collected dataset, without further interaction with the environment. Recent theoretical progress has focused on developing sample-efficient offline RL algorithms with various relaxed assumptions on data coverage and function approximators, especially to handle the case with excessively large state-action spaces. Among them, the framework based on the linear-programming (LP) reformulation of Markov decision processes has shown promise: it enables sample-efficient offline RL with function approximation, under only partial data coverage and realizability assumptions on the function classes, with favorable computational tractability. In this work, we revisit the LP framework for offline RL, and advance the existing results in several aspects, relaxing certain assumptions and achieving optimal statistical rates in terms of sample size. Our key enabler is to introduce proper constraints in the reformulation, instead of using any regularization as in the literature, sometimes also with careful choices of the function classes and initial state distributions. We hope our insights further advocate the study of the LP framework, as well as the induced primal-dual minimax optimization, in offline RL.

使用悲观，推理缺乏详尽的勘探数据集时的脱机强化学习最近颇具知名度。尽管它增加了算法的鲁棒性，过于悲观的推理可以在排除利好政策的发现，这是流行的基于红利悲观的问题同样有害。在本文中，我们介绍一般函数近似的Bellman-一致悲观的概念：不是计算逐点下界的值的功能，我们在超过设定的与贝尔曼方程一致的功能的初始状态实现悲观。我们的理论保证只需要贝尔曼封闭性作为探索性的设置标准，其中基于奖金的情况下的悲观情绪未能提供担保。即使在线性函数逼近的特殊情况下更强的表现力假设成立，我们的结果由$ \ mathcal {}Ø（d）在其样品的复杂$在最近的基于奖金的方法改善的时候，动作的空间是有限的。值得注意的是，我们的算法，能够自动适应事后最好的偏差 - 方差折中，而大多数现有的方法中需要调整的额外超参数的先验。

我们建议和分析一个强化学习原理，该原理仅在测试功能的用户定义空间沿使用它们的有效性来近似钟声方程。我们专注于使用功能近似的无模型离线RL应用程序，我们利用这一原理来得出置信区间以进行非政策评估，并在规定的策略类别中优化了对策略的优化。我们证明了关于我们的政策优化程序的甲骨文不平等，就任意比较策略的价值和不确定性之间的权衡而言。测试功能空间的不同选择使我们能够解决共同框架中的不同问题。我们表征了使用我们的程序从政策转移到政策数据的效率的丧失，并建立了与过去工作中研究的浓缩性系数的连接。我们深入研究了具有线性函数近似的方法的实施，即使贝尔曼关闭不结束，也可以通过多项式时间实现提供理论保证。

我们研究了具有一般函数近似的部分可观察的MDP（POMDP）的外部评估（OPE）。现有的方法，例如顺序重要性采样估计器和拟合-Q评估，受POMDP中的地平线的诅咒。为了解决这个问题，我们通过引入将未来代理作为输入的未来依赖性值函数来开发一种新颖的无模型OPE方法。未来依赖性的价值函数在完全可观察的MDP中起着与经典价值函数相似的角色。我们为未来依赖性价值作为条件矩方程提供了一个新的Bellman方程，将历史记录代理用作仪器变量。我们进一步提出了一种最小值学习方法，以使用新的Bellman方程来学习未来依赖的价值函数。我们获得PAC结果，这意味着我们的OPE估计器是一致的，只要期货和历史包含有关潜在状态和Bellman完整性的足够信息。最后，我们将方法扩展到学习动力学，并在POMDP中建立我们的方法与众所周知的光谱学习方法之间的联系。

我们研究了对识别的非唯一麻烦的线性功能的通用推断，该功能定义为未识别条件矩限制的解决方案。这个问题出现在各种应用中，包括非参数仪器变量模型，未衡量的混杂性下的近端因果推断以及带有阴影变量的丢失 - 与随机数据。尽管感兴趣的线性功能（例如平均治疗效应）在适当的条件下是可以识别出的，但令人讨厌的非独家性对统计推断构成了严重的挑战，因为在这种情况下，常见的滋扰估计器可能是不稳定的，并且缺乏固定限制。在本文中，我们提出了对滋扰功能的受惩罚的最小估计器，并表明它们在这种挑战性的环境中有效推断。提出的滋扰估计器可以适应灵活的功能类别，重要的是，无论滋扰是否是唯一的，它们都可以融合到由惩罚确定的固定限制。我们使用受惩罚的滋扰估计器来形成有关感兴趣的线性功能的依据估计量，并在通用高级条件下证明其渐近正态性，这提供了渐近有效的置信区间。

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

我们研究马尔可夫决策过程（MDP）框架中的离线数据驱动的顺序决策问题。为了提高学习政策的概括性和适应性，我们建议通过一套关于在政策诱导的固定分配所在的分发的一套平均奖励来评估每项政策。给定由某些行为策略生成的多个轨迹的预收集数据集，我们的目标是在预先指定的策略类中学习一个强大的策略，可以最大化此集的最小值。利用半参数统计的理论，我们开发了一种统计上有效的策略学习方法，用于估算DE NED强大的最佳政策。在数据集中的总决策点方面建立了达到对数因子的速率最佳遗憾。