用抽象层次加速复杂决策，减少错误选择的累积损失
Using causal abstractions to accelerate decision-making in complex bandit problems
- 通过因果抽象在不同层级间共享信息，先粗略探索再精细优化
- 相比经典UCB算法，累积后悔值显著降低，理论与实证均验证
- 适合高复杂度、多层级抽象的现实决策问题，如流行病模拟
尽管现实中的决策问题常可建模为不同抽象层级的因果多臂老虎机（CMAB），但缺乏通用方法来利用各层级的信息与计算优势。本文提出AT-UCB算法，高效利用在不同抽象层级定义的CMAB实例之间的共享信息。具体而言，AT-UCB基于因果抽象（CA）理论，在低成本、粗粒度的CMAB实例中进行探索，随后在目标CMAB的潜在最优动作子集中应用经典的上置信界（UCB）算法，从而显著降低累积后悔。我们通过新的累积后悔上界进行了理论分析，并在具有不同分辨率和计算成本的流行病学模拟器上进行实验，验证了该方法的有效性。
原文摘要 · Abstract (English)
Although real-world decision-making problems can often be encoded as causal multi-armed bandits (CMABs) at different levels of abstraction, a general methodology exploiting the information and computational advantages of each abstraction level is missing. In this paper, we propose AT-UCB, an algorithm which efficiently exploits shared information between CMAB problem instances defined at different levels of abstraction. More specifically, AT-UCB leverages causal abstraction (CA) theory to explore within a cheap-to-simulate and coarse-grained CMAB instance, before employing the traditional upper confidence bound (UCB) algorithm on a restricted set of potentially optimal actions in the CMAB of interest, leading to significant reductions in cumulative regret when compared to the classical UCB algorithm. We illustrate the advantages of AT-UCB theoretically, through a novel upper bound on the cumulative regret, and empirically, by applying AT-UCB to epidemiological simulators with varying resolution and computational cost.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。