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