Partition Tree Weighting for Non-Stationary Stochastic Bandits

作者: Joel Veness, Marcus Hutter, Andras Gyorgy, Jordi Grau-Moya

发布时间: 2025-02-27

来源: arxiv

研究方向: 非平稳随机伯努利赌徒问题与通用源编码

主要内容

该论文提出了一种名为ActivePTW的算法，用于解决非平稳随机伯努利赌徒问题。该算法基于通用源编码原理，通过将问题转化为编码问题，从而实现对环境的建模和策略的制定。

1. 提出了一种名为ActivePTW的算法，用于解决非平稳随机伯努利赌徒问题。

2. 将通用源编码技术应用于赌徒问题，实现了对环境的建模和策略的制定。

3. 通过实验证明了ActivePTW算法在非平稳随机伯努利赌徒问题上的有效性，并与其他算法进行了比较。

4. 对ActivePTW算法进行了理论分析，并给出了其性能保证。

1. 通用源编码

2. Krichevsky-Trofimov (KT) 估计

3. 分区树加权

4. 贝叶斯控制规则

5. Thompson抽样

实验结果表明，ActivePTW算法在非平稳随机伯努利赌徒问题上的性能优于其他算法，尤其是在存在多个变化点的情况下。在平稳环境中，ActivePTW算法的性能与Thompson抽样相当。

未来可以进一步研究ActivePTW算法在更复杂环境下的性能，并探索将通用源编码技术应用于其他决策问题。