Concepts / Reward Baselines in Gradient Bandit Algorithms

Reward Baselines in Gradient Bandit Algorithms

Gradient bandit algorithms converge because their expected update is the gradient of expected reward.

  • Programming

The Direction of Learning

A gradient bandit algorithm learns from rewards, but one sampled reward can be noisy. A single update does not necessarily point toward higher expected reward. The important claim concerns the expected update: when the possible stochastic updates are averaged, their direction is the gradient of expected reward. This is why gradient bandit learning is an instance of stochastic gradient ascent.

shape choice probabilitiesproduces参与atesinfluencesaveraged over possibilitiespoints toward its gradientAction preferencesinternal estimatesSelected actionprobabilistic choiceSampled rewardstochastic signalPreference updateone noisy updateExpected updateaverage directionExpected rewardincreasing direction
How do sampled rewards and action preferences combine so that the expected parameter update points toward increasing expected reward?

The convergence argument is about an average over stochastic updates, not about the direction of every individual update.

Preferences Before Values

Gradient bandit algorithms use action preferences as their internal estimates. These preferences are not the same thing as estimates of each action's expected value. Instead, the preferences help define a policy: they determine how likely each action is to be selected.

The preferences are passed into a soft-max distribution. A stronger preference gives an action a higher likelihood of selection, but does not eliminate probabilistic exploration. The result is graded exploration: actions can have different probabilities rather than being limited to an all-or-nothing choice.

contributescontributesassigns probabilityassigns higher probabilityLower preferenceaction AHigher preferenceaction BSoft-max distributiongraded probabilitiesAction Alower likelihoodAction Bhigher likelihood
How do action preferences become probabilities, and how does changing one preference alter the probability of selecting each action?

Reading a preference-based policy

Imagine three available actions with lower, middle, and higher preference estimates.

Start with preferences: The algorithm stores a preference for each action rather than treating an action-value estimate as the policy itself.

Apply soft-max: The preferences are converted into a probability distribution. The action with the higher preference becomes more likely, while the other actions still retain probabilistic selection.

Select an action: The learner makes a probabilistic choice from that distribution. Selection is therefore graded rather than completely deterministic.

A stronger preference changes the action-selection probabilities without eliminating probabilistic exploration.

Baseline and Expected Update

A reward baseline is used in the update, but the expected-update argument does not require one special baseline value. The stated requirement is that the baseline must not depend on the selected action. Under that condition, different baselines can preserve the same expected update.

For example, the source identifies a baseline of zero and a baseline of 1000 as two choices that leave the method as an instance of stochastic gradient ascent. This does not mean that the two choices produce the same individual update. Their sampled updates can differ. The claim is that their expected update remains the same for the stated action-independent-baseline argument.

affectsaverages toaffectsaverages toBaseline 0action-independentBaseline 1000action-independentSampled updateone stochastic resultSampled updateone stochastic resultExpected updategradient of expected rewardExpected updategradient of expected reward
Why can different baselines change individual updates without changing the expected update direction?

Stochastic Ascent in Practice

Across repeated samples, the algorithm receives stochastic rewards and makes stochastic preference updates. Some updates may point away from the direction of increasing expected reward. As the expected update is considered over the possible stochastic outcomes, however, the average direction is the gradient of expected reward. Repeated noisy movement therefore has the structure of stochastic gradient ascent.

select and observeinfluencesrepeatsexpected direction points towardInitial preferencespolicy stateSample rewardstochastic outcomeNoisy updateone stepRepeated samplesaverage behaviorHigher expectedrewardgradient direction
What happens across repeated samples as noisy preference updates move the policy toward higher expected reward?

  • Assuming every sampled update must point toward higher expected reward.

    Individual updates are stochastic and do not necessarily point exactly toward higher expected reward.

    Fix: Inspect the expected update by averaging over the possible stochastic updates.

  • Concluding that changing the baseline changes the expected update direction.

    For the stated argument, any baseline that does not depend on the selected action preserves the expected update.

    Fix: Separate the expected update from the variance and convergence-rate effects of the baseline.

Three Exploration Mechanisms

MethodInternal basisExploration behavior
ε-greedyAction choice with occasional random selectionOccasionally chooses randomly
UCBAction-value-based comparison with sample-count informationChooses deterministically while giving an advantage to actions that have received fewer samples
Gradient banditAction preferences converted through soft-maxUses a probability distribution in which stronger preferences increase likelihood without eliminating probabilistic exploration

ε-greedy, UCB, and gradient bandit methods all address the tension between exploration and exploitation, but they do so differently. ε-greedy uses occasional random choices. UCB makes a deterministic choice while giving some advantage to actions that have received fewer samples. Gradient bandits do not estimate action values as their policy mechanism; they maintain preferences and turn those preferences into a soft-max probability distribution.

The defining movement in a gradient bandit method is action preferences to soft-max distribution to probabilistic action selection.

Check Your Reasoning

MEDIUM

A learner claims: “Because one sampled update can point away from higher expected reward, gradient bandit algorithms are not performing gradient ascent.” Evaluate the claim and explain the role of the expected update.

Hints
  • Distinguish one stochastic update from the average of possible updates.
  • State what the expected update equals.
  • Connect that equality to stochastic gradient ascent.
MEDIUM

Compare these two statements: “The baseline changes the expected update” and “The baseline changes convergence behavior.” Which statement is supported by the action-independent-baseline argument, and why?

Hints
  • The baseline must not depend on the selected action.
  • Separate expected update from update variance.
  • Remember that convergence rate can change even when expected update does not.

Key Takeaways

  1. Gradient bandit algorithms converge because their expected update is the gradient of expected reward.
  2. Individual updates are stochastic, so a single update need not point toward higher expected reward.
  3. An action-independent baseline preserves the expected-update argument, although it can change update variance and convergence rate.
  4. Gradient bandits maintain action preferences and use soft-max to create graded probabilistic exploration.
  5. ε-greedy explores through occasional random choices, UCB explores through deterministic preference for less-sampled actions, and gradient bandits explore through preference-based probabilities.

Key Takeaways

  • The expected update, not each individual update, is the central object in the convergence argument.
  • That expected update equals the gradient of expected reward, making gradient bandit learning stochastic gradient ascent.
  • Action-independent baselines can leave the expected update unchanged while changing update variance and convergence rate.
  • Action preferences become graded probabilities through soft-max, producing probabilistic exploration.
  • Gradient bandits differ from ε-greedy and UCB because their exploration comes from a preference-based probability distribution.

Related Topics