Jul, 2020

稀疏不可知 Lasso Bandit

PDF
TL;DR本文提出了一种算法来解决随机上下文赌博机问题，该问题中特征向量的维数可能很大，但仅有一个小的稀疏特征子集会影响奖励函数，该算法可以在不需要先前了解稀疏度的情况下使用，并在温和条件下，确立了性能方面的紧密后悔界限，同时，我们全面评估了我们提出的算法的性能，并表明即使将正确的稀疏度指数暴露给现有方法，但将其保持对我们算法隐藏，我们的算法也能始终优于现有方法。
stochastic contextual banditsparse subsetregret boundsalgorithmperformance
发现论文，激发创造
  • 阈值套索强化学习算法

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

    Oct, 2020

  • 稀疏线性动态单臂赌博问题的协作阈值套索算法

    本文提出了一种用于解决多智能体稀疏背景下的上下文线性赌博问题的新方法，通过使用 Lasso 回归进行维度缩减、回归进行问题解决、结合特定过程和网络结构共享信息，达到降低通信成本、保证最小累计遗憾值的效果，并在合成和真实场景下验证了方法的有效性。

    May, 2023

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

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

    Jun, 2024

  • 双重稳健套索赌博机

    提出了一种新的算法：Doubly-Robust Lasso Bandit algorithm，它利用线性回归参数的稀疏结构，融合在缺失数据文献中使用的双重稳健技术，解决了高维稀疏环境下多臂赌博机算法的问题，大大减少了调参数量和算法复杂度。

    Jul, 2019

  • 具有最优臂兼容条件的套索赌徒

    这篇论文研究了一种稀疏线性的随机赌博问题，其中只有稀疏的上下文特征子集影响预期的回报函数。作者提出了一个算法，借助强制抽样技术，在单参数设置下表现出 polylog 的 dT 遗憾，相较于 Lasso 赌博算法，该算法假设更弱且性能更好。

    Jun, 2024

  • 高维稀疏线性赌博机

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

    Nov, 2020

  • 方差感知稀疏线性赌博机

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

    May, 2022

  • 稀疏随机赌博机

    本文研究了经典多臂老虎机问题的稀疏情况，并提出了一种算法，其遗憾值与臂数的正比例关系被缩小至仅与正收益臂数相同，同时证明了其最优性。

    Jun, 2017

  • 高维线性多臂赌博机与背包问题

    研究如何在高维度环境下应用稀疏估计和在线学习算法改进上下文强化学习中的多臂老虎机与背包问题，通过联合在线估计和原始 - 对偶框架，控制背包容量，从而取得了特征维度对数级依赖的次线性遗憾，同时在数据贫瘠和数据丰富情况下实现了最优遗憾结果。

    Nov, 2023

  • 稀疏性对于学习未正确规定的线性臂上的影响

    研究了线性错误赌博机的问题，并探讨了稀疏性在错误赌博机学习中的作用和限度，提出了一种新的算法，并且证明了该算法的样本复杂度近似最优。

    Mar, 2023