May, 2023

高维和低秩张量赌博机

PDF
TL;DRTOFU 算法研究了一个基于张量表示的线性赌博模型，其中系统参数和行动由张量表示，特别关注未知系统张量为低秩张量的情况。它首先利用灵活的张量回归技术估计与系统张量相关联的低维子空间，然后利用这些估计将原始问题转化为具有系统参数范数约束的新问题，最后采用 TOFU 算法，它利用这些约束来避免探索整个高维参数空间，理论分析表明，TOFU 在比先前的最佳后悔上界改善的倍数增加了一个随着系统阶数呈指数增长的系数，同时 TOFU 还建立了一个新的性能下限，进一步证明了 TOFU 的效率。
发现论文，激发创造
  • 高效广义低秩张量内容自助机

    本文提出了一种新颖的多维数据和奖励函数非线性性能充分发挥的强大 Bandits 算法，引入了广义低秩张量上下文 Bandits 模型进行决策服务，并证明其优于向量化和矩阵化情况的后悔界。通过一系列仿真和真实数据实验验证了该算法的有效性，充分利用了低秩张量结构来提升学习性能。

    Nov, 2023

  • 高维线性赌博机和推荐系统

    该研究使用线性参数化多臂赌博机模型来提高在线服务推荐新产品、视频、歌曲和广告的效果，得到了能够满足用户喜好探索和系统数据调查的解决方案，并在 Netflix 和 MovieLens 数据集上进行了测试。

    Jan, 2013

  • 低秩赌博机的紧致二至无穷奇异子空间恢复

    我们研究具有低秩结构的情境强化学习，提出了高效的算法用于策略评估、最佳策略识别和遗憾最小化，这些算法近乎极小化的性能表现可达到理论最优水平。

    Feb, 2024

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

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

    Jun, 2020

  • 分解赌博机

    该研究介绍了因式赌博模型，它是一种基于有限（赌博）反馈的学习框架，其中行动可以分解为原子行动的笛卡尔积。因式赌博将等级 1 赌博作为一个特例，但显着放宽了奖励函数形式的假设。我们提供了一种随时随地的随机因式赌博算法，并匹配了问题的上界和下界的常数。此外，我们表明，通过轻微修改，所提出的算法可以应用于效用基础的反复决斗赌徒。相对于现有算法，我们在遗憾边界的附加项方面获得了改进（这些附加项在时间范围内占支配地位，该时间范围呈指数增长）

    Jul, 2018

  • 高维稀疏线性赌博机

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

    Nov, 2020

  • 结构化随机线性 Bandits

    研究如何在处理具有结构属性的未知参数（例如稀疏、分组稀疏、低秩）的随机线性 Bandit 问题中构建置信椭圆，以达到更紧密的置信度范围和更尖锐的失误边界。

    Jun, 2016

  • 线性参数化赌博机

    本文研究基于多维随机向量臂收益的赌博机问题，证明了在解决特定问题时使用相应的相位策略可以达到最优的累计遗憾和贝叶斯风险，并提出了针对通用问题的近似最优解。

    Dec, 2008

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

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

    Nov, 2023

  • 序贯决策和广义博弈的赌徒线性优化

    报告描述了如何设计面向 TFSDM 的探索 - 利用算法以解决困难的在线决策问题

    Mar, 2021