Bayesian Bandits and Thompson Sampling
Bernoulli Reward Processes
From Complex Worlds to a Single Choice
You're familiar with reinforcement learning environments where an agent navigates a world, moving from state to state. Think of a game of chess or a robot learning to walk. These are modeled by Markov Decision Processes (MDPs), where actions influence future states and rewards are collected over a long horizon. Now, let's strip that complexity away. What if there's only one state? What if the world never changes, no matter what you do? You're faced with a single, repeatable decision, and your only goal is to maximize your immediate winnings. This is the world of the Multi-Armed Bandit (MAB), and it serves as a powerful, simplified model for understanding a core RL challenge: the exploration-exploitation tradeoff.
The multi-armed bandit introduces one of the core dilemmas of reinforcement learning: How to make good decisions under uncertainty.
In a MAB problem, you can think of the environment as a very special kind of MDP. It's an MDP with a single, terminal state. You take an action (pull an arm), you get a reward, and the episode ends. You are instantly returned to the exact same state to make another choice. The transition function is an identity mapping; your actions don't lead you to a new situation. This simplification is profound. It removes the need for complex strategies related to long-term planning, like temporal credit assignment or discount factors. The entire problem boils down to what you do right now to get the best immediate reward.
The Bernoulli Reward Process
In this simplified world, the reward isn't a guaranteed value. It's probabilistic. When you pull the arm of a slot machine, you either win or you don't. This binary, success-or-failure outcome is perfectly described by a a fundamental concept in probability. Each pull of an arm is a single Bernoulli trial. We can define a "success" (winning) as a reward of 1 and a "failure" (losing) as a reward of 0. The key is that each arm has its own, unknown probability of success, which we'll call . Your goal as the agent is to figure out which arm has the highest .
The expected reward for a single pull of an arm is therefore simply its success probability, . This is because the expected value is the sum of each outcome multiplied by its probability. The goal of any bandit algorithm is to estimate the hidden parameter for each arm and use those estimates to maximize the total reward collected over many trials.
| Feature | Multi-Armed Bandit (Bernoulli) | Full Reinforcement Learning (MDP) |
|---|---|---|
| State Space | Single, non-changing state | Multiple states |
| Action Impact | Determines immediate reward only | Determines next state and immediate reward |
| Reward Structure | Immediate reward from a simple probability distribution | Can be delayed; depends on a sequence of actions |
| Core Challenge | Exploration vs. Exploitation | Exploration vs. Exploitation AND Temporal Credit Assignment |
| Horizon | Single step per episode | Multi-step, potentially infinite horizon |
By parameterizing the reward for each arm as a Bernoulli process, we create a clean, understandable environment. This allows us to isolate and study the exploration-exploitation dilemma without the confounding factors of a changing state or delayed consequences. It's the perfect laboratory for developing strategies that balance trying new things with sticking to what's known to be good.
How is a Multi-Armed Bandit (MAB) problem best described in the context of a Markov Decision Process (MDP)?
The Multi-Armed Bandit problem serves as a simplified model primarily to study which fundamental challenge in reinforcement learning?