Gradient Bandit Algorithms
What you'll learn: How to learn action preferences directly through gradient ascent on expected reward, using a softmax policy without estimating action values.
The Core Idea
Until now, you've been estimating action values (how good each action is) and then picking actions based on those estimates. Gradient bandit algorithms flip this approach: they learn action preferences (numerical scores) and update them using gradient ascent to maximize expected reward, never computing explicit value estimates.
Think of it like adjusting your enthusiasm for different restaurants. Instead of tracking "this place is 8/10," you just maintain preference scores and nudge them up when a choice works out (relative to your average experience), without ever calculating exact ratings.
How It Works
You maintain a preference H_t(a) for each action a. These preferences get converted to action probabilities using the softmax distribution:
π_t(a) = exp(H_t(a)) / Σ_b exp(H_t(b))
After selecting action A_t and receiving reward R_t, you update preferences using a policy gradient rule:
- For the chosen action:
H_{t+1}(A_t) = H_t(A_t) + α(R_t - R̄_t)(1 - π_t(A_t)) - For other actions:
H_{t+1}(a) = H_t(a) - α(R_t - R̄_t)π_t(a)
Here R̄_t is a baseline (typically average reward so far), and α is the step size. The key insight: rewards better than baseline increase the chosen action's preference; worse rewards decrease it. Other actions move in the opposite direction.
Why It Matters
This approach works well when you care about the relative ranking of actions rather than their absolute values. The softmax naturally handles exploration through its probabilistic nature, and the algorithm is gradient-based, making it a foundation for policy gradient methods in full RL.
Key Takeaway: Gradient bandit algorithms learn action preferences via softmax policy gradient updates, adjusting scores based on how rewards compare to a baseline—no action-value estimates required.