在具有不可观测状态和受限决策周期的马尔可夫匪徒中学习

# 马尔可夫赌博机中基于非可观测状态与约束决策时段的学习  
来源：https://arxiv.org/html/2606.27448  

Thomas Hira¹, Victor Boone¹*, Urtzi Ayesta², Ina Maria Verloop²  
¹IRIT, 图卢兹大学, CNRS, 图卢兹 INP, 法国图卢兹  
²Ikerbasque-UPV/EHU, 巴斯克大学, 西班牙毕尔巴鄂  
（2026年3月）  

###### 摘要  
本文研究了马尔可夫赌博机中带有*非可观测状态*以及可能存在*约束*决策时段的遗憾最小化问题。研究聚焦于一个“纯”遗憾基准，将学习算法的性能与最优*纯策略*进行比较——该策略类似于随机赌博机的最优策略，从头到尾选择最优臂且从不切换。我们引入了一种对闲息式马尔可夫赌博机的推广——*自退化马尔可夫赌博机*，其中纯策略总是渐近最优的。我们证明，在无先验知识的情况下，对于每个赌博机实例，那些很少切换臂的算法的遗憾必然超对数增长，即 Ω(log(T))，其中 T 是学习时域。尽管对数区间不可达，我们设计了 UCB-NOM，一种受 UCB 启发的乐观算法，其遗憾接近对数级别。最后，我们证明，如果以臂的偏差函数上界形式提供马尔可夫赌博机的先验知识，UCB-NOM 的适当实例化可实现 O(log(T)) 的遗憾。我们进一步表明，该先验知识允许 UCB-NOM 具有 O(√(T log T)) 的 worst-case 遗憾界。值得注意的是，我们的遗憾界不依赖于底层马尔可夫链的状态数。我们的结论表明，在自退化马尔可夫赌博机中，状态不可观测性仅是一个轻微的障碍。  

## 1 引言  
## 2 学习非可观测马尔可夫赌博机  
本文首先描述学习问题并引入记号。我们的学习问题是一类马尔可夫赌博机（第 2.1 节），其中状态不可观测，且决策时段可能受约束。在第 LABEL:section_pure_policies 节中，我们通过识别那些纯策略实际上是最优的 restless 赌博机子类来激励将*纯策略*作为基准。最后，在第 2.2 节中，我们激励关注那些很少切换臂的学习算法。  

### 2.1 具有决策时段的非可观测马尔可夫赌博机  
我们考虑一个带有臂集 A 的马尔可夫赌博机，其中每个臂 a ∈ A 由一个马尔可夫决策过程 M_a ≡ (S_a, {0,1}, ν_a, p_a^0, p_a^1, s_a^{\text{init}}) 建模，具有*激活/非激活*动作、状态空间 S_a、固定初始状态 s_a^{\text{init}}、与动作选择无关的奖励函数 ν_a: S_a → P([0,1])，以及两个转移核 p_a^0, p_a^1: S_a → P(S_a)，它们根据激活与否控制状态的演化。平均奖励记为 r_a(s_a) := ∫ x dν_a(s_a)(x)。所得系统通过并行捆绑各臂得到 M ≡ (M_a)_{a∈A}。  

控制器与系统之间的交互如下：在时刻 t ≥ 1，控制器选择*单一*臂 A(t) ∈ A 进行激活，系统状态演化如下：  
S_a(t+1) ∼ { p_a^1(S_a(t)) 若 A(t)=a; p_a^0(S_a(t)) 若 A(t)≠a; }  
此外，对于 a=A(t)，立即获得奖励 R(t+1) ∼ ν_a(S_a(t))¹，独立于状态的生成。按惯例，R(1)=0。所有臂在给定当前状态和激活臂的条件下独立演化。后续中，臂 a 的*拉动次数*记为 N_a(T) := ∑_{t=1}^{T-1} 1(A(t)=a)。为简化论述，我们进一步假设激活下的转移核 p_a^1 是单链的——这一假设在 restless 马尔可夫赌博机中相当标准。  

###### 假设 1. 对每个 a ∈ A，p_a^1 是*单链*的，即它有一个唯一的状态常返分量。  

#### 2.1.1 约束决策时段  
与标准 restless 马尔可夫赌博机相反，我们关注控制器仅能在由奖励流触发的*决策时段*切换臂的系统。具体来说，时段由系统奖励 (R(t))_{t≥1} 生成的过滤下的递增停时序列 (τ_i)_{i≥1} 构成。在两个决策时段之间，控制器不允许切换臂，即：∀ i, ∀ t ∈ {τ_i, ..., τ_{i+1}-1}, A(t)=A(τ_i)。 (1)  

在整个过程中，我们对决策时段的结构做出两个假设。在下述假设 3 中，H(t) = (S(1), A(1), R(2), S(2), A(2), R(3), ..., S(t)) 是*历史记录*，即直到时刻 t 的所有状态、所有已玩臂和所有已发出奖励的向量。  

###### 假设 2. 存在一个可测集 U_τ ⊆ [0,1] 使得 τ_{i+1} = inf{ t > τ_i : R(t) ∈ U_τ }。  
###### 假设 3. 存在 C_τ ∈ R_+ 使得对于所有 t ≥ 1，E[inf{τ_i - t : τ_i ≥ t} | H(t)] ≤ C_τ。  

假设 2 意味着当立即奖励落入特殊集合时发生决策时段。例如，若 U_τ = [0,1]，则决策时段是平凡的，即 τ_i = i 对一切 i ≥ 1，因此假设 2 特别涵盖了无决策时段约束的系统。假设 3 声称给定历史记录的条件下，下一个决策时段的期望时间一致有界。例如，若对于每个臂 a ∈ A，存在一个状态 s_a ∈ S_a 在 p_a^1 下是常返的，且 ν(s_a)(U_τ) > 0，则该假设成立。在此情形下，C_τ 通常可以用 p_a^1 的直径（在 p_a^1 下从一个状态转移到另一个状态的期望时间）和从有利状态发出正确奖励的概率 ν(s_a)(U_τ) 来界定。  

#### 2.1.2 全赌博机反馈：状态不可观测性  
虽然臂的数量对控制器已知，但控制器不知道臂的当前状态 S_a(t)，也不知道它们可能处于多少个状态 |S_a|。换句话说，状态是不可观测的。不可观测性意味着臂 A(t) 的选择仅依赖于过去的*观测历史* H_o(t) := (A(1), R(2), A(2), ..., R(t))。用正式术语来说，随机臂 A(τ_i) 是 σ(H_o(t))-可测的。注意，对于每个决策时段 τ_i，有 {τ_i ≤ t} ∈ σ(R(2), ..., R(t))。即，决策时段关于累积奖励向量可测。该假设对我们的工作绝对必要，否则控制器无法正确切换臂。  

### 2.2 少切换算法与伪遗憾  
本节我们定义少切换策略的概念，这在考虑相对于纯策略的遗憾时提供了一类自然的学习规则。确实，这样的学习器应能够通过为每个臂构造增益 g_a 的良好估计来识别最优臂。纯策略 π_a 的增益仅取决于在 π_a 下被无限多次访问的状态——即 π_a 的*常返状态*集。当拉动一个臂来估计 g_a 时，过程最初可能处于该集合之外，需要若干步才能达到它，从而才能开始估计 g_a。由于 |S_a|（臂 a 的状态数）未知，任务进一步复杂化。  

图 1：一个需要连续激活至少 n 次才能被正确估计的臂。所有转移都是确定性的，p_a^1 用黑色表示，p_a^0 用红色表示。  

图 1 提供了一个例子，其中状态 n 在 π_a 下是吸收态，臂的增益为 g_a = 2/3。只有当在学习过程中控制器无限频繁地连续激活该臂超过 n 次时，才能准确估计该增益。由于 n ≥ 1 通常可以任意大，这促使我们尽可能减少从一个臂切换到另一个臂的次数，并通过*计数*拉动次优臂的次数来度量遗憾。这引入了*伪遗憾*：  
PR(T) := ∑_{a∈A} (g_* - g_a) N_a(T)。 (2)  
其命名源于多臂赌博机中的同名版本（Lattimore and Szepesvári, 2020, §4.9）。伪遗憾将学习算法的性能度量为即时成本之和：臂 a 的个体成本由增益缺口 g_* - g_a（其增益与 g_* 的差距）给出，伪遗憾是随时间累积的增益缺口之和。伪遗憾比遗憾更容易分析，因为它直接表示为拉动次优臂的次数。如果伪遗憾很大，那么遗憾也很大。反之一般不一定成立。  

我们现在讨论一类学习算法，其遗憾仍可以用伪遗憾来上界：*少切换算法*。  

###### 定义 1（少切换算法）. 给定一个次线性光滑凹函数 ψ: R_+ → R_+，如果对于所有 M ∈ M，满足 ∀ a ∈ A, ∀ T ≥ 1, ∑_{t=1}^{T-1} 1(A(t)=a, A(t+1)≠a) ≤ ψ(N_a(T))，则称该算法是*ψ-少切换*的。  

换句话说，如果算法切换到臂 a 的次数相对于 N_a(t)（臂 a 的拉动次数）是次线性增长的，那么它就是*少切换*的。当算法是 ψ-少切换时，伪遗憾 (2) 成为遗憾的自然代理：如下命题 1 所述，如果算法很少切换臂，那么两者（在一阶意义上）近似相等。该结论鼓励我们完全专注于伪遗憾的研究。  

###### 命题 1（遗憾与伪遗憾）. 设 M ∈ M 是具有唯一最优臂的任意模型。设 Λ 是一个 ψ-少切换算法。则存在一个正的光滑凹函数 ψ_0 = O(ψ) 使得对于每个时域 T ≥ 1，有  
|Reg(T) - E[PR(T)]| ≤ ψ_0(E[PR(T)])。  

命题 1 的证明推迟到附录 LABEL:appendix_rarely_switching。由于 ψ_0 = O(ψ) 是次线性函数，命题 1 指出少切换算法的期望遗憾为 E[PR(T)] + o(E[PR(T)])。因此，这类算法的遗憾可以通过直接控制伪遗憾来分析，后者更易处理。  

## 3 一般遗憾界  
作为理论图景的初步勾勒，我们首先从*实例相关*的角度来研究问题。即，给定一个实例 M ∈ M 和一个学习算法 Λ，我们旨在尽可能精确地界定当 T → ∞ 时 Reg(T; M, Λ) 的界。这与*最坏情况*或*极小化极大*方法相反，后者需要界定 sup_{M∈M} Reg(T; M, Λ)。当 M 太大时，极小化极大方法被证明表现不佳，而非平凡的实例相关界总是可以获得的。  

从实例相关设定开始，我们在第 3.1 节中证明每个少切换算法的期望遗憾（公式 LABEL:equation_regret_definition）都超对数增长（定理 2）。我们进一步猜测，在自退化实例空间上甚至可以去掉少切换假设。这些下界为学习算法提供了基准。特别地，O(log T) 数量级的遗憾保证是不可达到的。在第 3.2 节中，我们提出了我们的算法 UCB-NOM，它是 UCB2（Auer, 2002）的一个变体，将发散的*跨度代理*函数 f 以及置信函数 δ: N → [0,1] 作为输入。在第 3.3 节中，我们证明 UCB-NOM 的实例相关遗憾为 O(f(T)^2 log T)，这意味着它可以任意逼近理想的对数遗憾区间。我们在第 3.4 节中通过展示极小化极大遗憾界来结束。