REINFORCE

Main ideas / concepts conveyed

• Policy parameterization

  • The parameters of a policy are denoted (\Theta).

  • (\Theta) may be composed of multiple parameters, e.g. [ \Theta = (\theta_1,\theta_2,\dots,\theta_K). ]

  • A specific choice of (\Theta) corresponds to one policy.

• Performance measure for a policy

  • Define policy performance as expected payoff:
    • (EA(\theta)): performance/evaluation of the policy under parameter value (\theta).

  • Expected payoff is written using standard policy notation:

    • (\Pi(a;\Theta)) = probability of selecting action/arm (a) given parameters (\Theta).
    • The expected value becomes: [ EA(\Theta) = \sum_a \Pi(a;\Theta)\, Q^*(a). ]

  • Special case: deterministic policy

    • Only one action has probability 1; all others have probability 0.
    • Then the payoff reduces to the corresponding (Q^*(a)).

• Gradient ascent on the performance

  • Since the true function form may be unknown, the method uses gradients with respect to (\Theta) to increase performance.
  • Gradient ascent idea:
    • If performance improves by changing (\Theta) in some direction, update (\Theta) toward that direction.
  • Uses an iterative process (small step updates) rather than solving in closed form.

• Why “stochastic” updates are needed

  • The true quantity being optimized involves expectations, and the system is accessed via sampling:
    • You can sample actions according to the current policy (\Pi(a;\Theta)).
    • You observe rewards generated by the environment.
  • Because the gradient is estimated from samples, it can be noisy/wrong in any single step.
  • Stochastic gradient methods (general idea behind SGD, here used as “ascent”) work because:
    • Over many updates, the expected direction matches the true gradient direction.

• How the gradient is estimated (policy gradient / REINFORCE derivation setup)

  • The derivation rewrites the gradient of the expected payoff into a form that looks like an expectation over trajectories/samples drawn from (\Pi).
  • Key condition:
    • For the manipulations (multiplying/dividing by (\Pi)) to work, (\Pi(a;\Theta)\neq 0) for all actions (a).
  • Sampling interpretation:
    • At each iteration, pull an arm/action sampled from (\Pi(\cdot;\Theta)).
    • Receive reward, related to (Q^(a)) (and (Q^) is itself an expectation).
  • The gradient estimate uses:
    • Observed reward samples
    • The derivative of the policy log-probability (e.g., terms like (\nabla_\Theta \log \Pi(a;\Theta)) / (\nabla_\Theta \Pi(a;\Theta)), depending on the algebra shown).

• Update step structure for parameter updates

  • Two update modes are discussed:
    • Batch mode: fix (\Theta), sample (N) times, average, compute gradient, then update.
    • Incremental mode: update after (or per) each sampled experience.

  • Incremental update form: [ \Theta_{n+1} = \Theta_n + \Delta\Theta_n. ]

  • Reinforcement baseline (B_n) is introduced:

    • Add a term without changing the expected update direction, as long as (B_n) is not a function of the sampled action (i.e., not dependent on (a) in a way that changes the gradient’s unbiasedness).
    • Baseline intuition:
      • If reward is above baseline → push parameters to increase probability of that action.
      • If reward is below baseline → push parameters to decrease probability of that action.
    • Common baseline choice:
      • Average of past rewards (running mean).

• Variance reduction vs. cost

  • Baseline typically:
    • reduces variance → more stable convergence
    • but may add computational/implementation overhead.

• Actor-critic connection (mentioned as future topic)

  • When value estimates are learned alongside the policy:
    • (\Pi) acts as actor (policy)
    • (Q)-type estimates act as critic
  • This can address drawbacks of pure policy gradient methods like REINFORCE.

• REINFORCE algorithm background

  • REINFORCE is attributed to Williams (1988).
  • Proposed in the context of neural networks.
  • Key theoretical point:
    • Even though the gradient is estimated from one sampled action (high variance),
    • the expected update points in the correct direction.
  • Practical drawback:
    • extremely slow due to high variance.

• REINFORCE abbreviation

  • The expansion of “REINFORCE” is mentioned as unknown/forgotten by the speaker (humorously).

---

Methodology / workflow (REINFORCE / stochastic policy gradient)

1) Choose policy parameterization

• Define a policy (\Pi(a;\Theta)) mapping parameters (\Theta) to action probabilities.
• Ensure (\Pi(a;\Theta) > 0) for all actions (a) (required for the gradient estimation algebra).

2) Define the performance objective

• Use expected payoff: [ EA(\Theta) = \sum_a \Pi(a;\Theta)\,Q^*(a). ]

3) Iteratively increase performance using gradient ascent

• Update (\Theta) in the direction that increases (EA(\Theta)).
• Because (Q^*(a)) is unknown/intractable, estimate gradients via sampling.

4) Estimate the gradient using samples

• For current (\Theta):
  • sample (a \sim \Pi(\cdot;\Theta))
  • observe a reward sample from the environment dynamics
• Construct a gradient estimator using:
  • reward samples
  • policy gradient terms (derivatives of policy probability/log-probability w.r.t. (\Theta))
• Use either:
  • batch averaging over (N) samples, or
  • incremental per-sample updates.

5) Update parameters

• Apply: [ \Theta_{n+1} = \Theta_n + \Delta\Theta_n ]

• Use learning rate (\alpha_n) (or (\alpha)).

6) (Optional) Add a reinforcement baseline

• Introduce (B_n) (baseline/reward centering term):
  • must not depend on the sampled action (a) to keep the expected gradient correct
• Use an advantage-like term:
  • reward minus baseline (e.g., (R_n - B_n))
• Typical choice:
  • (B_n =) running average of past rewards.

7) Continue iterations

• Repeat: sample → estimate gradient → update (\Theta).
• Convergence is discussed as correct in expectation over many updates, not necessarily per-step.

---

Special cases / examples given

• Binary bandit (two actions)

  • Actions: (a \in {0,1})

  • Policy parameterization: [ \Pi(a=1;\Theta)=\Theta,\quad \Pi(a=0;\Theta)=1-\Theta. ]

  • Policy gradient terms become simple:

    • when (a=1): involves (1/\Theta)
    • when (a=0): involves (-1/(1-\Theta))
  • Learning rate choice discussed:
    • pick (\alpha\propto \Theta(1-\Theta)) to cancel constants.
  • Baseline chosen as (B=0).
  • Intuition (from the simplified example):
    • If action 1 yields reward 1 → (\Theta) updates upward.
    • If action 1 yields reward 0 → no update.
    • If action 0 yields reward 1 → update pushes (\Theta) downward.

• Softmax for (K) discrete actions

  • Policy: [ \Pi(a=i;\Theta)=\frac{e^{\Theta_i/\Beta}}{\sum_{j} e^{\Theta_j/\Beta}}. ]

  • Homework suggestion:

    • derive REINFORCE updates under softmax action selection.

• Continuous actions (conceptual motivation)

  • REINFORCE extends naturally to continuous action spaces.
  • Value-function approaches can be harder in continuous action settings.

---

Homework / tasks mentioned

• Derive/update rules for specific setups
  • Derive REINFORCE update rules for:
    • softmax action selection (discrete case)
  • For continuous actions:
    • derive REINFORCE update rules for parameters of a distribution (hinted example: Gaussian policy parameters (\mu) and (\sigma)).
  • Homework also includes simplifying algebra using learning-rate choices ((\alpha)) to cancel constants.

---

Speakers / sources featured

• Speaker: Not explicitly named in the subtitles (an instructor/lecturer presented the material).
• Named source:
  • Williams (1988) — credited with proposing the REINFORCE algorithm (originally in the context of neural networks).