Video summary

Thompson Sampling

Main summary

Key takeaways

Educational

Main ideas / concepts

  • Bandits as a stepping stone to RL

    • The lecturer frames multi-armed bandit problems as a “necessary evil” knowledge set for reinforcement learning (RL).
    • In the referenced textbook, bandit algorithms (e.g., UCB, and related “reinforcement learning” mentions) are discussed briefly—often in about one paragraph—and are expanded later.
    • Bandits are also portrayed as a large, active, research-rich area on their own.

  • Thompson Sampling / Posterior Sampling

    • The main new topic is Thompson sampling, also called posterior sampling in some literature.
    • Goal: solve an unknown bandit problem by making decisions without knowing the true action values ((Q^*)) in advance.
    • Key Bayesian viewpoint:
      • Treat the unknown true values (Q^) as random variables drawn from a prior distribution*.
      • As data arrives (observed rewards), update this belief using posterior updates.

  • Prior choice and the Beta distribution

    • When rewards are assumed to lie in [0, 1], a natural prior for a probability-like quantity is the Beta distribution (bounded in 0–1, flexible shapes).
    • If the lecturer assumes “I know nothing,” a uniform prior can be used as an uninformative starting belief.

  • From exact Bayesian decision-making to approximation

    • The “exact” posterior decision idea would require computing, for each possible arm, the probability that it is optimal under the posterior beliefs.
    • This can be computationally cumbersome, since it involves evaluating complex probabilities across combinations of arm values.

  • The approximation: sampling a complete bandit instance

    • Posterior sampling approach:
      • Instead of computing which arm is optimal by integrating over all possibilities, draw a random sample of the bandit parameters (Q^*) from the current posterior.
      • This sampled set of (Q)-values defines a single sampled bandit instance.
      • Then select the arm that would be optimal for that sampled instance.

  • Iterative loop and belief narrowing

    • After pulling the sampled-best arm and observing its reward:
      • Update the posterior.
      • The posterior becomes narrower (belief concentrates).
      • The probability of sampling high values for poorly performing arms decreases over time.
    • Eventually, sampling increasingly matches the underlying true bandit, improving decisions.

  • Why it’s getting attention

    • Thompson sampling has drawn interest because it can provide better regret bounds than UCB.
    • Historically, the analysis was difficult, and theoretical guarantees were limited for a long time.
    • More recently (last ~3–4 years mentioned), papers introduced techniques to analyze Thompson sampling.

  • Elimination / round-based versions

    • The discussion contrasts:
      • Methods that eliminate arms (not necessary in standard Thompson sampling).
      • A possible round-based Thompson sampling variant.
    • However:
      • Designing and analyzing the conditions/events used for elimination is tricky.
      • Once those events are defined, the bounding step becomes easier.
    • Standard Thompson sampling often becomes effectively “safe” without explicit elimination because posteriors concentrate.

  • Related work: learning automata / variable-structure finite state machines

    • The lecturer points out an older algorithmic class: learning automata.
    • In particular, variable-structured finite state automata have been used for bandit problems.
    • The lecturer claims some behaviors are similar to posterior sampling.
    • Recently, results showed these algorithms can also achieve logarithmic regret bounds (not just asymptotic convergence), citing work from around late last year (Oct/Nov).

  • Transition to next class

    • Next class will cover bandit/RL methods not depending on estimating the value function (Q).
    • Instead, they will look at learning the probabilities directly for selecting arms.

Thompson sampling methodology (step-by-step)

  1. Assume a prior over unknown action values (Q^*)

    • Choose a prior distribution for each arm’s (Q^*).
    • Common example given:
      • If rewards are in [0, 1], use a Beta distribution.
      • If no prior knowledge: use a uniform prior over [0, 1].

  2. Repeat over time

    • 1) Sample a candidate bandit
      • Draw random samples of the parameters:
        • Sample ( \tilde{Q}_1, \tilde{Q}_2, \tilde{Q}_3, \dots ) from the current posterior.
    • 2) Choose the greedy arm for the sampled instance
      • Compute which arm is best under the sampled ( \tilde{Q} ).
      • Select:
        • ( a_t = \arg\max_a \tilde{Q}_a )
    • 3) Play the selected arm and observe reward
      • Pull the chosen arm (a_t).
      • Observe the realized reward (r_t).
    • 4) Update the posterior
      • Use the observed reward to update beliefs about (Q^*).
      • The posterior distribution becomes narrower (belief concentrates).
    • 5) Continue
      • Continue sampling and updating until the posterior converges sufficiently so that the sampled optimal arm matches the true best arm with high probability.

Speakers / sources featured (as mentioned)

  • “Guys who did the course last year” (course participants; not a named person)
  • A guest lecturer who works in the field (unnamed)
  • The textbook (referenced course textbook; unnamed authors)
  • Research papers (mentioned generally; no specific titles/authors given)
  • A class of algorithms: learning automata / variable structured finite state machines (mentioned as an existing research line; no specific authors named)

Speaker/lecturer (the narrator of the lecture): unnamed

Original video