Statistical complexity and optimal algorithms for nonlinear ridge bandits¶

作者: Nived Rajaraman, Yanjun Han, Jiantao Jiao, Kannan Ramchandran
来源: Annals of Statistics
主题: 其他
相关性: 5/10
机构绿灯: New York University（US News 前 50，免分进入精读）
链接: https://doi.org/10.1214/24-aos2395

一、领域脉络与小综述¶

这个方向是什么¶

本方向研究的是非线性多臂老虎机问题 (nonlinear bandits) 中的统计高效学习边界。与经典的线性 bandit 不同（其中平均回报是动作向量的线性函数），非线性 bandit 的回报函数未知且非线性，这使得问题出现了两个独特的现象：(1) 一个由非线性函数复杂度决定的固定成本的“燃烧期” (burn-in period)，在燃烧期内学习几乎停滞；(2) 达到最优燃烧成本需要全新的探索算法。当前主流方法 (如 UCB 和基于回归 oracle 的算法) 在这种设定下是次优的。本文聚焦一类特殊的非线性函数——ridge 函数 (ridge functions)，即 $f(x) = g(\theta^\top x)$，其中 $g$ 是未知的单变量函数，$\theta$ 是未知的方向向量。

发展脉络 (history)¶

奠基工作——线性 bandit (Auer 2002, Dani 2008)：线性 bandit 理论奠定了多臂老虎机中序贯决策的框架，核心是探索-利用平衡，最优遗憾为 $\tilde{O}(d\sqrt{T})$。
迈向非线性的第一步——广义线性模型 (GLM) bandit (Filippi 2010, Li 2017)：将回报函数扩展为已知链接函数下的广义线性模型。这些工作的共同点是假设函数的形状 (链接函数) 是已知的，从而将非线性限制在已知的参数化结构内，因此避免了本文所称的“燃烧期”。
真正非线性的探索——非参数 / 核方法 bandit (Srinivas 2012, Valko 2013, Chowdhury & Gopalan 2017)：使用诸如高斯过程的核方法来处理完全未知的非线性函数。这类方法可以逼近任意函数，但其代价是依赖于函数空间复杂度 (如 RKHS 范数) 来保证遗憾界，且往往需要大 T 才能使遗憾率达到 (近乎) 参数速率。这一支线的工作是本文的直接上下文。
本文的位置——ridge 函数作为介于线性与完全非参数之间的桥梁 (Rajaraman 2024)：本文是第一篇显式刻画了“固定燃烧成本” 并证明其最优性的论文。其关键洞见在于：即使对于 $\theta$ 未知但 $g$ 完全未知的 ridge 函数，只要 $g$ 的变化足够丰富 (例如在支撑集上变化幅度有限)，算法就必须付出一个与 $d$ 无关的固定成本来“找准”好方向 (甚至仅是好动作的局部邻域)。本文的燃烧成本概念将非线性 bandit 的根本困难从“无法以参数速率学习”的悲观结论 (如非参数 bandit) 转向“存在一个明确可量化的、可被最优算法克服的最优固定成本”。

子线索聚类¶

被引文献大致落在以下两条子线索上：

线索 A：线性 / 参数化 bandit。 目标是通过假设回报函数为线性或已知链接函数的广义线性模型来简化问题。代表作：Auer (2002), Agrawal and Goyal (2013), Daniet al. (2008), Filippi et al. (2010)。核心弱点是：当模型误设时，这些算法可能完全失效。
线索 B：非参数 / 核方法 bandit。 放弃参数化假设，使用核方法 (如 GP-UCB) 来建模未知非线性函数。代表作：Srinivas et al. (2012), Valko et al. (2013), Chowdhury & Gopalan (2017)。核心弱点是：虽然可以逼近任意函数，但遗憾界通常依赖于函数在核空间中的范数，且对大 T 的渐近率往往远慢于参数速率，存在“便宜但永不精确”的风险。
线索 C：特殊结构非线性函数。 这是本文开创的新子线索——专门研究 ridge 函数。bridge 函数结构类似于单层神经网络的一个神经元 ($ abla f(x) = g'(\theta^\top x) \theta$)，其梯度方向完全由 $\theta$ 决定，但 $g$ 完全未知。这允许将问题拆分为“先快速定位好方向 / 好动作” (燃烧期) 和“在好方向周围进行局部线性学习” (学习期)。

核心问题与现有瓶颈¶

这个方向在追问的核心问题是：对于一个完全未知的非线性回报函数，是否存在一种最优的序贯决策算法，使得累积遗憾的上界形式可分解为一个由函数复杂度决定的常数成本和一个标准参数率的学习成本？
现有瓶颈是： - 经典 UCB 型算法在非线性情形下往往产生 $\Omega(T^{2/3})$ 量级的遗憾。 - 基于回归 oracle 的算法 (例如使用 online least squares) 在非线性下表现更差，可能产生线性遗憾。 - 对于一般的非参数函数，燃烧成本可能随着维度 $d$ 指数增长 (维数诅咒)，使其不具备实用性。

⚠️ 作者的 framing (必须明确标注成"这是作者的说法")¶

作者将 gap 框架化为：“线性 bandit 理论的成功误导了社区”（作者在引言原文中写道："Compared with the linear model, two curious phenomena arise in non-linear models..."——这是作者的说法，实际上是他们在重新定义问题）： - 作者声称：是线性假设掩盖了燃烧期的存在。而将模型推广到“简单的非线性” (ridge 函数) 就足以暴露这一成本。 - 作者淡化 / 回避的竞争路线：他们承认核方法 bandit (如 GP-UCB) 能处理非线性，但声称它们的遗憾界依赖于函数范数和核性质，无法分离出“燃烧期”的概念（因此他们认为自己的框架更具解释力——这是作者的说法）。 - 什么明显该被引 / 该存在、却没出现在 intro 里？ 连接 bias-variance tradeoff 的经典工作 (如 minimum-norm interpolation, benign overfitting) 未被引用。这些工作中也有“先大偏差探索后小方差估计”的类似现象。此外，关于分布鲁棒优化中 fixed cost 概念的工作也未出现。这些都是值得研究者去查的潜在 gap。

张力¶

未见明显的对立引用。但存在一条隐形的张力：在“低维参数结构” (如线性) 与“完全非参数” (如 GP-UCB) 之间，什么才是函数复杂度的正确度量？ ridge 函数是一类“低维结构”，所以其优点与结论是否仅对这类特定结构成立，无法推广到一般非线性？作者在 future work 中也有提及：“extending the current results beyond ridge functions…”。这暗示作者自认当前结果局限于 ridge 函数类，尚不清楚能否推广到更一般的函数空间。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号： - $d$：动作 (action) 的维度。 - $T$：总轮数 (horizon)。 - $f: \mathbb{R}^d \to \mathbb{R}$：未知的平均回报函数。 - $X_t \in \mathcal{X} \subseteq \mathbb{R}^d$：第 $t$ 轮选择的动作 (行动变量)。 - $Y_t = f(X_t) + \eta_t$：第 $t$ 轮观测到的回报，$\eta_t$ 是 $\sigma^2$-次高斯的噪声。 - $\pi$：一个策略 (policy)，定义了如何在每一轮选择 $X_t$。 - $\text{Regret}(T)$：累积遗憾 (cumulative regret)，定义为 $\sum_{t=1}^T [f(x^*) - f(X_t)]$，其中 $x^*$ 是 $\mathcal{X}$ 上 $f$ 的最大值点。 - $g: \mathbb{R} \to \mathbb{R}$：未知的单变量函数，是 ridge 函数 $f(x) = g(\theta^\top x)$ 中构成非线性部分。 - $\theta \in \mathbb{S}^{d-1}$：未知的方向向量 (单位球上)。

模型： - 数据生成机制：每个时刻 $t$，算法选择一个动作 $X_t$，环境生成一个回报 $Y_t = f(X_t) + \eta_t$。$f$ 是未知的，但属于一类非线性 ridge 函数：

\[f(x) = g(\theta^\top x),\]

其中 $\theta$ 是未知的单位向量，$g$ 是未知且非线性的函数。 - 已知信息：动作空间 $\mathcal{X}$ 已知（如 $[-a, a]^d$ 或单位球），噪声分布是次高斯的，h 的某些正则性成立 (如 Lipschitz 连续)。 - 待估计对象：$\theta$ 和 $g$ 都是待估的，但最终目标是最小化遗憾，而不是精确估计 $f$。 - 假设 (作者做的)：$g$ 在支撑集上的变化幅度 (variation) 是有界的，即 $g$ 在某个区间 $[m, M]$ 上的总变差 (TV) 或至少其最大值与最小值之差不超过常数 $C$。这个假设是燃烧期成本的核心：只要 $g$ 不是常数，其非平庸变化就会带来一个固定的探索成本。

可观测数据：
研究者实际能观测到的是动作-回报对的序列 $\{ (X_t, Y_t) \}_{t=1}^T$。
研究者想要但观测不到的是：$\theta$ 和 $g$。$g$ 本身只能通过沿不同方向 $\theta$ 的观测片段间接推断。这个区分很关键：因为 $\theta$ 未知，沿不同方向的观测不共享函数结构——沿着 $\theta_1$ 观测到的回报 $g(\theta^\top \cdot)$ 无法直接推断沿 $\theta_2$ 的回报，除非 $\theta_1$ 与 $\theta_2$ 足够接近 (梯度信息共享)。

第二步：讲最小内核¶

本文的最小内核是当动作空间是一维的 ($d=1$)，且 $g$ 是定义在区间 $[-1, 1]$ 上的有界非线性函数。虽然在 $d=1$ 时 $\theta$ 变成符号 ($\pm 1$)，但燃烧期问题的本质不依赖于方向未知，而在于 $g$ 的未知性。

最简特例： - 设定：$d=1$, $f(x) = g(x)$，其中 $g$ 是定义在 $[-1, 1]$ 上的 Lipschitz 连续函数，且总变差 $TV(g) \leq V < \infty$ (变化有界)。$x^*$ 为 $g$ 的全局最大值点，假设在区间内部 (例如 0.5)。 - 可观测数据：$\{ (X_t, Y_t) \}$，其中 $X_t \in [-1, 1]$, $Y_t = g(X_t) + \eta_t$。 - 核心问题：需要多少观测 (步数) 才能确定 $x^*$ 的近似位置？

为什么这个特例抓住了本质： 线性函数 $g(x)=ax$ 的情况下，两点的观测即可外推任意位置的回报。但对于非线性 $g$，无法用远距离观测来推断 $x^*$ 的值。例如，在 $x=-1$ 处观测到低回报，不能排除 $x=1$ 处更高的回报，因为 $g$ 可能在区间另一边骤升。因此，在 $g$ 未知且变化有界的条件下，必须对 $g$ 的整个定义域进行某种“全局采样”，以排除某些区域存在更高回报的可能性。这个“全局采样”所需的步数就是燃烧期成本。

数学退化： 在 $d=1$ 且 $g$ 已知 $L$-Lipschitz 时，经典的 Lipschitz bandit 算法 (如 UniformGrid) 需要 $\Omega(1/\epsilon)$ 步才能保证找到 $\epsilon$-最优动作，此时 Burn-in cost = $\tilde{O}( \sqrt{T} )$? (非参数率)。但本文中，他们通过对其施加更强的“变化幅度”条件 (并不是无穷多样性)，证明了只需常数步 (但不可忽略，如 $\Theta(\sqrt{d})$ 或 $\Theta(L)$ 相关的固定成本) 来定位一个“足够好的初始动作”。

更具体的“内核”问题 (当 $d>1$ 且 $\theta$ 未知)： 假设 $\theta$ 是未知的单位向量。挑战在于：沿任意方向 $x$ 的观测并不能告诉你沿另一个方向 $x'$ 的回报。为了学习方向 $\theta$，算法需要比较不同动作的回报。但是，由于回报函数是 $g(\theta^\top x)$，即使我们遍历整个 $x$ 空间，我们看到的仍然是同一个单变量函数 $g$ 在不同“有效投影” $\theta^\top x$ 上的值。因此，$g$ 的非参数部分并没有随着 $d$ 的增加而变得更复杂。然而 $\theta$ 的未知性使得探索成本与控制相联系。

核心命题 (对于 d>1 的 ridge 函数)： 存在一个固定常数成本 $C(g, \mathcal{X})$ (例如：$C = \Theta( \|g\|_\infty \cdot \text{diam}(\mathcal{X}) )$)，使得任何算法都必须付出至少 $C$ 的遗憾才能将搜索聚焦到最优动作的局部邻域。这个成本不随着 $T$ 增大而消失，是一个固定“入门费”。
证明的核心想法： 在最坏情形构造 $g_1, g_2$ 在大部分区域相等，但在好区域 (最优动作附近) 明显不同。算法只有获得足够的观测后才能区分这两种情形，而这需要先在好区域之外付出一定的探索成本。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：研究了平均回报为非线性 ridge 函数 $f(x) = g(\theta^\top x)$ 的多臂老虎机问题的最优累积遗憾形式，关注其中的“燃烧期”成本。
核心工具 / 方法：通过微分方程分析精确刻画了燃烧期内遗憾的增长轨迹，并提出一种两阶段探索算法：第一阶段利用“无偏探索” (unbiased exploration，如随机采样) 进行全局粗糙搜索，找到足够好的初始动作；第二阶段将问题视为局部线性 (局部 $g$ 近似线性) 进行利用性学习。
主要结论：证明了最优遗憾的上界可以是 $R(T) = \mathcal{O}( \text{Burn-in cost} + d \sqrt{T} )$，其中 Burn-in cost 由函数 $g$ 的复杂度 (如总变差) 决定，对 Ridge 函数是最优的。相反，经典 UCB 算法和基于回归 oracle 的算法会产生 $\Omega(T^{2/3})$ 甚至 $\Omega(T)$ 的次优遗憾。

关键设定与假设¶

动作空间：$\mathcal{X} \subseteq \mathbb{R}^d$ 是一个紧凸集 (如 $L_\infty$ 球 $[-1,1]^d$ 或单位 $L_2$ 球)。复杂度由半径 $R$ (diameter) 刻画。
回报函数：$f(x) = g(\theta^\top x)$，其中 $\theta \in \mathbb{R}^d$ 是未知单位方向向量，$g$ 是定义在某个区间 $I \subseteq \mathbb{R}$ 上的单变量函数。
关键假设 (对 $g$ 的复杂度定义)：$g$ 是有界变化 (bounded variation) 的，或者更具体地，存在一个已知常数 $V$ 使得 $\text{TV}(g) \le V$ (总变差界)。这比完全非参数的设定要弱 (总变差只控制了函数的波动总量，而不是函数本身的范数)，从而保证了全局搜索的成本是有界的。相比线性情形的“无成本”，这是一个核心加强。
对 $\theta$ 的处理：$\theta$ 是未知且任意的。算法不需要显式估计 $\theta$；只要它能够在“好动作”的邻域内收集足够多信息，局部线性近似 ($g \approx $ 线性函数) 就成立。
噪声：$\eta_t$ 是 $\sigma^2$-次高斯的，均值为零。
Smoothing assumption (对 $g$ 的光滑性)：在保证局部线性阶段有效时，需要 $g$ 在最优解附近是 Lipschitz 且二阶可微的。这与第一阶段的 TV-bounded 假设不同——说明在无偏探索阶段，连光滑性都不需要，只需要知道它的变化幅度有限。这是一个重要的假设对比：在局部阶段利用了二次型展开 ($g(\theta^\top x) \approx g(\theta^\top x^*) + \gamma \cdot (\theta^\top (x - x^*))$)。

主要结果¶

定理 3 (Burn-in cost 的上下界)：
- 上界：存在一个算法，其遗憾可被分解为 $\text{Regret}(T) \le C_{\text{in}}(\mathcal{X}, g) + \tilde{O}(d \sqrt{T})$，其中 $C_{\text{in}}(\mathcal{X}, g) = \Theta( R \cdot \text{TV}(g) \cdot \sqrt{d} )$ (以动作空间半径, 函数变化, 维度)。这意味着第一阶段付出 $C_{\text{in}}$ 的成本后，剩余遗憾以参数率 $O(\sqrt{T})$ 增长。
- 下界：对于算法类，任何算法的遗憾都不可能低于 $\Omega( R \cdot \text{TV}(g) \cdot \sqrt{d})$ (即燃烧成本部分)，只要 $T$ 不太大于某个准则。这证明了 $C_{\text{in}}$ 是最优的。
- 技术难点：需要证明“任何算法在学习期之前都必须付出这笔固定成本”，这需要用到多点对抗构造和信息论下界 (如 Fan 引理 / Fano 方差界)。作者指出，在经典线性 bandit 下界构造中，只需要构造两个相近的问题 (近参数) 就够；但这里需要构造多个非线性函数，且通过信息论来证明它们强不可区分甚至互斥，直到某些全局探索发生。
定理 5 (最优性分析——UCB 是次优的)：对于同一类问题，用 UCB 策略实现的遗憾至少为 $\Omega(T^{2/3})$。类似的，使用回归 oracle 作为子程序的算法 (如在线最小二乘法实现置信区间) 在最坏情形下产生 $\Omega(T)$ 的线性遗憾。
- 证明想法：UCB 的置信区间假设函数是“几乎线性”的，而回归 oracle 基于线性假设设计。在 Ridge 函数的结构下，这两者都无法正确处理“好动作”在远处与近处时函数值的剧烈变化，导致盲目乐观。
定理 6 (精确轨迹)：在特定的重要参数化下 (如 $g$ 为某个已知形如 $s \cdot \text{tanh}$ 或简单的分段线性函数)，通过求解一个微分方程，论文可以精确给出燃烧期的遗憾增长曲线，而不仅仅是渐进阶。

证明路线与技术技巧 (理论型)¶

整体路线：

下界构造 (Lower bound for Burn-in cost)：
- 构造两个或多个 Ridge 函数 $g_1, g_2$，它们在大部分区域相同 (即 $g_1(z) = g_2(z)$ 对于 $z \not\approx \theta^\top x^*$)，但在最优动作附近 (即 $z \approx \theta^\top x^*$) 有巨大差异 (如 $g_1$ 的局部最大值远高于 $g_2$)。
- 证明：如果一个算法试图最小化遗憾 (即选择高回报的动作)，它必须投入足够的采样来区分 $g_1$ 和 $g_2$。这个“区分成本”与 $g$ 的总变差相关 (因为为了改变 $g$ 在最优处的值，其总变差必须增加一个相同的量)。
- 应用经典的信息论下界技巧 (如 Fano 不等式 / Le Cam 方法)，证明需要 $\Omega( \frac{R^2 \cdot \text{TV}(g)^2 \cdot d}{\sigma^2})$ 级别的样本才能区分。因此，至少 $\text{Regret} \ge C_0(T)$，且由于 $T$ 很大，这部分成本无法通过后续学习摊销为零。
上界 (Upper bound) 算法设计——两阶段算法 (Two-stage algorithm)：
- 第一阶段：无偏探索 (Unbiased Exploration)。随机均匀采样动作空间 $\mathcal{X}$ 若干次 (大约 $\mathcal{O}(d \cdot \text{TV}(g)^2)$ )。对于 $\mathcal{X}$ 的每个坐标轴方向上的极端值点也进行确定性探索。这阶段不依赖于任何模型，只是收集足够多的信息来对 $g$ 的整体行为做个粗略估计。核心引理：经过足够多的无偏采样，以高概率可以找到一个“好动作” $x_0$，使得 $f(x_0) \ge f(x^*)- \epsilon$，其中 $\epsilon = O(1/\sqrt{T})$。直觉：TV-bounded 的函数可以被看做在有限个“平坦区”之间跳跃。采用无偏采样基本等同于对这些平坦区进行均匀覆盖，能以误差反比于样本量的速度找到最高山谷。
- 第二阶段：局部线性近似 (Locally linear approximation)。一旦找到 $x_0$ (与最优 $x^*$ 足够接近)，算法假设$f(\cdot)$ 在 $x_0$ 附近是近似线性的：$f(x) \approx f(x_0) + abla f(x_0)^\top (x - x_0)$。然后，使用一个线性 bandit 算法 (如 OFUL / 线性 UCB) 在这个邻域内进行精细搜索。这个过程的遗憾是 $\tilde{O}(d \sqrt{T})$。
证明 UCB 和回归 oracle 的次优性：通过构造一个特定问题实例，证明了 UCB 和回归 oracle 在面对 TV-bounded function 时的悲观性，并证明了它们的遗憾较低界。

关键跳跃点： - 最大的跳跃是从“无偏探索”找到一个好动作 $x_0$ 到“局部线性”后，如何保证两者的衔接是平滑的。即：为什么通过无偏探索找到一个动作后，$f$ 在该点附近一定是近似线性的？ 答案：不是所有的 $g$ 都保证这点。这是依赖于对区间 $I$ 上 TV-bounded 函数的光滑化近似：利用卷积核，任何 TV-bounded 函数都可以被光滑函数逼近到 TV-error ($L_1$ 意义上的速度) 与带宽相关的阶。如果通过第一阶段把最优解的邻域缩小到带宽以下，则在该邻域内函数近似线性。这使第二阶段能够有效地进行。

技术技巧点名： - 最坏情形构造 (worst-case construction)：证明下界时，构建了两个满足假设的 $g_1, g_2$，它们唯一不同是：在最优解附近，函数值大幅跳变。这迫使算法必须“花功夫”区分它们。 - 贝叶斯观点 (Bayesian approach)：在分析算法性能时，将 $g$ 的先验视为服从某种 TV-bounded 的先验分布。 - 微分方程刻画 (Differential equation analysis)：将燃烧期的遗憾轨迹视为一个确定性的动力系统，通过 ODE 进行精确求解。这依赖于问题中 $g$ 和 $\mathcal{X}$ 的结构 (例如无限多的动作，连续性)。这是一种罕见但极有力的分析工具。 - 引理 2 (Unreliability / 不可靠性 Lemma)：证明 UCB 在非线性下有高概率导致“未加克制乐观”的引理。这依赖于精心构造的函数 $g$，在某个采样点附近 $g$ 的局部线性近似 (UCB 所依赖的) 与真实函数值截然不同，从而诱使算法选择坏动作。

真实例子与应用¶

本文没有真实数据例子。这是纯理论论文，所有例子都是模拟实验 (numerical simulations) 或理论构造。在论文的 simulation 节 (文章末尾) 中，作者模拟了不同算法在一个人造 Ridge 函数 $f(x) = \sin(20\pi \theta^\top x)$ 上的表现 (动作空间是 $[-1,1]^d$)。实验验证了理论预测： 1. 对于两阶段算法：“固定的平坦段之后以参数率 $t^{1/2}$ 增长”。 2. UCB 显著落后于两阶段算法。 3. 给定稍大的方差，回归 oracle 方法的遗憾在初始时迅速爆炸 (线性遗憾)，验证了其不稳定性。
用法目的：只是展示“本文的理论界 (阶) - 实验结果匹配，而其他经典算法不行”，从而直观地证实燃烧期和参数学习期的存在以及算法的优越性。

🔎 结论是否比证明窄¶

潜在的一个“宽松结论”：作者证明了对 TV-bounded 的 $g$ 的最优燃烧成本，但可能在对 $g$ 的其他度量 (如 Hölder 光滑性) 下，燃烧成本可能完全不同或不存在 (如果 $g$ 解析则可能只需要对数级别的探测)。论文的结论显然无法逃避“对函数结构的依赖”。
另一个结论比证明宽的地方是：未来工作提到 "extending to multi-layer neural networks" 可能会有全新难题，但论文目前只处理 单结点 (ridge 函数)。因此论文充其量是证明了一个特殊情况具有这个结构，但论文题目可能会让人误以为 "complexity of nonlinear ridge bandits" 包含更广的神经网络复杂性。作者在 intro 末尾有明确表述：“We focus on the ridge function class…”，说明作者自己的范围界定是正确的，但读者可能会错误地泛化。

四、开放问题¶

非参数率和胆怯探索：本文处理的是 TV-bounded 的 ridge 函数，并发现了“固定成本 + 参数学习率”结构。对于更一般的函数类 (如 RKHS 空间下的非线性带 Gaussian 过程)，是否也存在类似的“固定成本”，而不是通常的 $\Omega(T^{2/3})$？还是说只有 ridge 函数才因为它的低维结构 (有效参数维数为 1) 才有此优势？【可扎根于 intro 中关于 GP-UCB 的结果部分，以及 conclusion 中的 “future work: beyond ridge functions…”】
高维方向已知时的统计-计算权衡：如果假设 $\theta$ 是稀疏的 (只有 $s << d$ 个非零坐标)，本文的结果如何变化？在稀疏设定下，无偏探索阶段的成本是否从 $O(d \cdot \text{TV}(g))$ 降解为 $O(s \cdot \text{TV}(g))$？此时是否存在计算-统计权衡：即算法如果能在多项式时间内近似估计出 $\theta$ 的支撑集？或者这是否触及低次多项式 (low-degree) 下界，意味着即使稀疏探索也会受到某些计算上的障碍？这直接连接研究者的 stat-comptradeoff 兴趣。【可扎根于本文没有提到稀疏性假设、以及关于算法对 $\theta$ 处理的低维假设“$d$ 就是标题的维度”】
多步动作和燃烧期的精确刻画：本文的微分方程分析可以看作把燃烧期看作一门关于探索节奏的科学：如果先探索太慢 (后验不确定)，达不到；如果先用满探索，却浪费了后期收益。当下他们得到的是完整轨迹。对于更一般的多步决策问题 (如多臂老虎机、MDP)，能否也为探索期设计一个 (非线性) 微分方程，刻画其最优轨迹，从而使我们的“在线探索”变成一种解析可解的过程？这是对“微分方程刻画”方法的推广，是受本文启发的经典问题。【扎根于本文的定理 6 (精确轨迹) 及其对应自然推广】

Maintained by 陈星宇 · Homepage · Source on GitHub