在本文中，我们提出了一种新的分支强化学习(分支RL)模型，并研究了该模型的后悔最小化(RM)和无奖励探索(RFE)指标。与标准的RL(每个情节的轨迹都是一个单一的h步路径)不同，分支RL允许代理在一个状态中采取多个基本动作，以便转换分支到多个相应的后续状态，因此它生成了一个树状结构的轨迹。该模型在分级推荐系统和在线广告中有重要的应用。对于分支RL，我们建立了新的Bellman方程和关键引理，即分支值差引理和总方差的分支定律，并在指数大轨迹下将总方差限定为O(H2)。对于RM和RFE度量，我们分别提出了高效的计算算法BranchVI和BranchRFE，并导出了近似匹配的上界和下界。尽管轨迹为指数级大，但我们的结果在问题参数上仅为多项式。

1.介绍

强化学习（Reinforcement Learning）是一个经典的在线决策模型。在强化学习中，智能体与未知的环境进行交互，以获得最大的累积奖励。传统强化学习是一个单路径的序列决策模型，智能体在一个状态下只选择一个动作。然而，在推荐系统、在线广告等许多现实应用中，用户们往往会一次选择多个选项，每个选项会触发对应的后继状态，例如，在基于类别的购物推荐中，系统往往会先推荐一些商品的一级类别，当某个一级类别被用户点击时，系统会进一步推荐一些二级类别。在一次购物中，用户可能会选择（触发）多条类别-商品路径，如用户可能会触发“办公设备-打印机-激光打印机”和“办公设备-扫描仪-平板扫描仪”这两条路径。

为了处理这种涉及多个动作和后续状态的场景，我们提出了一个新的分支强化学习(分支RL)框架，这是一个情景树结构的前向模型。在每个情节中，一个代理从一个初始状态开始，并采取一个包含多个基本操作的超级操作，在这个状态下的每个基本操作都有可能被触发。对于每个基于状态的动作对，如果成功触发，代理会收到一个奖励并转换到下一个状态;否则，如果它没有被触发，代理将接受零奖励并转换到与零奖励相关的吸收状态。因此，转换扩展到多个继承者状态。在第二步中，对于每个分支状态，代理还选择一个超操作，该超操作包含多个具有触发概率的基本操作。她只从触发的基于状态的动作对中获得奖励，而每个基于状态的动作对都会转换到对应的下一个状态。然后，第二步中的转换扩展到更多的后续状态。通过类推，直到最后一步，她都是穿过一个h层树状结构的轨迹，并且只在触发状态基动作对时收集奖励。

与每个轨迹都是单一h步路径的标准(情景)RL不同，分支RL的轨迹是一个h层触发树，每层的状态和动作呈指数增长。此模型允许代理一次执行多个基本操作并处理多个后续状态。它可以应用于许多分层决策场景，如基于类别的推荐Fu等[2021]和广告Kang等[2020]。

在分支RL模型下，我们研究了RL文献中两个流行的指标:(i)后悔最小化(RM) Jaksch等人[2010]，Azar等人[2017]，Zanette和Brunskill[2019]，我们希望最小化采取最优策略获得的奖励与代理实际获得的奖励之间的差异。(ii)无奖励探索(RFE) Jin等人[2018]，Kaufmann等人[2021]，M´enard等人[2021]，我们在不观察奖励的情况下进行探索，以便准确估计模型，以便对于任何给定的奖励函数，我们可以使用估计模型规划一个接近最优的策略。RFE的性能是通过探索过程中使用的片段数来衡量的(即样本复杂性)。

我们的工作面临以下挑战:(i)由于分支RL是一个树状结构的正向模型，与标准RL有很大的不同，现有的标准RL分析工具，如Bellman方程、值差引理和总方差定律，不能直接应用于我们的问题。(ii)对于指数级大的轨迹，分析总方差并导出紧密(多项式)遗憾和样本复杂性保证是具有挑战性的。(iii)由于可能的超操作的数量可以组合起来很大，如何设计一个计算效率高的算法，避免对所有超操作的幼稚枚举是另一个挑战。

为了应对上述挑战，我们建立了新的分析工具，包括分支Bellman方程、分支值差分引理和总方差分支定律，并在指数大轨迹下仅用O(H2)(有一个温和的假设)约束总方差。我们还提出了计算效率高的RM和RFE度量算法，并提供了近似匹配的上界和下界，尽管轨迹为指数级大，但在问题参数上仅为多项式。由于篇幅所限，我们将所有证明提交至附录。

综上所述，我们在本文中的贡献如下:

我们提出了一种新的分支强化学习(分支RL)框架，这是一个情景h层树状结构的前向模型，在分层推荐和广告中有重要的应用。在分支RL中，我们调查了两个流行的参数，即后悔最小化(RM)和无奖励探索(RFE)。
我们建立了新的RL分支技术，包括分支Bellman方程、分支值差引理和总方差分支定律，并在指数大轨迹下仅用O(H2)(有一个温和的假设)来约束总方差。
对于RM和RFE度量，我们分别设计了计算高效的算法BranchVI和BranchRFE，并建立了近似最优的上界和下界，即使是指数级大轨迹，问题参数也只能是多项式。当我们的问题减少到标准的RL，我们的结果是最先进的。

2.相关工作

下面我们将回顾标准(章节式和表格式)RL与遗憾最小化(RM)和无奖励探索(RFE)指标的文献。

标准RL-RM

对于后悔最小化(RM)度量，Jaksch等人[2010]提出了一种算法，该算法在转移概率上添加了乐观红利，并实现了一个后悔界，与Jaksch等人[2010]，Osband和Van Roy[2016]的下界相比，因子H, S存在差距。这里H是事件的长度，S是状态数。Agrawal和Jia[2017]使用后验抽样得到改进的后悔界。阿扎尔等[2017]直接建立值函数的置信区间，而不是转移概率，并提供第一最优后悔。Zanette & Brunskill[2019]设计了一种基于乐观和悲观值函数的算法，在不需要领域知识的情况下实现了更紧密的问题相关后悔边界。以上工作主要是基于模型的RL算法。还有Jin等人[2018]，Zhang等人[2020]研究了基于q学习的无模型算法，带有探索奖励或优势函数。

标准RL-RFE

Jin等人[2020]引入了无奖励探索(RFE)度量，并设计了一种算法，该算法运行现有RM算法Zanette & Brunskill[2019]的多个实例，其样本复杂度与Jin等人[2020]、Domingues等人[2021]在因子H, S. Kaufmann等人[2021]中提出了一种算法，该算法建立了值函数估计误差的置信上界，并改善Jin等人[2020]的样本复杂度。M´enard等人[2021]通过应用经验Bernstein不等式和总体估计误差的上限，实现了接近最优的样本复杂性。

标准RL和分支RL之间存在着巨大的差异。分支RL的指数级大轨迹给开发Bellman方程和关键引理、设计计算效率高的算法和导出最优(多项式)边界带来了独特的挑战。现有的RL算法和分析不能用于解决我们的挑战。

3.问题公式化

在本节中，我们提出了分支强化学习(分支RL)的正式形式。

分支马尔可夫决策过程(分支MDP)

分支马尔可夫决策过程。我们考虑一个由元组M = (S, Auniv, A, m, H, q, p, r)定义的情景分支MDP。这里S = Sreg∪{S⊥}是基数为S的状态空间，Sreg是规则状态集，S⊥是一个结束状态，是一个零回报的吸收状态。Auniv是基础动作集合，表示推荐中所有可行项的集合。设N:= |Auniv|表示基本动作的数量。一个超级动作A⊂Auniv由m (m≤N)个基本动作组成，代表一个推荐列表。A是所有可行的超级动作的集合，可以组合起来很大。H是一集的长度。在本文中，我们将一个超级动作简称为动作，称(s, a)∈S× Auniv为基于状态的动作对，称(s, a)∈s \ {s⊥}× Auniv为普通的基于状态的动作对。

q(s, a)为基于状态的动作对(s, a)∈S× Auniv的触发概率。对于任意(s', s, a)∈s × s × Auniv, p(s0|s, a)是基于状态的动作对(s, a)上过渡到状态s0的概率。r(s, a)∈[0,1]是对(s, a)∈s × Auniv的报酬。我们假设奖励函数r是确定的，正如许多先前的RL工作Azar等[2017]、Jin等[2018]、Zhang等[2020]，我们的工作可以很容易地推广到随机奖励。参数q, p, r是时间齐次的，即对于不同步长h∈[H]具有相同的定义。结束状态S⊥是零回报的，总是会回归到自身，即q(s⊥，a) = 0, p(s⊥|s⊥，a) = 1, r(s⊥，a) = 0。我们将策略π定义为H个函数的集合{π H: S→A} h∈[H]， K为集数。。。

基于字符串的符号

如图1所示，在分支RL中，每个情景的轨迹是一个m-ary树，其中有H层(步骤)，每层h∈[H]有mh−1个状态(节点)和mh个基于状态的动作对(边)。

我们使用以下基于字符串的符号来表示轨迹:

在第h层中的每个树节点都有一个字符串索引<ih1，… ih−1>

这个地方我感觉是第h层的根节点

第一层的根节点为空串∅,而且ih1，…， ih−1∈{1,2，…, m}。

我的想法是每个节点都有一个索引，从上到下。。。这个时候h层还没有连接到字符串。。。

这个节点的m个子节点的索引将ih∈[m]连接到字符串，使其成为<ih1，…， ih−1,ih>，其中ih表示该节点是节点<ih1，… ih−1>的第ih-th。

⊕是字符串的拼接操作，i⊕h表示任意i∈[m]， h∈[H]的h个字符串的拼接。

对于任意字符串σ， |σ|表示其长度，因此状态sσ在步长|σ| + 1处。

字符串σ，比如h=2,, |σ|表示其长度===2，因此状态sσ在步长|σ| + 1处。 s2的状态在3333333。。

图1:用m = 2举例说明分支RL

m = 2 第三层（h）有4 (mh−1)个状态。。。。有8 (mh)个边

在线游戏

在每集k∈[K]中，代理在开始时选择策略πk，并从初始状态s∅开始。在第1步，她选择了一个动作A∅= {a1，…， am}根据πk1。每个基于状态的动作对(s∅，ai)。对于i∈[m]，有q(s∅，ai)被触发的概率。如果触发成功，agent获得奖励r(s∅，ai)，此状态基动作对过渡到下一个状态si ~ p(·|s∅，ai);否则，如果没有成功触发，她将获得零奖励，这个基于状态的动作对将转移到结束状态。

因此，第1步的转换分支到m个后继状态s1，…sm。

在第2步，对于每个状态si (i∈[m])，她选择一个动作Ai = {ai1,ai2，…， aim}根据πk2。那么在第2步有m2个状态基动作对{(si, aij) i,j∈[m]，每个动作对的触发概率为q(si, aij)。如果触发成功，代理收到奖励r(si, aij)，这一对转换到下一个状态sij ~ p(·|si, aij); 否则，她将得不到任何奖励，这双鞋会过渡到s⊥。

然后，步骤2的跃迁分支到m2的后继状态{sij}i,j∈[m]。

这一集类推如下步骤3，…， h在轨迹树中，agent在某一节点上⊥达到s，则在这条分支上没有任何奖励(这就是所谓的“结束状态”)。

=========================================================================

对于无限的触发概率q，轨迹中常规(触发)状态基动作对的数量可以是指数级的，任何算法都必须遭受Ω(exp(H)√SN K)的遗憾(详见附录C.6.1)。为了限制触发的基于状态的动作对的数量，我们引入了以下技术假设:

假设1(轻微的触发概率)

假设1是温和的，因为在现实世界的应用中，例如推荐系统Fu等人[2021]和在线广告Kang等人[2020]，用户通常只被推荐列表中的少数项目吸引并点击。此外，在多步骤(例如，基于类别的)推荐中，用户的兴趣最终(在预期中)通常会收敛到单个分支。

分支值函数与Bellman方程

在策略π下，从h步到这个分支结束的某些状态s的预期累积奖励。

⊕是字符串的拼接操作，i⊕h表示任意i∈[m]， h∈[H]的h个字符串的拼接。

对于任意字符串σ， |σ|表示其长度，因此状态sσ在步长|σ| + 1处。

这里σ是步长h的任意状态的索引字符串，因此σ∈{1⊕(h−1)，…, m⊕(h−1)}。

有效枚举H−h+1层的所有树节点。对轨迹取期望，其依赖于触发分布q、转移分布p和策略π。

表示策略π下，从步骤h开始到分支结束的某些状态-动作对(s, A)的预期累积奖励。由s⊥的r, p, q的定义可知，对于任意A∈A, h∈[H], π， Vπ⊥= Qπ(s⊥)= 0

由于S、A和H都是有限的，所以存在一个确定性的最优策略π *，它的最优值是V * H (S) = supπ V π H (S)，对于任意S∈S和H∈[H]。然后，我们可以建立Bellman(最优性)方程:

在分支体验体验学习的框架下，我们考虑了两个重要的体验体验学习设置，即后悔最小化(分支体验体验学习)和无奖励探索(分支体验体验学习)。

遗憾最小化(RM)

在分支RL- RM中，代理人玩了K集的分支RL游戏，目标是尽量减少后续遗憾。。。

鼓励不劳而获地探索(RFE)

RL-RFE分支包括勘探和规划两个阶段。

(i)在探索阶段，给定固定的初始状态s∅，代理在不观察奖励函数r的情况下进行分支RL博弈，并估计一个触发和过渡模型(ˆq，ˆp)。

(ii)在计划阶段，给agent一个奖励函数r，并在她的估计模型(ˆq，ˆp)下计算出关于r的最优策略ˆπ *。给定一个精度参数ε和一个置信度参数δ，她需要保证对于任何给定的奖励函数r，ˆπ *关于r的策略是ε-最优的，即:

概率至少为1−δ。我们通过样本复杂度来衡量性能，即在探索阶段使用的集数，以保证任意给定r的ε-最优策略。

特别地，当m = 1时，我们的分支RL降低为带转移概率paug的标准情景的RL，使paug(s⊥，|s, a) = 1−q(s, a)， paug(s’|s, a) = q(s, a)p(s‘|s, a)，任意s0 ！= s⊥。在这种情况下，我们的结果与RM和RFE设置中标准RL的最新结果相匹配。

4.分支马尔可夫决策过程的性质研究

在介绍RL分支算法之前，在本节中，我们首先研究了分支MDP的特殊结构性质，这对于推导紧密(多项式)遗憾和样本复杂性保证是至关重要的。

4.1分支值差引理和总方差定律

与标准情景轨迹是H步路径MDP不同，分支MDP的轨迹是一个m元树，每个节点是一个状态，每个边是一个状态基动作对。因此，标准MDP中的许多分析工具，如值差引理和总方差定律不能直接应用于分支MDP。为了解决这个问题，我们建立了新的分支MDP的基本技术，包括分支值差引理和总方差分支律。

首先，我们提出一个分支值差引理。

引理2(分支值差分引理)

对于任意两个分支MDP M’(S, Auuniv, A, m, H, q‘, p’, r)和M‘’(S, Auuniv, A, m, H, q‘, p’, r)，相同策略π下的值差满足此条件

使用Lemma 2, M‘和M''分别为乐观和真实模型，我们可以用乐观和真实触发概率和转移概率之间的偏差来限制乐观和真实值之间的差异，期望相对于真实模型。。。。

然后，我们给出了一个总方差的分支律，它是分析转移估计误差的关键

引理3(总方差分支定律)

对于任何政策π，

这里var表示v相对于s的方差，该方差取决于触发概率q和跃迁概率p(·|sσ， aσ⊕')，条件于(sσ， aσ ')。

备注1

引理3表明，在分支MDP下，所有状态基动作对的条件方差之和等于考虑整个轨迹的总体方差，如式(2)所示。此外，总体方差可以由式(3)所示的规则(触发)状态的总数所限制。

由引理3可知，对于与条件方差之和相关的跃迁估计误差，可以对轨迹树中触发状态的总数进行约束(下文将讨论)。

4.2触发状态数

在本节中，我们展示了假设1只约束触发分布的第一阶矩，我们可以同时约束轨迹树中触发状态数的第一阶矩和第二阶矩。。。。。

引理4(触发状态数)

备注2

Eq.(4)给出了值函数V π ≤【】≤H，对于任意s∈S, h∈[H],π。此外，式(5)提供了总体方差的一个明显的上界，以及转移的条件方差之和(将式(5)代入引理3)。据我们所知，第二个矩的结果是新的。

引理4表明，尽管分支MDP中的节点呈指数增长，但其值和总体方差(估计误差)不会爆发。这个关键属性使我们能够避免指数级的遗憾或样本复杂性。

触发状态的新分析

引理4的分析是非平凡的。我们首先将所有常规触发概率放宽到1/m，然后分别研究每个步骤的触发状态数。虽然我们可以证明每一步触发状态的数量是一个条件二项随机变量，但它们和的分布太复杂了，无法表达。这在分析触发状态总数的第二时刻时带来了不小的挑战。为了解决这一挑战，我们研究了任何两个步骤之间的触发状态的相关性，通过利用分支MDP的结构。

素描的证据

在假设1下，要约束任意分支MDP和策略π的触发(规则)状态总数，只需在松弛模型M*下即q(s, a) = q *:= 1 M∈s \ {s⊥}× auuniv。

令ωh表示M*下每一步h的触发状态数，ω:= PH h=1 ωh。下面证明E[ω]≤H, E[ω2]≤3H2。

现在，挑战在于对于任意1 < i, j < h，如何定E[ωiωj]。设Wσ为一个伯努利随机变量，表示对于任意索引弦σ是否触发状态sσ。那么，我们可以将E[ωiωj]写成

这里(a)来自轨迹树的对称性。(b)是由于在第j步，s1⊕(i−1)的子态依赖于它，其他的子态独立于它，对于任何σ， σ', E[WσWσ'] = Pr[Wσ = 1, Wσ0 = 1]。将式(7)代入式(6)，得到E[ω2]≤H(H+1) 2 + 4h (H−1)2≤3H2。由此，我们得到引理4。

5.基于遗憾最小化的分支强化学习

在本节中，我们研究了分支RL-RM，并提出了一种高效算法BranchVI，对于足够大的k具有近似最优后悔保证，并建立了下界来验证BranchVI的最优性。

5.1算法BranchVI

分支RL的算法设计面临两个独特的挑战:

(i)计算效率。在标准RL动作空间A可以是组合大的。。

(ii)紧乐观估计器中显式维护Q函数是低效的。天真地采用标准RL算法，并分别在触发和转移概率上添加乐观的奖励，将导致宽松的后悔限制(详见附录a)。为了应对这些挑战，BranchVI只维护Q函数的组件，使用最大化oracle直接计算V函数。此外，BranchVI认为触发器和过渡分布是一个整体，并添加了一个复合奖励。

BranchVI(算法1)的过程如下:

在每个章节k中，我们首先计算经验触发和转移概率ˆqk，ˆpk，触发概率qk，ˆpk的加成，以及触发和转移概率bk,qpV的复合加成(第6-8行)。其中nk(s, a)、J ksum(s, a)和P ksum(s0|s, a)分别表示访问次数(s, a)、成功触发次数(s, a)和agent从(s, a)到事件k过渡到s’的次数。然后，我们计算一个分量函数f kh (s, a)，它表示每个(s, a)对值函数的贡献(第9行)

我们允许BranchVI访问一个最大化oracle，该oracle可以有效地计算任意向量的maxA∈a P a∈a w(a)和argmaxA∈a P a∈a w(a)。由于目标函数P a∈a w(a)是线性的，因此对于许多组合决策类，如所有m-基数子集和m-基数匹配，都存在这样的oracle。通过使用这个oracle和f kh (s, a)，我们可以有效地计算出乐观值函数¯V kh (s)和策略πkh，并进一步计算悲观值函数V kh(行11-13)。在对所有s, h求出¯V kh(s)， V kh， πkh(s)之后，我们在集k执行策略πk(第16行)。

计算效率

我们注意到BranchVI的计算复杂度是O(S2N)，而不是简单地采用标准RL算法所带来的昂贵的O(S2|A|)。这个优点是由于BranchVI只维护组件函数而不是Q函数，并利用最大化oracle直接计算V函数。。。

5.2BranchVI的后悔上界

现在我们为BranchVI提供后悔担保

定理5(遗憾上界)

在概率不小于1−δ的情况下，对于任意集K > 0，算法BranchVI的遗憾限定在O(H√SN K log(SN H(mH) δ)) ，特别是当K≥mH时，后悔的范围为

备注3

定理5表明，尽管分支RL的轨迹是指数级大的，但遗憾的是，BranchVI在问题参数上只有多项式。对于足够大的K，使K≥mH，定理5匹配下界(在第5.3节中提出)到对数因子。此外，当分支RL减少到标准RL(即m = 1)时，我们的结果也符合最先进的水平。。。

分支后悔分析

分支后悔分析。与标准相比，我们在第4节中基于分支RL的特殊结构特性推导出了树状结构的后悔分析。

利用分支值差引理(引理2)，我们可以将遗憾分解为每个正则状态基动作对的估计误差，如下所示:

这里w表示概率(sσ， aσ⊕l)= (s, a)在插曲k中，和˜qk和˜pk分别表示乐观的触发和过渡概率。在此分解中，我们分别处理触发奖励(第1项)和触发转移(第2项，第3项)的估计误差，并将触发和转移概率作为一个整体分布(第2项，第3项)考虑。主导项是第2项第3项，代表触发转移的估计误差，依赖于条件方差的总和。利用总方差的分支律(引理3)和触发状态的二阶矩界(引理4)，我们可以仅用O(H2)来约束第2,3项，尽管存在指数状态基作用对。

我们注意到有必要将触发奖励和触发过渡分开处理，并将触发和过渡作为奖励设计的整体分布(第8行)和遗憾分解。标准RL算法的一个天真的改编，它分别增加了触发和转移概率的奖金，即用f kh (s, A)←?ˆqk(s, A) + bk,q(s, A)?·(r(s, a) +ˆpk(·|s, a)>¯V kh+1 + bk,pV (s, a))，将在后悔范围内多出一个因子√H。请参阅附录A了解更多讨论。

5.3后悔下界

在本节中，我们给出了问题参数为多项式的分支RL-RM的下界，并证明了BranchVI的最优性。

定理6(遗憾下界)

存在一个分支RL-RM的实例，其中任何算法都必须有Ω(H√SN K)遗憾。

备注4

定理6验证了对于足够大的K, BranchVI的后悔(定理5)是接近最优的，并揭示了在分支RL中，即使是指数大的轨迹，多项式后悔也是可以实现的，并且是紧密的。。。

分支后悔下界分析

不像以前的标准的情景RL作品，直接适应基于直径的下界的情景设置，我们推出了一个新的下界分析的分支RL- rm。我们构造了一个硬实例，其中一个代理统一进入Θ(S)的“强盗状态”之一，即具有最优动作和次优动作的状态，此后总是过渡到一个“齐次状态”，即具有齐次动作的状态。那么，如果代理在强盗状态下犯了错误，她将在这一集遭受Ω(H)的遗憾。通过限定该硬实例与统一实例之间的kl -散度，我们可以得到一个期望的下界。

6.带有无奖励探索的分支强化学习

在本节中，我们研究了分支RL-RFE，并开发了一个高效的算法BranchRFE和样本复杂度的近匹配上界和下界。

6.1算法BranchRFE

每集BranchRFE估计触发和过渡概率，并计算估计误差Bkh(s)， Bkh(s)表示从步骤h到H触发和过渡的累积方差。一旦总估计误差Bk1 (s∅)缩小到要求的精度以下，BranchRFE返回估计模型(ˆqk，ˆpk)。给定任意奖励函数r，在(ˆqk，ˆpk)下关于r的最优策略ˆπ *是ε-最优的，即Vˆπ * 1 (s∅;r)≥V∗1 (s∅;R)−ε，概率至少为1−δ。

我们对BranchRFE(算法2)的描述如下:

在每一集k中，对于每一步h, BranchRFE首先估计触发器和转移概率ˆqk，ˆpk(第6、7行)，并计算每个状态基动作对的分量估计误差gkh(s, a)(第8行)。

然后，与BranchVI类似，我们利用最大化oracle有效地找到最大估计误差(探索最必要的动作)为πkh(s)的动作，并将该最大误差分配给Bkh(s)(第10、11行)。如果总估计误差pBk1 (s∅)(代表整个轨迹的触发和转场标准差)的方根小于ε/2, BranchRFE停止并输出估计模型(ˆqk，ˆpk)(第14行);否则，根据计算出的策略πk继续探索(第15行)。

BranchRFE的计算复杂度也是O(S2N)而不是O(S2|A|)，因为它只计算状态基作用对的分量估计误差，而不枚举超作用，并利用最大化oracle计算πkh(s)和Bkh(s).......

6.2 BranchRFE的样本复杂度上界

现在我们展示BranchRFE的样本复杂性。我们说分支RL-RFE的算法是(δ， ε)正确的，如果它返回一个估计模型(ˆq，ˆp)，这样给定任何奖励函数r，(ˆq，ˆp)下关于r的最优策略是ε-最优的，概率至少为1−δ。

定理7(样本复杂度上界)

对于任意ε > 0和δ∈(0,1)，算法BranchRFE是(δ， ε)-正确的。此外，BranchRFE中使用的集数以1−δ的概率为界

备注5

定理5表明，即使在分支RL中具有指数级大的轨迹，BranchRFE只需要多项式次就可以确保任意奖励函数的ε-最优策略。这个样本复杂度对于对数因子内足够小的δ是最优的(与第6.3节中给出的下界相比)。此外，当退化到标准RL(即m = 1)时，我们的结果也符合最先进水平

分支样本复杂度分析

分支样本复杂性分析。

不同于只对单个h步路径上的估计误差进行定界的标准RL，分支RL需要对轨迹树中所有状态基动作对的估计误差进行展开和分析。在我们的分析中，我们利用分支MDP的特殊结构性质，如总方差的分支律(引理3)和触发状态的二阶矩界(引理4)，巧妙地对整个轨迹树的总估计误差进行了界。尽管轨迹呈指数级大，但在问题参数上我们得到的样本复杂度仅为多项式。

6.3样本复杂度下界

定理8(样本复杂性下界)

存在一个分支RL-RFE的实例，其中任何(δ， ε)-正确的算法需要Ω(H2SN ε2 log δ−1)轨迹。

备注6

定理8证明BranchRFE(定理7)在δ足够小的情况下可以达到接近最优的样本复杂度，并且在分支RL-RFE中可以达到多项式的样本复杂度。

7.结论与未来工作

在本文中，我们提出了一个新的分支RL模型，同时考虑了后悔最小化和无奖励探索指标。

不同于标准的RL，在标准的RL中，每个情节都是一个单一的h步路径，分支RL是一个树状结构的向前模型，它允许在一个状态中有多个基本动作和多个后续状态。对于分支RL，我们构建了新的基本分析工具，并仔细地确定了总体方差。

我们设计了高效的算法，并提供了近乎最优的上界和下界。

有许多有趣的方向可以探索。

一个方向是去除定理5中的因子log(mH)，以改善小k的遗憾界。另一个方向是用线性函数逼近来研究分支RL，即，用线性形式表示关于(s, a)特征向量的值函数

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/867232