ICLRMay, 2022

方差感知稀疏线性赌博机

PDF
TL;DR本文发展了一种数据稀疏 (稀疏线性斯托剖斯) 的新型算法，该算法使较小的环境维度下研究致命后果的风险得以降低，实现了一种有区别的、具有人造和样本方差适应性的总体安全算法。同时，该研究还探讨了如何在一种 <黑盒> 化的方式下将任何方差算法转化为 sparce linear bandits 算法。
sparse linear banditsregret guaranteevariance-awareambient dimensiondivide-and-conquer
发现论文，激发创造
  • 高维稀疏线性赌博机

    研究高维稀疏特征的随机线性臂模型中，在数据匮乏的情况下，特征向量遵守固定的探测分布，通过探索然后提交算法，得到了 $Ω(n^{2/3})$ 的无维度极小遗憾下界和 $Θ(n^{2/3})$ 的上界。

    Nov, 2020

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

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

    Feb, 2024

  • 改进方差自适应线性赌博机和无时序线性混合马尔可夫决策过程的遗憾分析

    本篇论文研究在线学习中的方差自适应算法，提出了适用于线性赌臂机以及线性混合马尔可夫决策过程的遗憾界分析，该方法在未知方差的情况下，能够实现 Regret 的拟多项式算法复杂度降低。

    Nov, 2021

  • 多臂赌博机中的稀疏性、方差和曲率

    研究了在线学习理论，特别是有限反馈情况下的敌对多臂赌博和线性赌博设置，并解决了几个关于算法存在优势遗憾边界的开放性问题，得出某些情况下的优势遗憾边界。

    Nov, 2017

  • 基于方差的线性赌博机和线性混合 MDP 置信区间的改进

    本文提出了一种新的方差感知置信集，用于线性 bandits 和线性混合马尔可夫决策过程（MDPs）中，我们得到了与方差和维度相关，但不显式依赖于循环次数 k 的后悔上限，并获得了史上首个仅在强化学习中呈对数比例的后悔上限，这三种技术思想可能是独立感兴趣的应用。

    Jan, 2021

  • 低秩广义线性赌博机问题

    提出了一种基于在线到置信区间映射和基于低秩矩阵覆盖的指数加权平均预测器相结合的算法，解决了低秩线性赌博机问题，具体算法延伸自探索子空间再精炼算法，可以使得拥有低秩矩阵 Theta 的线性赌博机达到更好的期望累积损失表现并得到了实验的验证。

    Jun, 2020

  • 线性参数赌博机的近似极小极大后悔

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

    Mar, 2019

  • 阈值套索强化学习算法

    本文提出一种基于阈值套索算法的 regret minimization 解决方案，能够更好地应对稀疏随机上下文线性赌博机问题，且不需要对稀疏度等参数有先验知识，理论上的性能约束也有所提高。

    Oct, 2020

  • 具有自适应对手的稀疏不可知线性赌博机

    我们研究了随机线性臂问题，在每一轮中，学习者接收一组动作（即特征向量），从中选择一个元素并获得随机奖励。期望奖励是所选动作的一个固定但未知的线性函数。我们研究了稀疏遗憾界，其依赖于线性奖励函数中的非零系数数目 $S$。先前的研究关注 $S$ 已知的情况，或者动作集满足额外假设的情况。在这项研究中，我们首次获得了在 $S$ 未知且动作集由对手生成时成立的稀疏遗憾界。我们的技术将在线转换为置信区间，并结合一种新颖的层级置信区间随机模型选择方法。当 $S$ 已知时，我们的分析恢复了对于对手动作集的最先进界限。我们还表明，我们的方法的一种变体，使用 Exp3 动态选择置信区间，可用于提高随机线性臂问题的实证性能，同时享受对于时间段的最优遗憾界限。

    Jun, 2024

  • 针对随机情境对决赌徒的方差感知后悔界限

    本研究提出了一种基于广义线性模型的上下文对决算法，该算法在计算效率和方差感知遗憾边界方面有优势，并通过实验验证了其优于以往无方差算法的优点。

    Oct, 2023