Bootstrapped Thompson Sampling and Deep Exploration
Ian Osband Benjamin Van Roy
Abstract
This technical note presents a new approach to carrying out the kind of exploration achieved by Thompson sampling, but without explicitly maintaining or sampling from posterior distributions. The approach is based on a bootstrap technique that uses a combination of observed and artificially generated data. The latter serves to induce a prior distribution which, as we will demonstrate, is critical to effective exploration. We explain how the approach can be applied to multi-armed bandit and reinforcement learning problems and how it relates to Thompson sampling. The approach is particularly well-suited for contexts in which exploration is coupled with deep learning, since in these settings, maintaining or generating samples from a posterior distribution becomes computationally infeasible.
中文速览
用自举法（bootstrap）来模拟后验采样，是这篇文章解决的核心问题：在强化学习和多臂赌博机（multi-armed bandit）等序贯决策任务中，汤普森采样（Thompson sampling）需要维护并从后验分布中抽样，但当模型是深度神经网络这类非线性结构时，这在计算上几乎不可行。作者提出"带人工数据的自举汤普森采样"（Bootstrapped Thompson Sampling）——关键创新在于把真实观测数据与人工生成的伪数据混合后再做自举，其中人工数据起到诱导先验分布的作用，从而让算法在没有观测的动作上仍能保持合理的不确定性估计。实验表明，缺少人工数据时算法会因探索不足而陷入次优策略，加入人工数据后则能有效驱动探索并显著降低累积遗憾（regret）。这一方法天然可并行化，能直接套用在深度神经网络上，为大规模深度强化学习中的高效探索提供了一条既实用又有理论支撑的新路径。
原文 arXiv:1507.00300;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1507.00300v1