提出新线性强化学习算法，可精确计算选臂概率，适合离线评估。
Minimum Empirical Divergence for Sub-Gaussian Linear Bandits
- 基于最小经验散度设计随机选臂策略，可闭式求解概率。
- 理论证明近似最优的 $d\sqrt{n}$ 与 $\frac{d^2}{Δ}\log^2(n)\log\log(n)$ 依赖问题的后悔界。
- 适用于需要精确采样概率的离线策略评估场景。
我们提出一种新型线性强化学习算法 LinMED（线性最小经验散度），是原始用于多臂赌博机的 MED 算法的线性扩展。该算法为随机型，可闭式计算各动作的采样概率，不同于常见的线性汤普森采样。这一特性在离线策略评估中极具价值，因无偏评估要求准确计算采样概率。理论分析表明，LinMED 在时间步数 $n$ 与维度 $d$ 条件下，具有近似最优的 $d\sqrt{n}$ 阶后悔上界（含对数因子）；进一步证明其问题依赖性后悔界为 $\frac{d^2}{Δ} \log^2(n) \log\log(n)$，其中 $Δ$ 为最小次优间隙。实验表明，其性能与当前最优算法相当。
原文摘要 · Abstract (English)
We propose a novel linear bandit algorithm called LinMED (Linear Minimum Empirical Divergence), which is a linear extension of the MED algorithm that was originally designed for multi-armed bandits. LinMED is a randomized algorithm that admits a closed-form computation of the arm sampling probabilities, unlike the popular randomized algorithm called linear Thompson sampling. Such a feature proves useful for off-policy evaluation where the unbiased evaluation requires accurately computing the sampling probability. We prove that LinMED enjoys a near-optimal regret bound of $d\sqrt{n}$ up to logarithmic factors where $d$ is the dimension and $n$ is the time horizon. We further show that LinMED enjoys a $\frac{d^2}Δ\left(\log^2(n)\right)\log\left(\log(n)\right)$ problem-dependent regret where $Δ$ is the smallest sub-optimality gap. Our empirical study shows that LinMED has a competitive performance with the state-of-the-art algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。