我们在面对未衡量的混杂因素时研究离线增强学习(RL)。由于缺乏与环境的在线互动,离线RL面临以下两个重大挑战:(i)代理可能会被未观察到的状态变量混淆; (ii)提前收集的离线数据不能为环境提供足够的覆盖范围。为了应对上述挑战,我们借助工具变量研究了混杂的MDP中的政策学习。具体而言,我们首先建立了基于和边缘化的重要性采样(MIS)的识别结果,以确定混杂的MDP中的预期总奖励结果。然后,通过利用悲观主义和我们的认同结果,我们提出了各种政策学习方法,并具有有限样本的次级临时性保证,可以在最小的数据覆盖范围和建模假设下找到最佳的课堂政策。最后,我们广泛的理论研究和一项由肾脏移植动机的数值研究证明了该方法的有希望的表现。
translated by 谷歌翻译
我们研究马尔可夫决策过程(MDP)框架中的离线数据驱动的顺序决策问题。为了提高学习政策的概括性和适应性,我们建议通过一套关于在政策诱导的固定分配所在的分发的一套平均奖励来评估每项政策。给定由某些行为策略生成的多个轨迹的预收集数据集,我们的目标是在预先指定的策略类中学习一个强大的策略,可以最大化此集的最小值。利用半参数统计的理论,我们开发了一种统计上有效的策略学习方法,用于估算DE NED强大的最佳政策。在数据集中的总决策点方面建立了达到对数因子的速率最佳遗憾。
translated by 谷歌翻译
我们研究了一个名为“战略MDP”的新型模型下的离线增强学习,该模型表征了本金和一系列与私有类型的近视药物之间的战略相互作用。由于双层结构和私人类型,战略MDP涉及主体与代理之间的信息不对称。我们专注于离线RL问题,其目标是基于由历史互动组成的预采用数据集学习委托人的最佳政策。未观察到的私人类型混淆了这样的数据集,因为它们会影响委托人收到的奖励和观察结果。我们提出了一种新颖的算法,具有算法工具(计划)的悲观政策学习,该算法利用仪器变量回归的思想和悲观主义原则在一般功能近似的背景下学习近乎最佳的原理政策。我们的算法是基于批判性观察,即主体的行为是有效的工具变量。特别是,在离线数据集中的部分覆盖范围假设下,我们证明计划输出$ 1 / \ sqrt {k} $ - 最佳策略,$ k $是收集的轨迹数量。我们进一步将框架应用于一些特殊的战略MDP案例,包括战略回归,战略强盗和推荐系统中的不合规性。
translated by 谷歌翻译
离线政策评估(OPE)被认为是强化学习(RL)的基本且具有挑战性的问题。本文重点介绍了基于从无限 - 马尔可夫决策过程的框架下从可能不同策略生成的预收集的数据的目标策略的价值估计。由RL最近开发的边际重要性采样方法和因果推理中的协变量平衡思想的动机,我们提出了一个新颖的估计器,具有大约投影的国家行动平衡权重,以进行策略价值估计。我们获得了这些权重的收敛速率,并表明拟议的值估计量在技术条件下是半参数有效的。就渐近学而言,我们的结果比例均以每个轨迹的轨迹数量和决策点的数量进行扩展。因此,当决策点数量分歧时,仍然可以使用有限的受试者实现一致性。此外,我们开发了一个必要且充分的条件,以建立贝尔曼操作员在政策环境中的适当性,这表征了OPE的困难,并且可能具有独立的利益。数值实验证明了我们提出的估计量的有希望的性能。
translated by 谷歌翻译
我们研究了用线性函数近似的加固学习中的违规评估(OPE)问题,旨在根据行为策略收集的脱机数据来估计目标策略的价值函数。我们建议纳入价值函数的方差信息以提高ope的样本效率。更具体地说,对于时间不均匀的epiSodic线性马尔可夫决策过程(MDP),我们提出了一种算法VA-OPE,它使用价值函数的估计方差重新重量拟合Q迭代中的Bellman残差。我们表明我们的算法达到了比最着名的结果绑定的更紧密的误差。我们还提供了行为政策与目标政策之间的分布转移的细粒度。广泛的数值实验证实了我们的理论。
translated by 谷歌翻译
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.
translated by 谷歌翻译
我们在无限地平线马尔可夫决策过程中考虑批量(离线)策略学习问题。通过移动健康应用程序的推动,我们专注于学习最大化长期平均奖励的政策。我们为平均奖励提出了一款双重强大估算器,并表明它实现了半导体效率。此外,我们开发了一种优化算法来计算参数化随机策略类中的最佳策略。估计政策的履行是通过政策阶级的最佳平均奖励与估计政策的平均奖励之间的差异来衡量,我们建立了有限样本的遗憾保证。通过模拟研究和促进体育活动的移动健康研究的分析来说明该方法的性能。
translated by 谷歌翻译
我们研究了具有无限观察和状态空间的部分观察到的马尔可夫决策过程(POMDP)的强化学习,理论上仍然不太研究。为此,我们首次尝试弥合具有线性结构的一类POMDP的部分可观察性和功能近似。详细说明,我们建议在$ O(1/\ Epsilon^2)$情节中获得$ \ epsilon $ - 最佳策略的增强学习算法(通过对抗积分方程或操作装置的乐观探索)。特别是,样品复杂性在线性结构的固有维度上缩放,并且独立于观测和状态空间的大小。 Op-Tenet的样品效率由一系列成分启用:(i)具有有限内存的钟形操作员,该操作员以递归方式表示值函数,(ii)通过对抗性积分对此类操作员的识别和估计方程式具有针对线性结构量身定制的平滑歧视器,以及(iii)通过乐观探索观察和状态空间,该探索基于量化对抗性积分方程的不确定性。
translated by 谷歌翻译
使用悲观,推理缺乏详尽的勘探数据集时的脱机强化学习最近颇具知名度。尽管它增加了算法的鲁棒性,过于悲观的推理可以在排除利好政策的发现,这是流行的基于红利悲观的问题同样有害。在本文中,我们介绍一般函数近似的Bellman-一致悲观的概念:不是计算逐点下界的值的功能,我们在超过设定的与贝尔曼方程一致的功能的初始状态实现悲观。我们的理论保证只需要贝尔曼封闭性作为探索性的设置标准,其中基于奖金的情况下的悲观情绪未能提供担保。即使在线性函数逼近的特殊情况下更强的表现力假设成立,我们的结果由$ \ mathcal {}Ø(d)在其样品的复杂$在最近的基于奖金的方法改善的时候,动作的空间是有限的。值得注意的是,我们的算法,能够自动适应事后最好的偏差 - 方差折中,而大多数现有的方法中需要调整的额外超参数的先验。
translated by 谷歌翻译
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.
translated by 谷歌翻译
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.
translated by 谷歌翻译
强化学习(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总体上,轨迹奖励的效率非常有效。
translated by 谷歌翻译
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.
translated by 谷歌翻译
我们考虑在部分可观察到的马尔可夫决策过程(POMDP)中的违法评估(OPE),其中评估策略仅取决于可观察变量,并且行为策略取决于不可观察的潜在变量。现有的作品无论是假设未测量的混乱,还是专注于观察和状态空间都是表格的设置。因此,这些方法在存在未测量的混淆器的情况下遭受大偏差,或者在具有连续或大观察/状态空间的设置中的大方差。在这项工作中,通过引入将目标策略的价值和观察到的数据分布联系起来,提出了具有潜在混淆的POMDPS的新识别方法。在完全可观察到的MDP中,这些桥接功能将熟悉的值函数和评估与行为策略之间的边际密度比减少。我们接下来提出了用于学习这些桥接功能的最小值估计方法。我们的提案允许一般函数近似,因此适用于具有连续或大观察/状态空间的设置。最后,我们基于这些估计的桥梁功能构建了三种估计,对应于基于价值函数的估计器,边缘化重要性采样估计器和双重稳健的估计器。他们的掺入无血症和渐近性质进行了详细研究。
translated by 谷歌翻译
The offline reinforcement learning (RL) problem is often motivated by the need to learn data-driven decision policies in financial, legal and healthcare applications. However, the learned policy could retain sensitive information of individuals in the training data (e.g., treatment and outcome of patients), thus susceptible to various privacy risks. We design offline RL algorithms with differential privacy guarantees which provably prevent such risks. These algorithms also enjoy strong instance-dependent learning bounds under both tabular and linear Markov decision process (MDP) settings. Our theory and simulation suggest that the privacy guarantee comes at (almost) no drop in utility comparing to the non-private counterpart for a medium-size dataset.
translated by 谷歌翻译
在马尔可夫决策过程(MDP)中,可能存在不可观察的混杂因素并对数据生成过程产生影响,因此经典的非政策评估(OPE)估计器可能无法识别目标策略的真实价值函数。在本文中,我们研究了与可观察的仪器变量混杂的MDP中OPE的统计特性。具体而言,我们根据仪器变量提出了一个两阶段估计器,并在具有线性结构的混杂MDP中建立了其统计属性。对于非反应分析,我们证明了一个$ \ Mathcal {o}(n^{ - 1/2})$ - 错误绑定了$ n $是样本的数量。对于渐近分析,我们证明了两阶段估计量在渐近正常上,典型速率为$ n^{1/2} $。据我们所知,我们是第一个通过仪器变量显示混合线性MDP的两阶段估计量的统计结果。
translated by 谷歌翻译
我们在使用函数近似的情况下,在使用最小的Minimax方法估算这些功能时,使用功能近似来实现函数近似和$ q $ functions的理论表征。在各种可靠性和完整性假设的组合下,我们表明Minimax方法使我们能够实现重量和质量功能的快速收敛速度,其特征在于关键的不平等\ citep {bartlett2005}。基于此结果,我们分析了OPE的收敛速率。特别是,我们引入了新型的替代完整性条件,在该条件下,OPE是可行的,我们在非尾部环境中以一阶效率提出了第一个有限样本结果,即在领先期限中具有最小的系数。
translated by 谷歌翻译
我们建议和分析一个强化学习原理,该原理仅在测试功能的用户定义空间沿使用它们的有效性来近似钟声方程。我们专注于使用功能近似的无模型离线RL应用程序,我们利用这一原理来得出置信区间以进行非政策评估,并在规定的策略类别中优化了对策略的优化。我们证明了关于我们的政策优化程序的甲骨文不平等,就任意比较策略的价值和不确定性之间的权衡而言。测试功能空间的不同选择使我们能够解决共同框架中的不同问题。我们表征了使用我们的程序从政策转移到政策数据的效率的丧失,并建立了与过去工作中研究的浓缩性系数的连接。我们深入研究了具有线性函数近似的方法的实施,即使贝尔曼关闭不结束,也可以通过多项式时间实现提供理论保证。
translated by 谷歌翻译
离线增强学习(RL)可以从先前收集的数据中进行有效的学习,而无需探索,这在探索昂贵甚至不可行时在现实世界应用中显示出巨大的希望。折扣因子$ \ gamma $在提高在线RL样本效率和估计准确性方面起着至关重要的作用,但是折现因子在离线RL中的作用尚未得到很好的探索。本文研究了$ \ gamma $在离线RL中的两个明显影响,并通过理论分析,即正则化效果和悲观效应。一方面,$ \ gamma $是在现有离线技术下以样本效率而定的最佳选择的监管机构。另一方面,较低的指导$ \ gamma $也可以看作是一种悲观的方式,我们在最坏的模型中优化了政策的性能。我们通过表格MDP和标准D4RL任务从经验上验证上述理论观察。结果表明,折现因子在离线RL算法的性能中起着至关重要的作用,无论是在现有的离线方法的小型数据制度下还是在没有其他保守主义的大型数据制度中。
translated by 谷歌翻译
我们研究了具有连续状态的可观察到的马尔可夫决策过程(POMDPS)的非政策评估问题(OPE)。由最近提出的近端因果推理框架的动机,我们开发了一个非参数识别结果,以通过时间依赖性代理变量的帮助通过所谓的V-bridge函数来估算策略值。然后,我们开发一种拟合的Q评估类型算法来递归估算V桥功能,其中每个步骤都解决了非参数仪器变量(NPIV)问题。通过分析这个具有挑战性的顺序NPIV问题,我们建立了用于估计V桥功能的有限样本误差界限,并因此根据样本量,地平线和所谓(本地)度量来评估策略值,以评估策略值每个步骤都不适。据我们所知,这是非参数模型下POMDP中OPE绑定的第一个有限样本误差。
translated by 谷歌翻译