arXiv:2410.05117cs.LGcs.IT2024-10NeurIPS被引 14

提出统一框架,解决交互式决策学习的理论下界难题。

Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability

  • 引入交互Fano方法,融合经典下界与交互学习特性
  • 提出分数覆盖数新度量,实现任意随机博弈问题的可学习性刻画
  • 填补交互学习下界与上界差距,适用于凸模型类问题

我们构建了一个信息论下界的统一框架,用于统计估计和交互式决策。经典方法如Fano、Le Cam和Assouad引理在被动估计中至关重要,但无法给出交互式算法(如强化学习、多臂赌博机)的紧致下界。近期工作使用决策-估计系数(DEC)得到交互学习的下界,但未能恢复被动估计的最优结果。本文提出交互Fano方法,统一不同分析路径。进一步引入分数覆盖数这一新复杂度度量,拓展了DEC方法对估计复杂性的建模能力。利用该度量,(i) 给出任意随机赌博机问题的可学习性统一刻画;(ii) 在凸模型类下,将Foster等(2021, 2023)的上下界差距缩小至多项式因子内。

原文摘要 · Abstract (English)

We develop a unifying framework for information-theoretic lower bound in statistical estimation and interactive decision making. Classical lower bound techniques -- such as Fano's method, Le Cam's method, and Assouad's lemma -- are central to the study of minimax risk in statistical estimation, yet are insufficient to provide tight lower bounds for \emph{interactive decision making} algorithms that collect data interactively (e.g., algorithms for bandits and reinforcement learning). Recent work of Foster et al. (2021, 2023) provides minimax lower bounds for interactive decision making using seemingly different analysis techniques from the classical methods. These results -- which are proven using a complexity measure known as the \emph{Decision-Estimation Coefficient} (DEC) -- capture difficulties unique to interactive learning, yet do not recover the tightest known lower bounds for passive estimation. We propose a unified view of these distinct methodologies through a new lower bound approach called \emph{interactive Fano method}. As an application, we introduce a novel complexity measure, the \emph{Fractional Covering Number}, which facilitates the new lower bounds for interactive decision making that extend the DEC methodology by incorporating the complexity of estimation. Using the fractional covering number, we (i) provide a unified characterization of learnability for \emph{any} stochastic bandit problem, (ii) close the remaining gap between the upper and lower bounds in Foster et al. (2021, 2023) (up to polynomial factors) for any interactive decision making problem in which the underlying model class is convex.

下界分析博弈学习理论框架

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。