← mackyi.com

REINFORCE

A little agent starts out knowing nothing. Each cell of the maze is one of Williams' stochastic units. After every run, the single reinforcement signal it gets nudges the weights of every unit it used. Eventually it finds the way.

 

Click a cell to cycle it between empty, wall and pit. The agent adapts as it goes.

training
show
episodes
0
success · last 100
0%
steps to goal
–
last episode
–
how episodes end goal timeout pit
milestonesepisode numbers since the last Reset brain · success over the last 50 runs
first goal
–
50% success
–
90% success
–
shortest route
–
reinforcement r
0.50
0.040
Not in the 1992 paper: it's the entropy-maximization idea from Williams & Peng (1991). Warmer/colder scoring barely needs it. With time-aware or naive scoring, set it to 0 and reset to see why it matters.

What's going on, in the paper's terms

Williams (1992) named REINFORCE after its own update rule: REward Increment = Nonnegative Factor × Offset Reinforcement × Characteristic Eligibility. Everything on this page maps onto those pieces.

  1. One stochastic unit per cell. Each cell i is a unit with four weights wij, one per direction. Its output yi (the move) is drawn from a distribution gi, here a softmax of the weights. The arrows show gi. Williams' derivation works for any unit whose g is differentiable in its weights. His worked examples use Bernoulli and Gaussian units; a 4-way softmax is the same idea with four outcomes.
  2. An episode, then one reinforcement. The units act until the agent reaches the goal, falls in a pit, or runs out of 80 steps. Only then does the environment deliver a single scalar reinforcement r. By default (warmer/colder) it depends on how many steps T it took to reach the goal or, if it never got there, on how close it came:
    r = 1 − T/80 (goal) · −1 + 0.8 × closest approach (otherwise)
    "Closest approach" runs from 0 at the start to 1 at the goal, measured along the safe path. The environment knows that distance; the agent never sees it. All it ever gets is one number per episode.
  3. Characteristic eligibility. Each time a unit acts, it records how its weights would change the log-probability of what it just did: eij = ∂ ln gi / ∂ wij. For a softmax unit that's 1 − gij for the move taken and −gij for the others. In the episodic version, a unit used several times sums its eligibilities over the episode.
  4. The update. At the end of the episode, every unit that acted moves its weights by the three factors:
    Δwij = αij · (r − bij) · Σt eij(t)
    α is the nonnegative learning rate factor, and r − b is the offset reinforcement. The reinforcement baseline b here is reinforcement comparison: each unit keeps a running average of the r it has seen, shown as the cell color. Williams' main result is that, for any baseline that doesn't depend on the unit's own output, the expected weight change points uphill on the expected reinforcement. The baseline doesn't change where the agent is heading, only how noisy the steps are. Try turning it off.

Williams leaves the choice of r to the task, and it matters more than anything else on this page. The reinforcement r switch has three versions, each fixing the trap the one before it falls into:

Try it: load the Pit field, pick naive, and press Reset brain. Or click cells to build a winding path through a sea of pits and compare time-aware with warmer/colder. A "Looks stuck" note appears when the signal has gone flat.

One addition: a small entropy bonus that nudges each unit's distribution back toward even. It isn't in the 1992 paper. It's the entropy-maximization strategy Williams and Peng explored in a companion paper. With warmer/colder scoring the default maze is solved without it, because the slope toward the goal does the exploring. With the other two scorings this maze is almost never solved without it: pits are easy to stumble into, so the units learn to fear them long before a random walk ever reaches the goal, and then the agent stops exploring.

Because every unit gets the same end-of-episode r, credit is spread across the whole trajectory, detours included. That's why the agent's runs are wobbly even once it reliably succeeds. Later variants sharpen this with discounting, so steps taken closer to the outcome get more of the credit, but that goes beyond the original paper.

Papers: Ronald J. Williams, “Simple statistical gradient-following algorithms for connectionist reinforcement learning”, Machine Learning 8, 229–256 (1992). Ronald J. Williams and Jing Peng, “Function optimization using connectionist reinforcement learning algorithms”, Connection Science (1991). Everything here runs in your browser in a few hundred lines of plain JavaScript.