← Back to all posts
Reinforcement LearningMulti-Armed BanditsContextual BanditsLinUCB

Multi-Armed and Contextual Bandits: Reinforcement Learning Without State Transitions

Bandits explained as the simplest possible RL problem — no state transitions, just repeated action selection under uncertainty — covering epsilon-greedy, UCB1, Thompson Sampling for the stationary case, and LinUCB for contextual bandits, with code and applications in online recommendation and A/B testing.

O Ohara University · · 11 min read

TL;DR

Strip away state transitions from an MDP entirely — no notion of one action leading to a different situation next time — and what’s left is a multi-armed bandit: repeatedly choose among a fixed set of actions (“arms”), observe a reward, and try to maximize cumulative reward over time. It’s the cleanest possible testbed for the explore/exploit trade-off, and the exploration techniques covered in the companion exploration-strategies article (epsilon-greedy, UCB, Thompson Sampling) were largely developed and analyzed in this simpler bandit setting first. Contextual bandits add back a single piece of state — context about the current situation — without full state transitions, and LinUCB is the standard method for that setting. Used pervasively in online recommendation, ad placement, and A/B testing, where the “next state” genuinely doesn’t depend on which arm you pulled.

The Bandit Loop

graph LR
    A[Observe Context - optional] --> B[Choose an Arm]
    B --> C[Observe Reward]
    C --> D[Update That Arm's Estimate]
    D -->|next round| A

    style D fill:#6366f1,color:#fff

Problem Statement

Full RL’s hardest problems — credit assignment across a long trajectory, learning a value function over an entire state space — are all consequences of actions affecting future states. Many real problems don’t have that structure at all: showing a user one of several ad creatives doesn’t change what ad creative will be relevant to the next user who arrives. Bandits formalize this simpler setting explicitly, and because there’s no long-horizon credit assignment problem to solve, bandit algorithms can offer much stronger theoretical guarantees (provable regret bounds) than general RL usually can.

Epsilon-Greedy and UCB1: The Stationary Bandit Baselines

The same exploration strategies covered in the companion article apply directly, in their original, simplest form:

def epsilon_greedy_bandit(arm_estimates, epsilon):
    if random.random() < epsilon:
        return random.randint(0, len(arm_estimates) - 1)
    return np.argmax(arm_estimates)

def ucb1_bandit(arm_estimates, arm_pull_counts, total_pulls):
    bonus = np.sqrt(2 * np.log(total_pulls) / (arm_pull_counts + 1e-6))
    return np.argmax(arm_estimates + bonus)

UCB1 specifically has a clean, provable regret bound — the gap between its cumulative reward and the reward of always pulling the single best arm grows only logarithmically with the number of rounds, one of the cleanest theoretical guarantees in all of sequential decision-making, and a guarantee that gets substantially harder to establish once state transitions are added back in.

Thompson Sampling for Bandits

Thompson Sampling (also covered in the companion exploration article) is particularly natural in the bandit setting because each arm’s reward distribution can be tracked with a simple conjugate posterior — a Beta distribution for binary (click/no-click) rewards is the canonical example:

class BetaBanditArm:
    def __init__(self):
        self.alpha, self.beta = 1, 1   # uniform prior

    def sample(self):
        return np.random.beta(self.alpha, self.beta)

    def update(self, reward):
        self.alpha += reward
        self.beta += (1 - reward)

def thompson_sampling_bandit(arms: list[BetaBanditArm]):
    sampled_values = [arm.sample() for arm in arms]
    return np.argmax(sampled_values)

This exact algorithm, applied to click-through-rate optimization, is one of the most widely deployed RL-adjacent techniques in production internet systems, largely because the Beta-Bernoulli conjugate pair makes the posterior update a two-line increment rather than requiring any approximate inference.

Contextual Bandits: Adding Context Without Full State Transitions

Contextual bandits add one piece of realism: before choosing an arm, the agent observes a context vector (e.g., a user’s features) that affects which arm is best, but — critically — the context for the next round is drawn independently, not determined by which arm was chosen this round. This is the key structural difference from full RL: context varies, but there’s still no state transition to reason about.

LinUCB (Li et al., 2010) assumes each arm’s expected reward is linear in the context, and maintains a confidence bound around that linear estimate per arm:

def linucb_select_arm(context, arm_models, alpha=1.0):
    scores = []
    for arm in arm_models:
        theta_hat = arm.A_inv @ arm.b                                    # ridge regression estimate
        predicted_reward = context @ theta_hat
        confidence_width = alpha * np.sqrt(context @ arm.A_inv @ context)
        scores.append(predicted_reward + confidence_width)               # optimistic upper bound
    return np.argmax(scores)

def linucb_update(arm_model, context, reward):
    arm_model.A_inv = sherman_morrison_update(arm_model.A_inv, context)  # incremental matrix update
    arm_model.b += reward * context

The same UCB principle from the stationary case — act optimistically under uncertainty — carries over directly, just with the point estimate and confidence bound now computed via linear regression over the context rather than a simple running average per arm.

Comparison Table

MethodSettingRegret GuaranteeKey Idea
Epsilon-GreedyStationary banditWeak (linear regret without decay)Random exploration a fixed fraction of the time
UCB1Stationary banditLogarithmic regret (provable)Optimism proportional to uncertainty
Thompson SamplingStationary banditNear-optimal, often matches UCB1 empiricallySample from a posterior, act on the sample
LinUCBContextual banditSublinear regret under linearity assumptionUCB principle applied to a linear reward model per arm

Applications

Key Learnings

  1. Bandits are RL with the hardest part removed, and that’s exactly what makes them a good place to learn exploration theory. Every exploration strategy in the companion exploration article — UCB, Thompson Sampling — was analyzed most cleanly in this setting first, before being adapted to full RL where credit assignment complicates the picture.
  2. The stationary/contextual distinction is really about whether “state” exists at all, not how complex the reward function is. A contextual bandit’s context can be a rich, high-dimensional feature vector and still not be full RL, as long as the agent’s action doesn’t influence what context arrives next.
  3. Bandits are probably the single most deployed RL-adjacent technique in production internet systems, precisely because so many real recommendation and ranking problems genuinely lack the state-transition structure that would require reaching for full RL machinery at all.

References