Feb, 2012

在线线性优化带赌博式反馈的极小极大政策

PDF
TL;DR该研究提出了在线线性优化问题的带有 bandit 反馈的算法，并使用 Mirror Descent 算法在特定案例中获得具有最小二乘优化后退限制的计算高效性的策略，证明了计算上以及最小二乘上的结果优化，为输出结果减少了冗余的符号。
linear optimizationbandit feedbackregret boundsmirror descent algorithmeuclidean ball
发现论文，激发创造
  • 线性参数赌博机的近似极小极大后悔

    研究了有限动作集的线性上下文强化学习问题，介绍了一种名为 VCL SupLinUCB 的算法，并表明其与最佳下界相匹配，相较于之前的算法分析，节省了两个对数因子。

    Mar, 2019

  • 组合式预测游戏的极小化策略

    我们研究了在线线性优化问题，探讨了半强盗、强盗和完全反馈三种情况下的极小后悔量，并提出了使用 Bregman 投影技术的梯度下降通用策略以及上下界解决方案，并在最后指出了指数加权平均预测者对于 L∞对手是次优解的问题。

    May, 2011

  • 多对数级别的极小极大遗憾的线性赌博机

    研究线性随机赌博机的噪声模型，介绍一种基于加权最小二乘估计的算法，能够最小化后悔度，通过几何论证独立于噪声模型，能够紧密控制每个时间步骤的期望后悔度为 O (1/t)，从而导致了累积后悔度的对数缩放。

    Feb, 2024

  • 面向具有悔恨的对抗性线性马尔可夫决策过程的最优化

    在线强化学习是研究的主题之一，尤其在线性 Markov 决策过程中使用了对抗性损失和强盗反馈，提出了两个算法以改善后悔性能。

    Oct, 2023

  • 针对零阶对抗性 Bandit 凸优化的改进遗憾

    以信息论为基础，改进探索性分布以在零阶对抗性 bandit 凸优化的 minimax regret 的信息理论上界上证明其为 O (d^{2.5} 根号 n 对数 (n))，并提高 Bubeck 等人 (2017) 的 O (d^{9.5} 根号 n 对数 (n)^{7.5} 上界。

    May, 2020

  • 在线组合优化中的遗憾

    本文研究使用二进制向量表示决策者可能的选择时的在线线性优化问题及其反悔，探讨了决策者在不同反馈条件下的最优反悔幅度，并提出了一种使用镜像下降算法和隐式归一化预测策略的解决方案，获得了半强盗情形的最优界限，同时也证明了在线组合优化基准算法的次优性。

    Apr, 2012

  • 关于具备反馈图的在线学习的最小化后悔算法

    本文针对具有强可观测无向反馈图的在线学习问题，在回报上下界方面进行了改进，并使用 FTRL 与 q-Tsallis 熵对结果进行了证明；同时扩展了该技术应用于时间变化图的情形，并提供了适用于所有 alpha>1 的改良下界。

    May, 2023

  • 组合半弦臂算法的一阶遗憾上界

    本文研究了在线组合优化问题中的半盲反馈，提出了一种优化算法来减少期望后悔。该算法以 L_T * 的平方根为增长率，在部分反馈方案中首次实现了此类保证，并在组合设置中首次实现了此类保证。

    Feb, 2015

  • 在线一位反馈随机线性优化

    本文研究在线随机线性优化的特殊赌徒环境，其中每轮只有一位信息被揭示给学习者。我们假定二元反馈是从对数模型产生的随机变量，并旨在最小化未知线性函数定义的遗憾。为了解决此挑战，我们通过利用观测模型的特定结构开发了一种高效的在线学习算法。

    Sep, 2015

  • 睡眠赌徒的近最佳每个动作的遗憾界

    我们使用广义版本的 EXP3、EXP3-IX 和 FTRL 与 Tsallis 熵直接最小化每次行动的遗憾，从而获得了接近最优的 $ O (√{TAln⁡K})$ 和 $ O (√{T√{AK}})$ 的界限，并将我们的结果推广到了从睡眠专家那里寻求建议的强盗情境，从而得到了一些现有自适应和跟踪遗憾上限的新证明，并通过推广我们的结果到专家报告信心的强盗版本，得到了主要依赖于专家信心之和的置信遗憾上限。

    Mar, 2024