Reproduce “Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Tong Zhang

Feel-Good Thompson Sampling (FGTS) introduces an optimistic modification to standard Thompson Sampling, enabling it to achieve minimax optimal frequentist regret bounds across diverse contextual bandit scenarios, including linearly embeddable settings, and extends these guarantees to contextual reinforcement learning with deterministic transitions. This framework resolves long-standing theoretical gaps regarding Thompson Sampling's performance in worst-case frequentist analyses.

Key insights

  • Standard Thompson Sampling can exhibit linear regret in worst-case frequentist scenarios, demonstrating that explicit optimism (as introduced in FGTS) is crucial for achieving optimal frequentist performance.
  • The novel "decoupling coefficient" technique is a general analytical tool that simplifies Thompson Sampling regret analysis by reducing complex stochastic dependencies to an online least squares estimation problem.
  • A unified analytical framework can successfully extend Thompson Sampling's theoretical guarantees, achieving minimax optimal frequentist regret bounds across finite-action, linearly embeddable contextual bandits, and contextual MDPs with deterministic transitions.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.