Source-linked AI summary
Taming the Noise in Reinforcement Learning via Soft Updates
Roy Fox, Ari Pakman, Naftali Tishby
TL;DR
Noisy early Q-learning can select biased value estimates and spend subsequent learning unlearning suboptimal behavior. The paper proposes G-learning, which regularizes values by penalizing deterministic policies early and scheduling this penalty over time. The authors report reduced bias, improved convergence, lower exploration costs in examples, and support for prior domain knowledge, while noting that function-approximation extensions remain to be studied.
Problem
Noise makes Q-learning’s min selection bias value estimates and can produce wrong early decisions that slow learning.
Method
G-learning is an off-policy information-theoretic method that penalizes deterministic policies relative to a stochastic prior, with the penalty coefficient scheduled during learning.
Results
G-learning reduces value-estimation bias and improves convergence in examples; with ϵ-greedy exploration, it also chooses a less costly exploration policy.
Takeaways & Limitations
G-learning can incorporate prior domain knowledge and exhibits exploration-cost awareness usually associated with on-policy algorithms.
Takeaways & Limitations
The paper presents a lookup-table formulation; applying G-learning where G requires approximation and determining the optimal β schedule remain future work.
Abstract
from arXiv · showhide
Model-free reinforcement learning algorithms, such as Q-learning, perform poorly in the early stages of learning in noisy environments, because much effort is spent unlearning biased estimates of the state-action value function. The bias results from selecting, among several noisy estimates, the apparent optimum, which may actually be suboptimal. We propose G-learning, a new off-policy learning algorithm that regularizes the value estimates by penalizing deterministic policies in the beginning of the learning process. We show that this method reduces the bias of the value-function estimation, leading to faster convergence to the optimal value and the optimal policy. Moreover, G-learning enables the natural incorporation of prior domain knowledge, when available. The stochastic nature of G-learning also makes it avoid some exploration costs, a property usually attributed only to on-policy algorithms. We illustrate these ideas in several examples, where G-learning results in significant improvements of the convergence rate and the cost of the learning process.
1 INTRODUCTION
Noisy reinforcement learning can make Q-learning commit to biased, suboptimal estimates early, motivating G-learning’s soft, information-theoretic regularization. The method reduces estimation bias, supports prior knowledge, and can lower exploration costs.
- Motivation: Q-learning’s noisy min or max selection can produce biased estimates, wrong early decisions, and costly unlearning of suboptimal behavior.The problem is analogous to the winner’s curse: selecting an apparent optimum among noisy estimates may select a suboptimal action.
- G-learning: G-learning is an off-policy method that regularizes model-free state-action value estimates with an information-theoretic penalty.The penalty discourages deterministic policies that diverge from a simple stochastic prior.
- G-learning: Early learning favors randomized policies, then shifts toward deterministic exploitation as samples accumulate through a scheduled penalty coefficient.The paper suggests that a simple linear schedule can perform well.
- Results: G-learning reduces value-estimation bias and improves convergence in the paper’s examples.The authors link bias reduction to learning performance and report significant improvement from the scheduled method.
- Results: G-learning with ϵ-greedy exploration chooses a less costly exploration policy, exhibiting an on-policy-like property usually associated with SARSA-style algorithms.This exploration-cost advantage is illustrated in the cliff domain.
2 LEARNING IN NOISY ENVIRONMENTS
The section explains why noisy model-free Q-learning can learn slowly: hard min selection creates biased value estimates and premature policy commitment. It analyzes when policy errors matter and motivates soft updates that represent uncertainty explicitly.
- Setting: Model-free learning estimates value functions from environmental samples because transition and cost distributions are unknown.Q-learning updates estimates from observed states, actions, costs, and successor states.
- Bias and early commitment: Noise in costs or successor states makes Q-learning’s min estimator negatively biased, slowing learning.The resulting cost-to-go can appear lower than its true value.
- Bias and early commitment: Jensen’s inequality explains the bias because the concave min operator is applied to noisy Q estimates.Equality holds only when the estimates already reveal the optimal policy with probability 1.
- Policy suboptimality: The greedy policy is most suboptimal when the action-value gap is comparable to estimation noise.Large gaps are usually identified correctly, while confusing nearly tied actions has limited value impact.
- Policy suboptimality: Bias can propagate between states, making even large-gap suboptimal actions appear optimal when they lead into highly biased regions.A near-greedy exploration policy can accelerate bias reduction through a self-correcting variance loop.
- Soft updates: Soft updates address early commitment by penalizing deterministic policies and explicitly representing uncertainty during learning.The penalty is applied early, while the eventual output can remain the deterministic greedy policy.
3 LEARNING WITH SOFT UPDATES
G-learning augments discounted cost with an information penalty relative to a stochastic prior, producing soft policies and a free-energy value function. The resulting off-policy updates converge under standard stochastic-approximation conditions and can incorporate prior knowledge.
- Free energy: The information cost penalizes deviations of the learned policy from a stochastic prior policy.Its expected per-state penalty is the KL divergence from the prior.
- Free energy: Adding discounted information cost to discounted external cost defines the free-energy objective, weighted by β.β controls the relative importance of the two costs and grows during learning.
- Soft policy: The soft policy approaches the prior when β is small and the deterministic greedy policy for G when β is large.The policy is the soft-min operator applied to G, with inverse-temperature β.
- G-learning: G-learning is an off-policy temporal-difference algorithm that learns the optimal free-energy function from environmental interaction.Its fixed-point formulation yields the update rule used by the algorithm.
- Role of the prior: The prior policy can encode domain knowledge, including softer preferences that assign lower probability to actions that are usually harmful.Incorrect prior information can hinder learning, so the prior should represent available knowledge without adding unsupported assumptions.
- Scope: The paper presents G-learning with a lookup-table representation, while function-approximation benefits remain preliminary.Applying the method to more challenging approximation-based domains and finding an optimal β schedule are left for future work.
- Convergence: The update operator is contractive, and G-learning converges to the optimal G with probability 1 under the stated learning-rate, visitation, and bounded-noise conditions.The convergence argument relies on the contraction lemma and stochastic iteration results.
4 SCHEDULING β
G-learning schedules β to move from the prior-policy behavior of Qρ-learning toward the optimal-policy behavior of Q-learning, reducing bias as learning progresses.
- With β = ∞, G-learning becomes Q-learning, while β = 0 yields Qρ-learning and convergence to Qρ.
- Qρ-learning is initially advantageous because it avoids committing to a deterministic policy from noisy Q estimates, whereas Q-learning becomes preferable later.
- A suitable β schedule can transition smoothly from Qρ-learning to Q-learning, combining their early and late advantages.
- Continuity and monotonicity of the update in β imply that some β can make the update unbiased.
- The existence proof for an unbiased schedule is non-constructive and allows β to depend on iteration and potentially the current state.
- β should increase as samples accumulate; experiments found a simple linear schedule effective, while Bellman-error-based scheduling produced similar results.
- The linear schedule coefficient can be tuned through brief preliminary runs, and tuning on several related domains can improve learning across the domain class.
5 RELATED WORK
Related work addresses noisy value estimation, exploration, information penalties, and gap-increasing updates; G-learning distinguishes itself by using soft-greedy policies directly in TD updates.
- Double-Q-learning and other Q-learning modifications address statistical bias caused by domain noise or function approximation.
- Advantage learning can accelerate learning in some noisy environments, while gap-increasing operators are motivated by the role of action gaps in bias generation.
- Information-theoretic reinforcement-learning methods use free energy or related quantities, and KL penalties have also been used to encourage curiosity in known environments.
- G-learning is presented as the first TD-learning algorithm to explicitly use soft-greedy policies in its updates.
- Unlike the related approach that constrains divergence from the previous empirical policy, G-learning measures divergence from a fixed prior and increases the permitted divergence through β.
- G-learning keeps reliable state-action values through a separate β parameter, whereas Ψ-learning penalizes actions judged suboptimal and may require unlearning early errors.
6 EXAMPLES
Across gridworld and cliff-walking examples, G-learning improves learning under noisy costs and exploration, combining faster value convergence with lower exploration costs.
- 6.1 GRIDWORLD: The gridworld uses an 8 × 8 board with walls, a goal state, stochastic movement, and three cost-noise conditions.
- 6 EXAMPLES: The experiments compare G-learning with Q-learning, Double-Q-learning, Ψ-learning, TC-learning, Qρ-learning, and Expected-SARSA across gridworld settings.
- 6.1 GRIDWORLD: The evaluations average three measures over N = 100 runs for 250,000 iterations: empirical bias, mean absolute error, and increase in cost-to-go.
- 6.1 GRIDWORLD: In noisy-cost gridworlds, G-learning dominates competing algorithms on all three measures, with statistically significant results.
- 6.1 GRIDWORLD: Qρ-learning initially outperforms Q-learning because its prior-directed updates avoid early commitment to noisy deterministic estimates, before later degrading toward suboptimal Qρ.
- 6.1 GRIDWORLD: G-learning combines Qρ-learning’s early advantage with Q-learning’s later convergence advantage by increasing β as estimates improve.
- 6.1 GRIDWORLD: G-learning reaches zero average Bellman error faster than competing methods even while β increases toward the Q-learning limit.
- 6.2 CLIFF WALKING: In cliff walking, G-learning’s update policy favors safer trajectories early because avoiding the fall requires high information cost near the cliff.
7 CONCLUSIONS
G-learning mitigates slow early-stage Q-learning in noisy environments by addressing bias from hard policy optimization. The paper also identifies extensions to more challenging model-free settings and further study of the β schedule as future work.
- G-learning mitigates slow early-stage Q-learning in noisy environments caused by bias from hard policy optimization.
- In the cliff domain, G-learning’s exploration-aware policy chooses less costly exploration and exhibits on-policy-like properties despite being off-policy.
- The approach may extend to TD(λ), function approximation, experience replay, and actor-critic methods.
- Applying G-learning to more challenging domains requiring G-function approximation and determining the optimal β schedule remain open questions.
A CONVERGENCE OF G-LEARNING
The section establishes that G-learning converges almost surely to the optimal G∗ under its update rule, using contraction properties and stochastic-iteration results.
- The convergence argument relies on a lemma concerning contraction in the supremum norm and on zt having expectation 0.
- The operator B∗[G](s,a) is a contraction in the supremum norm.
- For any policy π, the corresponding operator is also a contraction under the supremum norm.
- The update equation can be expressed as a stochastic iteration equation involving the random variable zt.
- Under the contraction property, infinite visits to every state-action pair, and bounded |zt|, Gt converges to the optimal G∗ with probability 1.