PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning with Perturbed Rewards

Jingkang Wang, Yang Liu, Bo Li

arXiv:1810.01032v4cs.LGcs.CRcs.CVstat.ML

TL;DR

Noisy or corrupted rewards make reinforcement-learning feedback unreliable and can undermine learning in real-world and adversarial settings. The paper models this corruption with a confusion matrix, estimates it when needed, and replaces observed rewards with unbiased surrogates. The resulting framework provides convergence and sample-complexity guarantees and performs robustly in experiments, including substantial improvements for PPO under noisy Atari-game rewards.

  • Problem

    Noisy rewards from sensors, adversarial perturbations, or other biased corruption create a reinforcement-learning problem where observed feedback may not reflect true rewards.

  • Method

    The framework models perturbed rewards with a confusion matrix, estimates unknown matrices in deterministic-reward settings, and defines unbiased surrogate rewards for existing RL algorithms.

  • Results

    The method achieves convergence guarantees and finite sample-complexity bounds, while experiments show robust performance under noisy rewards across OpenAI Gym and Atari settings.

  • Takeaways & Limitations

    The approach supports learning from perturbed rewards without requiring knowledge of the true reward distribution or adversarial strategy, within the confusion-matrix noise model.

  • Takeaways & Limitations

    Surrogate rewards remain unbiased but have higher variance than true rewards, which can delay convergence; the model assumes corruption follows an invertible confusion matrix.

Abstract

from arXiv · show

Recent studies have shown that reinforcement learning (RL) models are vulnerable in various noisy scenarios. For instance, the observed reward channel is often subject to noise in practice (e.g., when rewards are collected through sensors), and is therefore not credible. In addition, for applications such as robotics, a deep reinforcement learning (DRL) algorithm can be manipulated to produce arbitrary errors by receiving corrupted rewards. In this paper, we consider noisy RL problems with perturbed rewards, which can be approximated with a confusion matrix. We develop a robust RL framework that enables agents to learn in noisy environments where only perturbed rewards are observed. Our solution framework builds on existing RL/DRL algorithms and firstly addresses the biased noisy reward setting without any assumptions on the true distribution (e.g., zero-mean Gaussian noise as made in previous works). The core ideas of our solution include estimating a reward confusion matrix and defining a set of unbiased surrogate rewards. We prove the convergence and sample complexity of our approach. Extensive experiments on different DRL platforms show that trained policies based on our estimated surrogate reward can achieve higher expected rewards, and converge faster than existing baselines. For instance, the state-of-the-art PPO algorithm is able to obtain 84.6% and 80.8% improvements on average score for five Atari games, with error rates as 10% and 30% respectively.

Introduction

The paper addresses reinforcement learning with biased, perturbed rewards by modeling corruption through a confusion matrix and constructing unbiased surrogate rewards. Its analysis provides convergence and sample-complexity guarantees, while experiments report robust performance under substantial noise.

  • Motivation: Reward design is critical for real-world reinforcement learning, but sensors, human feedback, and adversarial perturbations can make observed rewards unreliable.The paper identifies inherent, application-specific, and adversarial sources of reward or observation noise.
  • Problem setting: The proposed setting models perturbed rewards as learnable outputs generated by a confusion matrix, without assuming an arbitrary noise model or a known true reward distribution.The model includes stochastic reward flipping and can represent adversarial manipulation such as reversing reward values.
  • Method: The framework estimates reward confusion matrices and defines unbiased surrogate rewards so agents can learn despite observing only biased, perturbed rewards.The approach targets biased noise rather than requiring an unbiased noise distribution.
  • Theory: The analysis establishes convergence and finite sample complexity for reward-robust reinforcement learning, using Q-Learning as an example.The contribution is presented as a theoretical extension of unbiased estimation ideas to reinforcement learning.
  • Experiments: OpenAI Gym experiments show comparable performance to policies trained with true rewards, with higher cumulative reward in some settings.The authors conjecture that inserted noise combined with unbiased reward correction can provide additional exploration in certain settings.

Problem Formulation and Preliminaries

The paper formulates reinforcement learning with perturbed rewards as an MDP in which agents observe corrupted rather than true reward values. Corruption is represented by a perturbation function or confusion matrix, and the framework can estimate that matrix when rewards are deterministic for each state-action pair.

  • Problem Formulation and Preliminaries: The perturbed-reward problem extends an MDP with an observed reward space and a corruption mechanism while retaining states, actions, transitions, and discounting.The agent interacts with an unknown environment and seeks a policy maximizing cumulative reward.
  • Reinforcement Learning: The Noise-Free Setting: In the noise-free formulation, an agent selects actions from states, receives rewards, transitions according to an unknown kernel, and learns an optimal policy.The MDP is represented as M = ⟨S, A, R, P, γ⟩.
  • Reinforcement Learning: The Noise-Free Setting: The Q-function represents expected cumulative reward for taking an action in a state and then following a policy.This value function is the standard object learned by many reinforcement-learning algorithms.
  • Perturbed Reward in RL: With perturbed rewards, the agent observes ˜r_t instead of the true reward r_t after acting.The primary presentation considers finite reward sets, with continuous settings handled through discretization.
  • Perturbed Reward in RL: For binary rewards, perturbation is described by two error rates measuring flips from positive to negative and negative to positive rewards.These rates define state-independent flipping noise in the binary setting.
  • Perturbed Reward in RL: For M reward outcomes, a confusion-matrix entry c_j,k gives the probability of observing R_k when the true reward is R_j.The perturbation function maps states and true rewards to observed rewards.
  • Perturbed Reward in RL: The framework also estimates unknown confusion matrices when each state-action pair has a deterministic reward, rather than assuming the noise rates are known.This differs from many supervised-learning treatments that assume the noise structure is given.

Learning with Perturbed Rewards

The framework replaces perturbed rewards with unbiased surrogate rewards, enabling existing RL algorithms to learn despite biased reward noise. It establishes convergence and sample-complexity guarantees, while experiments and analysis expose the variance and quantization trade-offs of the approach.

  • Unbiased surrogate rewards: Known reward confusion matrices define surrogate rewards whose expectation equals the true reward.The binary and multi-outcome constructions require an invertible confusion matrix in the multi-outcome case.
  • Unbiased surrogate rewards: Continuous rewards are discretized into intervals, trading smaller quantization error against a larger confusion matrix.Increasing the number of intervals reduces quantization error but makes confusion-matrix estimation more demanding.
  • Convergence and sample complexity: Q-learning with surrogate rewards converges with probability one to the optimal policy despite noise in observed rewards.The convergence result applies to finite MDPs under the stated conditions for Q-learning with surrogate rewards.
  • Convergence and sample complexity: The sample complexity increases by at most O(1/det(C)^2) relative to learning with perfectly observed rewards.The additional factor is the cost of reward noise and becomes larger as the noise level increases.
  • Variance and robustness trade-offs: Surrogate rewards are unbiased but have higher variance, which can delay convergence and become unbounded as binary error rates approach one.The method also permits a bias-variance trade-off through R_proxy = ηR + (1 −η)R̂.
  • Estimated confusion matrices: The generic Reward Robust RL algorithm can incorporate existing RL algorithms by replacing observed rewards with estimated surrogate rewards.The estimated confusion matrices are updated from historical observations using predicted true rewards and observed rewards.

Experimental Results

Experiments across classic-control and Atari environments test robust RL under symmetric and asymmetric perturbed rewards. Surrogate rewards generally restore reliable learning, with faster convergence or stronger performance in several settings.

  • Experimental Setup: The evaluation covers CartPole, Pendulum, and seven Atari 2600 games using multiple RL algorithms and reward types.The tested rewards include unary, binary, multivariate, and continuous rewards.
  • Experimental Setup: Experiments vary symmetric and asymmetric noise, including rand-one and rand-all perturbations with different noise levels.Noise magnitude is measured by the confusion-matrix weight ω.
  • CartPole: With increasing CartPole noise rates from 0.1 to 0.9, noisy-reward models converge more slowly, while DQN and DDQN with surrogate rewards reach the best score of 200.The estimated surrogate rewards adapt multiple underlying algorithms to noisy settings without assuming the true reward distribution.
  • CartPole: In slight-noise CartPole settings, surrogate rewards can converge faster than true rewards, which the authors conjecture reflects implicit exploration from adding noise and removing bias.The same passage connects this observation to cases where estimated confusion matrices outperform known matrices.
  • Pendulum: Surrogate rewards support strong Pendulum performance for DDPG and NAF under different noise amounts, correcting biases over the long term even at ω = 0.7.Pendulum uses discretized continuous rewards and multi-outcome surrogate estimation.
  • Variance Reduction: Variance reduction alone can produce large regrets, but combining it with surrogate rewards improves convergence or performance in multiple cases, especially at high noise rates.The comparison uses sample-mean variance reduction with sequence length 100.

Conclusions

The paper proposes a robust RL framework for biased noisy rewards and supports it with theoretical guarantees and extensive experiments.

  • The framework addresses biased noisy rewards without assuming knowledge of the true reward distribution.
  • Convergence guarantees and finite sample complexity are provided for Q-Learning and its variants using estimated surrogate rewards.
  • Experiments on OpenAI Gym show that surrogate rewards can rescue models from misleading rewards at high noise rates.

A Proofs

The proofs establish that confusion-matrix-based surrogate rewards are unbiased and that Q-Learning can converge to optimal or near-optimal policies under stated conditions.

  • The surrogate rewards are obtained by solving R = C · ˆR, yielding ˆR = C−1 · R when the confusion matrix is invertible.
  • For every true reward level Ri, the surrogate reward has expectation Ri, establishing unbiasedness.
  • The stochastic-process conditions support convergence of the Q-value error to zero with probability one.
  • The sample-complexity analysis assumes bounded rewards and invertible confusion matrices so that surrogate rewards remain bounded.
  • Phased Q-Learning converges to a near-optimal policy within finite steps when the surrogate rewards are used.
  • With sufficient samples, the value function converges to the optimal one for every state with probability greater than 1 −δ.

B Experimental Setup

The robustness evaluation combines multiple RL algorithms with control and Atari environments under symmetric and asymmetric reward noise.

  • Experiments use OpenAI baselines and keras-rl with OpenAI Gym environments.
  • The evaluation includes Q-Learning, CEM, Deep SARSA, DQN, DDQN, and DDPG among other state-of-the-art algorithms.
  • Noise experiments include symmetric corruption and asymmetric rand-one and rand-all perturbation schemes.
  • Noise magnitude is parameterized as C = (1 −ω) · I + ω · N, where ω controls the noise weight.

Perturbed-Reward MDP Example

A finite MDP example tests robust reward Q-Learning under symmetric, asymmetric, and time-varying perturbations generated by a reward confusion matrix.

  • The example gives reward r+ = 1 upon reaching state 5 and reward r− = 0 otherwise.
  • Time-varying noise changes across four training intervals, with e− and e+ taking different values at each stage.
  • Algorithm 1 remains robust to time-variant noise by dynamically adjusting the estimated confusion matrix after distribution changes.
  • A maximum memory size restricts learning to recent noisy-reward observations during time-variant experiments.

Training Details

The experiments use standard neural-network configurations for CartPole and Atari, while discretization enables reward-confusion estimation in continuous-state tasks. The framework also supports plugging confusion-matrix estimation into existing RL algorithms.

  • CartPole: CartPole uses a five-layer fully connected Keras-RL network with three 16-unit hidden layers and rectified nonlinearities.The output layer is linear.
  • Atari: Atari uses 84 × 84 × 4 stacked grayscale frames and a convolutional network with three convolutional and two fully connected layers.The convolutional kernels are 8 × 8, 4 × 4, and 3 × 3 with the stated strides and filter counts.
  • State discretization: Continuous-state MDPs are discretized to balance quantization error and estimation complexity, although estimation is highly robust to the quantization level.The procedure is similar to preprocessing for continuous rewards.
  • State discretization: CartPole uses 80 discretized states, while inverted Pendulum uses 16,000 discretized states for collecting noisy rewards by state-action pair.The state dimensions are 8 × 10 for CartPole and 20 × 20 × 40 for Pendulum.
  • Algorithm integration: Reward Robust Q-Learning estimates the confusion matrix dynamically and computes surrogate rewards, with the same steps extendable to other RL algorithms.The framework inserts confusion-matrix estimation and surrogate-reward computation into existing algorithms.

State-Dependent Perturbed Reward

The framework extends to state-dependent reward noise by using state-specific confusion matrices, while its algorithm estimates corruption, constructs surrogate rewards, and retains theoretical guarantees under invertibility assumptions.

  • State-dependent noise: State-dependent perturbed rewards are modeled with a confusion function that allows different states to have different noise distributions and confusion matrices.The framework remains applicable beyond state-independent noise.
  • Surrogate reward: The surrogate reward is designed to be unbiased, satisfying E˜r|r,st[ˆr(st, at, st+1)] = r(st, at, st+1).This relation connects the expected surrogate reward to the true reward.
  • Algorithm: Reward Robust Q-Learning collects noisy rewards, uses majority voting to predict true rewards, re-estimates the confusion matrix, and updates Q-values with surrogate rewards.The update combines the surrogate reward with the discounted next-state value.
  • Guarantees: The theoretical analysis revises the earlier results for state-dependent confusion matrices and gives an upper bound when each matrix Cs is invertible.The bound depends on det(Cs) and an appropriate choice of m.
  • Guarantees: Under bounded rewards and invertible confusion matrices, the surrogate reward variance is bounded, and the algorithm returns an approximately optimal policy with high probability.The policy guarantee is expressed as |Vπ(s) − V∗(s)| ≤ ϵ with probability at least 1 − δ.
  • State-dependent noise: For state-dependent noise, each confusion-matrix entry represents the probability of generating a perturbed reward outcome from a true reward at state s.The estimation step is modified accordingly.

Experimental Results

Experiments on CartPole evaluate robust RL when noise rates are unknown, using discretized observations and η = 1. The proposed estimators rapidly recover approximate confusion matrices and remain robust across noise conditions.

  • CartPole setup: CartPole experiments test robust reward algorithms while keeping the noise rates unknown to the agents during exploration.Observations such as velocity and angle are discretized to construct the state set.
  • CartPole setup: The experiments set η = 1.0 for the surrogate-reward configurations.The implementation follows the reward-robust algorithm after discretizing observations.
  • Results: The proposed estimators successfully obtain approximate confusion matrices and produce robust learning in environments with unknown noise.The results are reported from learning curves comparing multiple algorithms and reward types.
  • Results: Confusion-matrix estimation converges very fast across the tested CartPole settings.The convergence analysis compares estimated error rates with their ground truths and tracks normalized matrix differences.
  • Results: The implementation assumes no additional knowledge of the noise or the true reward distribution.This supports evaluation under unknown reward corruption.

D Supplementary Experimental Results

Supplementary experiments examine confusion-matrix estimation and surrogate rewards across CartPole, Pendulum, and Atari settings. They vary noise rates, reward-processing choices, algorithms, and repeated random seeds.

  • CartPole: CartPole estimation plots compare ground-truth and estimated error rates and report normalized absolute confusion-matrix differences.The curves cover error rates from 0.1 to 0.9.
  • CartPole: CartPole learning curves compare true, noisy, estimated surrogate, sample-mean noisy, and sample-mean estimated surrogate rewards across noise rates 0.1, 0.3, 0.7, and 0.9.Each experiment is repeated 10 times with percentile areas and highlighted means.
  • CartPole: CartPole score comparisons evaluate sample-mean rewards with variance reduction, surrogate rewards, and their combination when confusion matrices are unknown.Each experiment is repeated three times with different random seeds.
  • Pendulum: Pendulum experiments use DDPG and NAF with true, noisy, and surrogate rewards under both symmetric and asymmetric noise.Noise rates range from 0.1 to 0.9, and each setting is repeated six times.
  • Atari: PPO learning curves on seven Atari games compare true, noisy, and surrogate rewards.The figure reports complete learning curves for these reward conditions.
  • Atari: Atari visualizations vary noise rates from 0.1 to 0.9 in increments of 0.1 and generally omit true-reward curves except for Pong-v4.The omitted curves are removed for visual clarity.
Loading 1810.01032v4…