提出高效算法解决高维线性强化学习中的椭球约束优化问题。
Tractable Instances of Bilinear Maximization: Implementing LinUCB on Ellipsoids
- 针对椭球约束下的双线性最大化问题设计新算法
- 在高维场景下实现线性带宽算法的快速求解
- 适用于需要快速探索的高维强化学习任务
我们研究在 $x^ op θ$ 上关于 $(x,θ) \ ext{in} \mathcal{X} \times Θ$ 的最大化问题，其中 $\mathcal{X} \subset \mathbb{R}^d$ 为凸集，$Θ\subset \mathbb{R}^d$ 为椭球。该问题在线性带宽中至关重要，因学习者需每步求解以使用乐观算法。我们首先证明：当 $\mathcal{X}$ 为 $\ell_p$ 球且 $p>2$ 时，除非 $\mathcal{P} = \mathcal{NP}$，否则不存在有效算法。随后，我们提出两种新算法，在 $\mathcal{X}$ 为中心椭球时可高效求解。本工作首次提供了在高维情形下实现线性带宽乐观算法的方法。
原文摘要 · Abstract (English)
We consider the maximization of $x^\top θ$ over $(x,θ) \in \mathcal{X} \times Θ$, with $\mathcal{X} \subset \mathbb{R}^d$ convex and $Θ\subset \mathbb{R}^d$ an ellipsoid. This problem is fundamental in linear bandits, as the learner must solve it at every time step using optimistic algorithms. We first show that for some sets $\mathcal{X}$ e.g. $\ell_p$ balls with $p>2$, no efficient algorithms exist unless $\mathcal{P} = \mathcal{NP}$. We then provide two novel algorithms solving this problem efficiently when $\mathcal{X}$ is a centered ellipsoid. Our findings provide the first known method to implement optimistic algorithms for linear bandits in high dimensions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。