在参数噪声下，线性强化学习实现近最优后悔界，简单算法即可达成。
Stochastic Linear Bandits with Parameter Noise
- 引入参数噪声模型，将奖励建模为动作与随机参数的内积。
- 在任意动作集上达到约 $\widetilde{O}(\sqrt{dT \log(K/δ) σ^2_{\max}})$ 的后悔上界。
- 对 $\ell_p$ 球等特定动作集，简单探索-利用算法即可实现最优后悔率。
我们研究了参数噪声下的随机线性赌博机模型，其中动作 $a$ 的奖励为 $a^\top θ$，$θ$ 独立同分布采样。我们证明了在时长 $T$、动作集大小 $K$、维度 $d$ 的条件下，后悔上界为 $\widetilde{O} (\sqrt{d T \log (K/δ) σ^2_{\max})}$，其中 $σ^2_{\max}$ 是任一动作的最大奖励方差。进一步给出下界 $\widetildeΩ (d \sqrt{T σ^2_{\max}})$，当 $\log(K) \approx d$ 时达到紧致性。针对 $\ell_p$ 单位球（$p \leq 2$）及其对偶范数 $q$ 的具体动作集，最小最大后悔为 $\widetildeΘ (\sqrt{dT σ^2_q)}$，其中 $σ^2_q \leq 4$。这与经典加性噪声模型中 $d \sqrt{T}$ 的后悔率形成对比。令人惊讶的是，这一最优后悔界可通过极简的探索-利用算法实现。
原文摘要 · Abstract (English)
We study the stochastic linear bandits with parameter noise model, in which the reward of action $a$ is $a^\top θ$ where $θ$ is sampled i.i.d. We show a regret upper bound of $\widetilde{O} (\sqrt{d T \log (K/δ) σ^2_{\max})}$ for a horizon $T$, general action set of size $K$ of dimension $d$, and where $σ^2_{\max}$ is the maximal variance of the reward for any action. We further provide a lower bound of $\widetildeΩ (d \sqrt{T σ^2_{\max}})$ which is tight (up to logarithmic factors) whenever $\log (K) \approx d$. For more specific action sets, $\ell_p$ unit balls with $p \leq 2$ and dual norm $q$, we show that the minimax regret is $\widetildeΘ (\sqrt{dT σ^2_q)}$, where $σ^2_q$ is a variance-dependent quantity that is always at most $4$. This is in contrast to the minimax regret attainable for such sets in the classic additive noise model, where the regret is of order $d \sqrt{T}$. Surprisingly, we show that this optimal (up to logarithmic factors) regret bound is attainable using a very simple explore-exploit algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。