序列决策问题中汤普森采样的理论与应用研究

序列决策问题中汤普森采样的理论与应用研究

论文摘要

现实生活中的很多问题可以被模型化为序列决策问题。在序列决策问题中,算法通过与未知且充满噪音的环境交互最大化累积收益。汤普森采样算法是解决随机序列决策问题最重要的算法之一,它使用贝叶斯启发式策略平衡序列决策问题中的探索利用权衡。虽然该算法在很多应用中被证明有效,对汤普森采样的理论分析还比较匮乏。复杂模型中信息在不同策略间的共享机制还没有被完全的理解,而汤普森采样能够平衡探索利用权衡的原因还没有彻底的研究。在很多应用领域,汤普森采样对环境的随机静态假设并不成立,这个不足之处限制了其在高动态和大规模问题中的实际应用。本论文对汤普森采样的理论保障和实际应用两个方面对当前研究进行了扩展。本论文的具体工作概括如下:1.通过使用鞅论为基础的分析方法,本文证明线性汤普森采样算法的频率损失上界与其贝叶斯损失上界和该问题的信息论下界相匹配。本文的理论分析量化了该问题中的探索利用权衡并且部分揭示了线性模型中信息共享的机制。本文还通过实验验证了该证明中假设的合理性和结论的真实性。2.通过损失分解和矩阵鞅论的相关理论,本文证明线性级联汤普森采样算法的期望损失上界与当前最优的上置信界算法相同。本文的分析指出线性级联汤普森采样算法在特征空间的各个方向都进行了充分的探索并最大化利用了已经得到的信息。本文还通过两个真实数据集的实验证明该算法相对于相关算法的优势。3.本文在汤普森采样算法中引入了协同效应。通过引入协同效应,算法可以捕捉环境的实时变化并相应调整其决策方法。实验证明协同汤普森采样算法在协同环境下优于标准汤普森采样算法。并且,本文还在线性模型和非上下文相关模型中提供了对该算法的损失分析。理论分析证明在协同环境下,该算法的性能优于标准的汤普森采样算法。4.本文设计并分析了协同组合级联汤普森采样算法以解决协同环境中的序列决策问题。通过研究收益估计量的方差变化,本文证明该协同算法可以有效的探索环境中未知的聚类结构,并利用环境中的协同信息加速算法的学习过程。本文还在模拟数据集中证明了使用协同信息优势。

论文目录

  • 摘要
  • abstract
  • 第1章 绪论
  •   1.1 研究背景与研究意义
  •   1.2 研究目标与研究内容
  •   1.3 论文组织结构
  • 第2章 汤普森采样研究综述
  •   2.1 Bandit问题与模型
  •     2.1.1 Bandit问题的基本框架
  •     2.1.2 上下文无关模型和上下文相关模型
  •     2.1.3 随机模型和对抗模型
  •     2.1.4 组合模型和级联模型
  •     2.1.5 非静态模型
  •   2.2 随机Bandit算法
  •     2.2.1 UCB算法
  •     2.2.2 汤普森采样算法
  • 第3章 线性汤普森采样的最优频率损失上界
  •   3.1 引言
  •   3.2 线性汤普森采样算法
  •     3.2.1 问题设定和算法
  •     3.2.2 符号和假设
  •   3.3 理论分析
  •     3.3.1 面对的挑战和证明提纲
  •     3.3.2 形式化证明
  •     3.3.3 相关引理
  •     3.3.4 与上下文无关的汤普森采样算法的关系
  •   3.4 实验结果与讨论
  •     3.4.1 模拟数据
  •     3.4.2 性能比较
  •     3.4.3 最小特征值假设
  •   3.5 总结
  • 第4章 线性级联汤普森采样
  •   4.1 引言
  •   4.2 线性级联汤普森采样算法
  •     4.2.1 问题设定和算法
  •     4.2.2 符号和假设
  •   4.3 理论分析
  •     4.3.1 需要面对的挑战和证明提纲
  •     4.3.2 形式化证明
  •     4.3.3 相关引理
  •   4.4 实验结果
  •     4.4.1 Movielens数据集
  •     4.4.2 Yahoo!数据集
  •   4.5 总结
  • 第5章 协同汤普森采样
  •   5.1 引言
  •   5.2 相关工作
  •   5.3 问题模型
  •   5.4 协同汤普森采样算法
  •   5.5 理论分析
  •     5.5.1 非上下文相关模型
  •     5.5.2 线性模型
  •   5.6 实验结果
  •     5.6.1 数据集描述
  •     5.6.2 Yahoo!数据集
  •     5.6.3 Avazu数据集
  •   5.7 总结
  • 第6章 协同组合级联汤普森采样
  •   6.1 引言
  •   6.2 基本设定和算法
  •     6.2.1 问题设定
  •     6.2.2 符号和假设
  •     6.2.3 协同组合级联汤普森采样算法
  •   6.3 算法分析
  •     6.3.1 证明提纲
  •     6.3.2 第一部分的证明
  •     6.3.3 第二部分的证明
  •     6.3.4 相关引理
  •   6.4 实验
  •     6.4.1 模拟数据
  •   6.5 讨论与总结
  • 第7章 总结与展望
  •   7.1 全文总结
  •   7.2 进一步工作的展望
  • 参考文献
  • 致谢
  • 在读期间发表的学术论文与取得的研究成果
  • 文章来源

    类型: 博士论文

    作者: 朱振宇

    导师: 黄刘生

    关键词: 序列决策问题,探索利用权衡,汤普森采样,随机模型,上下文相关模型

    来源: 中国科学技术大学

    年度: 2019

    分类: 基础科学

    专业: 数学,数学

    单位: 中国科学技术大学

    分类号: O212.2;O225

    DOI: 10.27517/d.cnki.gzkju.2019.000011

    总页数: 112

    文件大小: 6007K

    下载量: 92

    相关论文文献

    • [1].小小奇迹 克莱·汤普森[J]. NBA特刊 2019(23)
    • [2].克莱·汤普森 留下来[J]. NBA特刊 2018(10)
    • [3].克莱·汤普森 面对面[J]. NBA特刊 2018(22)
    • [4].火线传真[J]. 当代体育(扣篮) 2016(24)
    • [5].拳赛预告[J]. 拳击与格斗 2017(03)
    • [6].特利斯坦·汤普森的穿搭秘诀[J]. NBA特刊 2017(05)
    • [7].克莱·汤普森 暗影猎手[J]. NBA特刊 2017(04)
    • [8].珠落玉盘 斯蒂芬·库里&克莱·汤普森[J]. 当代体育(扣篮) 2017(01)
    • [9].乔治·格文VS大卫·汤普森 超时空大战[J]. NBA特刊 2017(03)
    • [10].PS主义[J]. 当代体育(扣篮) 2017(01)
    • [11].克莱·汤普森 绝对速度[J]. NBA特刊 2017(01)
    • [12].UFC209 伍德利二度卫冕[J]. 拳击与格斗 2017(04)
    • [13].伊塞亚·托马斯 小鬼当家[J]. NBA特刊 2017(06)
    • [14].一个老师的故事(译文)[J]. 牡丹 2017(11)
    • [15].克雷·汤普森 奔跑流年[J]. 当代体育(扣篮) 2017(13)
    • [16].汤普森夫人[J]. 杂文选刊 2017(07)
    • [17].虚晃后跳投KLAY THOMPSON[J]. NBA特刊 2017(S1)
    • [18].化身车神 克莱·汤普森[J]. NBA特刊 2017(20)
    • [19].克莱·汤普森 大国手[J]. NBA特刊 2016(01)
    • [20].超神之夜 汤普森单节37分[J]. NBA特刊 2015(02)
    • [21].交错时光 克莱·汤普森[J]. 当代体育(扣篮) 2015(17)
    • [22].汤普森夫人[J]. 意林文汇 2015(16)
    • [23].世界上最棒的老师——汤普森夫人[J]. 阅读与作文(初中版) 2013(11)
    • [24].学生亦为吾师——读《汤普森夫人》一文有感[J]. 广东教育(综合版) 2014(Z1)
    • [25].汤普森夫人[J]. 考试(双语读写) 2014(04)
    • [26].开心一刻钟[J]. 小学生(新读写) 2012(Z1)
    • [27].大卫·汤普森 偶像的偶像[J]. 体育世界(扣篮) 2009(18)
    • [28].“科学”的预见[J]. 中学生数理化(七年级数学)(华师大版) 2008(Z1)
    • [29].浅谈《约翰·汤普森简易钢琴教程》教学方法[J]. 艺术研究 2015(04)
    • [30].托尼·汤普森 虎老雄风在[J]. 拳击与格斗 2014(05)

    标签:;  ;  ;  ;  ;  

    序列决策问题中汤普森采样的理论与应用研究
    下载Doc文档

    猜你喜欢