Joint Online Learning and Decision-making via Dual Mirror Descent
Joint Online Learning and Decision-making via Dual Mirror Descent
复制标题
DOI：
--
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Alfonso Lobos;Paul Grigas;Zheng Wen
中科院分区：
文献类型：
--
作者：
Alfonso Lobos;Paul Grigas;Zheng Wen
我们考虑在有限时间范围内受成本下限和上限影响的在线收入最大化问题。在每个周期，代理都会收到一个独立同分布 (i.i.d) 采样的上下文向量。来自未知的分布，需要自适应地做出决策。收入和成本函数取决于上下文向量以及一些固定但可能未知的待学习参数向量。我们提出了一种新颖的离线基准和一种新算法，它将在线双镜像下降方案与通用参数学习过程相结合。当参数向量已知时，我们展示了 $O(\sqrt{T})$ 遗憾结果以及可能违反约束的 $O(\sqrt{T})$ 界限。当参数未知且必须学习时，我们证明遗憾和约束违规是先前 $O(\sqrt{T})$ 项加上直接取决于学习过程收敛的项的总和。
We consider an online revenue maximization problem over a finite time horizon subject to lower and upper bounds on cost. At each period, an agent receives a context vector sampled i.i.d. from an unknown distribution and needs to make a decision adaptively. The revenue and cost functions depend on the context vector as well as some fixed but possibly unknown parameter vector to be learned. We propose a novel offline benchmark and a new algorithm that mixes an online dual mirror descent scheme with a generic parameter learning process. When the parameter vector is known, we demonstrate an $O(\sqrt{T})$ regret result as well an $O(\sqrt{T})$ bound on the possible constraint violations. When the parameter is not known and must be learned, we demonstrate that the regret and constraint violations are the sums of the previous $O(\sqrt{T})$ terms plus terms that directly depend on the convergence of the learning process.