Simple statistical gradient-following algorithms for connectionist reinforcement learning

Inside the paper

The problem

A learning system may receive a single reinforcement signal for its behavior instead of being told the correct output for each unit. The problem is how to adjust a stochastic network’s parameters using that limited feedback.

The idea

The paper develops a family of rules that combines reinforcement with the sensitivity of the probability of the sampled output to each parameter. The expected update follows an improving direction under the stated assumptions.

How it works

• A stochastic unit samples an output from a distribution whose probabilities depend on adjustable parameters and its input.
• For each parameter, calculate how the log probability of the observed output changes with that parameter.
• Multiply that sensitivity by the reinforcement signal minus an eligible baseline and by a nonnegative learning rate.
• For delayed feedback, accumulate the relevant sensitivities over an episode and apply the final reinforcement to the accumulated terms.

What it showed

The paper proves a relationship between the expected update and the gradient of expected reinforcement, and develops examples for different stochastic units. It also explains that following the gradient in expectation alone does not guarantee convergence to the best solution.

Read it for

Read Sections 3–5 for the objective, theorem and episodic extension, then Section 8 for the convergence limits. The detailed unit-specific derivations can be skimmed on an initial reading.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.