Reinforcement Learning by Probability Matching

Philip N. Sabes, Michael I. JordanNeurIPS 1995

Abstract / TL;DR The "Probability Matching" (PM) algorithm improves reinforcement learning by matching a network's output distribution to a target distribution derived from environmental rewards. This approach prevents premature convergence to local minima and is uniquely effective at training "Mixture of Experts" architectures where traditional methods like REINFORCE often fail.

1. Introduction: The Problem with Standard RL

In associative reinforcement learning, a learner receives a scalar reward rather than a direct error signal (gradient). This makes learning notoriously slow and prone to "local minima"—solutions that look good early on but are far from optimal.

The authors highlight a specific failure mode in Mixture of Experts (MoE) networks. In an MoE setup, different "expert" sub-networks should ideally learn different parts of a task. However, standard RL algorithms like REINFORCE often suffer from a "winner-take-all" effect: one expert happens to perform slightly better early on, the algorithm puts all its "weight" there, and the other experts are never trained. This wastes the representational power of the network.

2. Methods: The Probability Matching Approach

The core innovation of this paper is the Probability Matching (PM) cost function, which shifts the objective from simple reward maximization to distribution matching.

  • Boltzmann Distribution as a Target: The authors treat rewards as "inverse energies." They define a theoretical target distribution, $p^*$, where high-reward outputs are highly probable and low-reward outputs are improbable. This is controlled by a temperature parameter ($T$).
  • KL Divergence: Instead of just maximizing reward, the algorithm minimizes the Kullback-Leibler (KL) divergence between the network’s actual output distribution and this ideal reward-based target.
  • The Free Energy Analogy: Mathematically, this cost function decomposes into two parts: the negative of the average reward and an entropy term scaled by $T$. This makes the algorithm behave like a physical system seeking a "free energy" minimum.
  • Annealing: By starting with a high $T$, the network is forced to maintain high entropy (broad exploration). As $T$ is lowered (annealed), the network "sharpens" its focus onto the highest-reward areas.
Annealing process showing the output distribution sharpening as temperature T decreases from 1 to 0.05.

The authors derive specific update rules for Gaussian units and Mixtures of Gaussian Experts, showing that the PM rule is essentially a reward-modulated version of standard supervised learning.

3. Experimental Setup

The paper uses three synthetic simulation environments to benchmark the algorithm against REINFORCE and REINFORCE with reinforcement comparison (REINF-COMP):

  • Linear Mapping: A task where a mixture of three Gaussian experts must learn a $2 \times 3$ matrix transformation.
  • Absolute Value Function: A non-linear task requiring a mixture of two experts to coordinate.
  • Multi-modal Reward Landscape: A "toy" environment with many local maxima of increasing heights to test the algorithm's ability to escape local traps.

4. Key Insights

  • Entropy as a Safety Net: By explicitly including an entropy term in the cost function, PM prevents the network from "collapsing" its search space too early. This is the "Probability Matching" namesake: the network tries to match the diversity of the reward landscape.
  • Solving the MoE "Starvation" Problem: In the linear example, REINFORCE converged to a solution where only one expert was active (entropy $\approx 0.21$). PM kept all three experts active (entropy $\approx 0.99$), allowing the network to utilize its full architecture.
  • Adaptive Variance: In landscapes with many local peaks, PM allows the variance of the output to grow to bridge the gap between peaks, whereas REINFORCE tends to shrink its variance as soon as it finds any peak, effectively trapping itself.

5. Key Results

The empirical results demonstrate significant advantages for the Probability Matching approach across speed, reliability, and global optimization capabilities:

  • Speed: In the linear task, PM with $T=1$ was nearly 3x faster than REINFORCE and 50% faster than REINF-COMP.
  • Reliability: In the absolute value task, PM achieved a 100% success rate in convergence, while REINFORCE succeeded only 48% of the time.
  • Global Optimization: In the multi-modal landscape, REINFORCE never made it past the third local peak. PM (with $T=2$) successfully navigated to much higher peaks, reaching values orders of magnitude greater than its competitors.
Performance trajectories demonstrating the algorithm's ability to reach higher reward peaks over time.

6. Limitations and Future Work

  • Annealing Schedules: While the paper suggests that decreasing $T$ over time is beneficial, it does not provide a formal or automated schedule for how to do this optimally.
  • Scope of Units: The empirical tests are limited to Gaussian units. While the authors claim the math extends to logistic or softmax units for classification, these are not demonstrated in the results.
  • Complexity: The simulations are "simple examples." While the authors note that preliminary results on larger problems are promising, the paper lacks a benchmark on high-dimensional, real-world datasets.

Summary updated

BibTeX
@inproceedings{sabes1995reinforcement,
  author = {Philip N. Sabes and Michael I. Jordan},
  title = {{Reinforcement Learning by Probability Matching}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
}
Figure