summaries: The paper aims at studying the setting of perturbed rewards in a deep RL setting. Studying the effect of noise in the reward function is interesting. The paper is quite well-written. However the paper studies a rather simple setting, the limitations could be discussed more clearly and there are one or two elements unclear (see below).

summaries: The authors present work that shows how to deal with noise in reward signals by creating a surrogate reward signal. The work develops a number of results including: showing how the surrogate reward is equal in expectation to the true reward signal, how this doesn't affect the fixed point of the Bellman equation, how to deal with finite and continuous rewards and how the convergence time is affected for different levels of noise. They demonstrate the value of this approach with a variety of early and state-of-the-art algorithms on a variety of domains,, and the results are consistent with the claims.

abstractText: Recent studies have shown that reinforcement learning (RL) models can be vulnerable in various scenarios, where noises from different sources could appear. For instance, the observed reward channel is often subject to noise in practice (e.g., when observed rewards are collected through sensors), and thus observed rewards may not be credible. Also, in applications such as robotics, a deep reinforcement learning (DRL) algorithm can be manipulated to produce arbitrary errors. In this paper, we consider noisy RL problems where observed rewards by RL agents are generated with a reward confusion matrix. We call such observed rewards as perturbed rewards. We develop an unbiased reward estimator aided robust RL framework that enables RL agents to learn in noisy environments while observing only perturbed rewards. Our framework draws upon approaches for supervised learning with noisy data. 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 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 67.5% and 46.7% improvements in average on five Atari games, when the error rates are 10% and 30% respectively.

authors:
Alan Joseph Bekker
Jacob Goldberger

title: Training deep neural-networks based on unreliable labels

venue: In ICASSP,

authors:
Alexander Philip Dawid
Allan M Skene

title: Maximum likelihood estimation of observer error-rates using the em algorithm

venue: Applied statistics,

authors:
Tom Everitt
Victoria Krakovna
Laurent Orseau
Shane Legg

title: Reinforcement learning with a corrupted reward channel

venue: In IJCAI,

authors:
Justin Fu
Katie Luo
Sergey Levine

title: Learning robust rewards with adversarial inverse reinforcement learning

authors:
Shixiang Gu
Timothy P. Lillicrap
Ilya Sutskever
Sergey Levine

title: Continuous deep q-learning with model-based acceleration

venue: In ICML,

authors:
Zhaoyuan Gu
Zhenzhong Jia
Howie Choset

title: Adversary a3c for robust reinforcement learning, 2018

authors:
Dylan Hadfield-Menell
Smitha Milli
Pieter Abbeel
Stuart J Russell
Anca Dragan

title: Inverse reward design

authors:
Dan Hendrycks
Mantas Mazeika
Duncan Wilson
Kevin Gimpel

title: Using trusted data to train deep networks on labels corrupted by severe

venue: noise. CoRR,

authors:
Sandy Huang
Nicolas Papernot
Ian Goodfellow
Yan Duan
Pieter Abbeel

title: Adversarial attacks on neural network policies

venue: arXiv preprint arXiv:1702.02284,

title: Deep reinforcement learning doesn’t work yet

authors:
Tommi S. Jaakkola
Michael I. Jordan
Satinder P. Singh

title: Convergence of stochastic iterative dynamic programming algorithms

venue: In NIPS,

title: On the Sample Complexity of Reinforcement Learning

venue: PhD thesis, University of London,

authors:
David R Karger
Sewoong Oh
Devavrat Shah

title: Iterative learning for reliable crowdsourcing systems. In Advances in neural information processing

authors:
Michael J. Kearns
Satinder P. Singh

title: Finite-sample convergence rates for q-learning and indirect algorithms

title: Bias-variance error bounds for temporal difference updates

venue: In COLT, pp

authors:
Michael J. Kearns
Yishay Mansour
Andrew Y. Ng

title: A sparse sampling algorithm for nearoptimal planning in large markov decision processes

authors:
Ashish Khetan
Zachary C. Lipton
Anima Anandkumar

title: Learning from noisy singly-labeled data

authors:
Jernej Kos
Dawn Song

title: Delving into adversarial attacks on deep policies

authors:
Timothy P. Lillicrap
Jonathan J. Hunt
Alexander Pritzel
Nicolas Heess
Tom Erez
Yuval Tassa
David Silver
Daan Wierstra

title: Continuous control with deep reinforcement learning

authors:
Shiau Hong Lim
Huan Xu
Shie Mannor

title: Reinforcement learning in robust markov decision processes

venue: Math. Oper. Res.,

authors:
Yen-Chen Lin
Zhang-Wei Hong
Yuan-Hong Liao
Meng-Li Shih
Ming-Yu Liu
Min Sun

title: Tactics of adversarial attack on deep reinforcement learning agents

authors:
Qiang Liu
Jian Peng
Alexander T Ihler

title: Variational inference for crowdsourcing

venue: In Proc. of NIPS,

authors:
Yang Liu
Mingyan Liu

title: An online learning approach to improving the quality of crowdsourcing

venue: IEEE/ACM Transactions on Networking,

authors:
R. Loftin
B. Peng
J. MacGlashan
M.L. Littman
M.E. Taylor
J. Huang
D.L. Roberts

title: Learning something from nothing: Leveraging implicit human feedback strategies

venue: In The 23rd IEEE International Symposium on Robot and Human Interactive Communication,

authors:
Aditya Menon
Brendan Van Rooyen
Cheng Soon Ong
Bob Williamson

title: Learning from corrupted binary labels via class-probability estimation

venue: In International Conference on Machine Learning,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin A. Riedmiller

title: Playing atari with deep reinforcement learning

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Andrei A Rusu
Joel Veness
Marc G Bellemare
Alex Graves
Martin Riedmiller
Andreas K Fidjeland
Georg Ostrovski

title: Human-level control through deep reinforcement learning

authors:
Nagarajan Natarajan
Inderjit S Dhillon
Pradeep K Ravikumar
Ambuj Tewari

title: Learning with noisy labels

authors:
Lerrel Pinto
James Davidson
Rahul Sukthankar
Abhinav Gupta

title: Robust adversarial reinforcement learning

authors:
Aravind Rajeswaran
Sarvjeet Ghotra
Sergey Levine
Balaraman Ravindran

title: Epopt: Learning robust neural network policies using model ensembles

authors:
Joshua Romoff
Alexandre Piché
Peter Henderson
Vincent François-Lavet
Joelle Pineau

title: Reward estimation for variance reduction in deep reinforcement learning

authors:
Aurko Roy
Huan Xu
Sebastian Pokutta

title: Reinforcement learning under model mismatch

authors:
John Schulman
Filip Wolski
Prafulla Dhariwal
Alec Radford
Oleg Klimov

title: Proximal policy optimization algorithms

title: A reinforcement learning method for maximizing undiscounted rewards

title: A rate of convergence for mixture proportion estimation, with application to learning from noisy labels

venue: In AISTATS,

authors:
Clayton Scott
Gilles Blanchard
Gregory Handy
Sara Pozzi
Marek Flaska

title: Classification with asymmetric label noise: Consistency and maximal denoising

title: Mean-variance tradeoffs in an undiscounted MDP

venue: Operations Research,

authors:
Sainbayar Sukhbaatar
Rob Fergus

title: Learning from noisy labels with deep neural networks

venue: arXiv preprint arXiv:1406.2080,

authors:
Richard S. Sutton
Andrew G. Barto

title: Reinforcement learning - an introduction. Adaptive computation and machine learning

authors:
Istvan Szita
András Lörincz

title: Learning tetris using the noisy cross-entropy method

venue: Neural Computation,

authors:
Yee Whye Teh
Victor Bapst
Wojciech M. Czarnecki
John Quan
James Kirkpatrick
Raia Hadsell
Nicolas Heess
Razvan Pascanu

title: Distral: Robust multitask reinforcement learning

authors:
Andrea Lockerd Thomaz
Cynthia Breazeal

title: Reinforcement learning with human teachers: Evidence of feedback and guidance with implications for learning

title: Asynchronous stochastic approximation and q-learning

venue: Machine Learning,

authors:
Hado van Hasselt
Arthur Guez
David Silver

title: Deep reinforcement learning with double qlearning

venue: In AAAI,

authors:
Brendan van Rooyen
Robert C Williamson

title: Learning in the presence of corruption

venue: arXiv preprint arXiv:1504.00091,

authors:
Ziyu Wang
Tom Schaul
Matteo Hessel
Hado van Hasselt
Marc Lanctot
Nando de Freitas

title: Dueling network architectures for deep reinforcement learning

title: Learning from Delayed Rewards

venue: PhD thesis, King’s College,

authors:
Yuchen Zhang
Xi Chen
Denny Zhou
Michael I Jordan

title: Spectral methods meet em: A provably optimal algorithm for crowdsourcing

venue: Proof of Lemma 3. See previous literature (Jaakkola et al.,

title: EXPERIMENTAL SETUP We set up our experiments within the popular OpenAI baselines (Dhariwal et al., 2017) and kerasrl (Plappert, 2016) framework. Specifically, we integrate the algorithms and interact with OpenAI Gym (Brockman et al., 2016) environments

authors: Specially Romoff

heading: 1 INTRODUCTION

text:
Designing a suitable reward function plays a critical role in building reinforcement learning models for real-world applications. Ideally, one would want to customize reward functions to achieve application-specific goals (Hadfield-Menell et al., 2017). In practice, however, it is difficult to design a function that produces credible rewards in the presence of noise. This is because the output from any reward function is subject to multiple kinds of randomness:
• Inherent Noise. For instance, sensors on a robot will be affected by physical conditions such as temperature and lighting, and therefore will report back noisy observed rewards.
• Application-Specific Noise. In machine teaching tasks (Thomaz et al., 2006; Loftin et al., 2014), when an RL agent receives feedback/instructions from people, different human instructors might provide drastically different feedback due to their personal styles and capabilities. This way the RL agent (machine) will obtain reward with bias.
• Adversarial Noise. Adversarial perturbation has been widely explored in different learning tasks and shows strong attack power against different machine learning models. For instance, Huang et al. (2017) has shown that by adding adversarial perturbation to each frame of the game, they can mislead RL policies arbitrarily.
Assuming an arbitrary noise model makes solving this noisy RL problem extremely challenging. Instead, we focus on a specific noisy reward model which we call perturbed rewards, where the observed rewards by RL agents are generated according to a reward confusion matrix. This is not a very restrictive setting to start with, even considering that the noise could be adversarial: Given that arbitrary pixel value manipulation attack in RL is not very practical, adversaries in the real-world have high incentives to inject adversarial perturbation to the reward value by slightly modifying it. For instance, adversaries can manipulate sensors via reversing the reward value.
In this paper, we develop an unbiased reward estimator aided robust framework that enables an RL agent to learn in a noisy environment with observing only perturbed rewards. Our solution framework builds on existing reinforcement learning algorithms, including the recently developed DRL ones (Q-Learning (Watkins, 1989; Watkins & Dayan, 1992), Cross-Entropy Method (CEM) (Szita & Lörincz, 2006), Deep SARSA (Sutton & Barto, 1998), Deep Q-Network (DQN) (Mnih et al., 2013; 2015; van Hasselt et al., 2016), Dueling DQN (DDQN) (Wang et al., 2016), Deep Deterministic Policy Gradient (DDPG) (Lillicrap et al., 2015), Continuous DQN (NAF) (Gu et al., 2016) and Proximal Policy Optimization (PPO) (Schulman et al., 2017) algorithms).
The main challenge is that the observed rewards are likely to be biased, and in RL or DRL the accumulated errors could amplify the reward estimation error over time. We do not require any assumption on knowing the true distribution of reward or adversarial strategies, other than the fact that the generation of noises follow an unknown reward confusion matrix. Instead, we address the issue of estimating the reward confusion matrices by proposing an efficient and flexible estimation module. Everitt et al. (2017) provided preliminary studies for the noisy reward problem and gave some general negative results. The authors proved a No Free Lunch theorem, which is, without any assumption about what the reward corruption is, all agents can be misled. Our results do not contradict with the results therein, as we consider a specific noise generation model (that leads to a set of perturbed rewards). We analyze the convergence and sample complexity for the policy trained based on our proposed method using surrogate rewards in RL, using Q-Learning as an example.
We conduct extensive experiments on OpenAI Gym (Brockman et al., 2016) (AirRaid, Alien, Carnival, MsPacman, Pong, Phoenix, Seaquest) and show that the proposed reward robust RL method achieves comparable performance with the policy trained using the true rewards. In some cases, our method even achieves higher cumulative reward - this is surprising to us at first, but we conjecture that the inserted noise together with our noisy-removal unbiased estimator adds another layer of exploration, which proves to be beneficial in some settings. This merits a future study.
Our contributions are summarized as follows: (1) We adapt and generalize the idea of defining a simple but effective unbiased estimator for true rewards using observed and perturbed rewards to the reinforcement learning setting. The proposed estimator helps guarantee the convergence to the optimal policy even when the RL agents only have noisy observations of the rewards. (2) We analyze the convergence to the optimal policy and finite sample complexity of our reward robust RL methods, using Q-Learning as the running example. (3) Extensive experiments on OpenAI Gym show that our proposed algorithms perform robustly even at high noise rates.

heading: 1.1 RELATED WORK

text:
Robust Reinforcement Learning It is known that RL algorithms are vulnerable to noisy environments (Irpan, 2018). Recent studies (Huang et al., 2017; Kos & Song, 2017; Lin et al., 2017) show that learned RL policies can be easily misled with small perturbations in observations. The presence of noise is very common in real-world environments, especially in robotics-relevant applications. Consequently, robust (adversarial) reinforcement learning (RRL/RARL) algorithms have been widely studied, aiming to train a robust policy which is capable of withstanding perturbed observations (Teh et al., 2017; Pinto et al., 2017; Gu et al., 2018) or transferring to unseen environments (Rajeswaran et al., 2016; Fu et al., 2017). However, these robust RL algorithms mainly focus on noisy vision observations, instead of the observed rewards. A couple of recent works (Lim et al., 2016; Roy et al., 2017) have also looked into a rather parallel question of training robust RL algorithms with uncertainty in models.
Learning with Noisy Data Learning appropriately with biased data has received quite a bit of attention in recent machine learning studies Natarajan et al. (2013); Scott et al. (2013); Scott (2015); Sukhbaatar & Fergus (2014); van Rooyen & Williamson (2015); Menon et al. (2015). The idea of above line of works is to define unbiased surrogate loss function to recover the true loss using the knowledge of the noises. We adapt these approaches to reinforcement learning. Though intuitively the idea should apply in our RL settings, our work is the first one to formally establish this extension both theoretically and empirically. Our quantitative understandings will provide practical insights when implementing reinforcement learning algorithms in noisy environments.

heading: 2 PROBLEM FORMULATION AND PRELIMINARIES

text: In this section, we define our problem of learning from perturbed rewards in reinforcement learning. Throughout this paper, we will use perturbed reward and noisy reward interchangeably, as each time step of our sequential decision making setting is similar to the “learning with noisy data” setting in supervised learning (Natarajan et al., 2013; Scott et al., 2013; Scott, 2015; Sukhbaatar & Fergus, 2014). In what follows, we formulate our Markov Decision Process (MDP) problem and the reinforcement learning (RL) problem with perturbed (noisy) rewards.

heading: 2.1 REINFORCEMENT LEARNING: THE NOISE-FREE SETTING

text:
Our RL agent interacts with an unknown environment and attempts to maximize the total of his collected reward. The environment is formalized as a Markov Decision Process (MDP), denoting as M = 〈S,A,R,P, γ〉. At each time t, the agent in state st ∈ S takes an action at ∈ A, which returns a reward r(st, at, st+1) ∈ R (which we will also shorthand as rt), and leads to the next state st+1 ∈ S according to a transition probability kernel P , which encodes the probability Pa(st, st+1). Commonly P is unknown to the agent. The agent’s goal is to learn the optimal policy, a conditional distribution π(a|s) that maximizes the state’s value function. The value function calculates the cumulative reward the agent is expected to receive given he would follow the current policy π after observing the current state st: V π(s) = Eπ [∑∞ k=1 γ krt+k | st = s ] , where 0 ≤ γ ≤ 11 is a discount factor. Intuitively, the agent evaluates how preferable each state is given the current policy. From the Bellman Equation, the optimal value function is given by V ∗(s) = maxa∈A ∑ st+1∈S Pa(st, st+1) [rt + γV
∗(st+1)] . It is a standard practice for RL algorithms to learn a state-action value function, also called the Q-function. Q-function denotes the expected cumulative reward if agent chooses a in the current state and follows π thereafter: Qπ(s, a) = Eπ [r(st, at, st+1) + γV π(st+1) | st = s, at = a] .

heading: 2.2 PERTURBED REWARD IN RL

text:
In many practical settings, our RL agent does not observe the reward feedback perfectly. We consider the following MDP with perturbed reward, denoting as M̃ = 〈S,A,R, C,P, γ〉2: instead of observing rt ∈ R at each time t directly (following his action), our RL agent only observes a perturbed version of rt, denoting as r̃t ∈ R̃. For most of our presentations, we focus on the cases whereR, R̃ are finite sets; but our results generalize to the continuous reward settings.
The generation of r̃ follows a certain function C : S×R → R̃. To let our presentation stay focused, we consider the following simple state-independent3 flipping error rates model: if the rewards are binary (consider r+ and r−), r̃(st, at, st+1) (r̃t) can be characterized by the following noise rate parameters e+, e−: e+ = P(r̃(st, at, st+1) = r−|r(st, at, st+1) = r+), e− = P(r̃(st, at, st+1) = r+|r(st, at, st+1) = r−). When the signal levels are beyond binary, suppose there are M outcomes in total, denoting as [R0, R1, · · · , RM−1]. r̃t will be generated according to the following confusion matrix CM×M where each entry cj,k indicates the flipping probability for generating a perturbed outcome: cj,k = P(r̃t = Rk|rt = Rj). Again we’d like to note that we focus on settings with finite reward levels for most of our paper, but we provide discussions in Section 3.1 on how to handle continuous rewards with discretizations.
In the paper, we do not assume knowing the noise rates (i.e., the reward confusion matrices), which is different from the assumption of knowing them as adopted in many supervised learning works Natarajan et al. (2013). Instead we will estimate the confusion matrices (Section 3.3).
1γ = 1 indicates an undiscounted MDP setting (Schwartz, 1993; Sobel, 1994; Kakade, 2003). 2The MDP with perturbed reward can equivalently be defined as a tuple M̃ = 〈S,A,R, R̃,P, γ〉, with the
perturbation function C implicitly defined as the difference betweenR and R̃. 3The case of state-dependent perturbed reward is discussed in Appendix C.3

heading: 3 LEARNING WITH PERTURBED REWARDS

text: In this section, we first introduce an unbiased estimator for binary rewards in our reinforcement learning setting when the error rates are known. This idea is inspired by Natarajan et al. (2013), but we will extend the method to the multi-outcome, as well as the continuous reward settings.

heading: 3.1 UNBIASED ESTIMATOR FOR TRUE REWARD

text:
With the knowledge of noise rates (reward confusion matrices), we are able to establish an unbiased approximation of the true reward in a similar way as done in Natarajan et al. (2013). We will call such a constructed unbiased reward as a surrogate reward. To give an intuition, we start with replicating the results for binary rewardR = {r−, r+} in our RL setting: Lemma 1. Let r be bounded. Then, if we define,
r̂(st, at, st+1) :=
{ (1−e−)·r+−e+·r−
1−e+−e− (r̃(st, at, st+1) = r+)
(1−e+)·r−−e−·r+ 1−e+−e−
(r̃(st, at, st+1) = r−) (1)
we have for any r(st, at, st+1), Er̃|r[r̂(st, at, st+1)] = r(st, at, st+1).
In the standard supervised learning setting, the above property guarantees convergence - as more training data are collected, the empirical surrogate risk converges to its expectation, which is the same as the expectation of the true risk (due to unbiased estimators). This is also the intuition why we would like to replace the reward terms with surrogate rewards in our RL algorithms.
The above idea can be generalized to the multi-outcome setting in a fairly straight-forward way. Define R̂ := [r̂(r̃ = R0), r̂(r̃ = R1), ..., r̂(r̃ = RM−1)], where r̂(r̃ = Rm) denotes the value of the surrogate reward when the observed reward is Rk. Let R = [R0;R1; · · · ;RM−1] be the bounded reward matrix with M values. We have the following results: Lemma 2. Suppose CM×M is invertible. With defining:
R̂ = C−1 ·R. (2) we have for any r(st, at, st+1), Er̃|r[r̂(st, at, st+1)] = r(st, at, st+1).
Continuous reward When the reward signal is continuous, we discretize it into M intervals and view each interval as a reward level, with its value approximated by its middle point. With increasing M , this quantization error can be made arbitrarily small. Our method is then the same as the solution for the multi-outcome setting, except for replacing rewards with discretized ones. Note that the finerdegree quantization we take, the smaller the quantization error - but we would suffer from learning a bigger reward confusion matrix. This is a trade-off question that can be addressed empirically.
So far we have assumed knowing the confusion matrices, but we will address this additional estimation issue in Section 3.3, and present our complete algorithm therein.
3.2 CONVERGENCE AND SAMPLE COMPLEXITY: Q-LEARNING
We now analyze the convergence and sample complexity of our surrogate reward based RL algorithms (with assuming knowing C), taking Q-Learning as an example. Convergence guarantee First, the convergence guarantee is stated in the following theorem: Theorem 1. Given a finite MDP, denoting as M̂ = 〈S,A, R̂,P, γ〉, the Q-learning algorithm with surrogate rewards, given by the update rule,
Qt+1(st, at) = (1− αt)Q(st, at) + αt [ r̂t + γmax
b∈A Q(st+1, b)
] , (3)
converges w.p.1 to the optimal Q-function as long as ∑ t αt =∞ and ∑ t α 2 t <∞.
Note that the term on the right hand of Eqn. (3) includes surrogate reward r̂ estimated using Eqn. (1) and Eqn. (2). Theorem 1 states that that agents will converge to the optimal policy w.p.1 with replacing the rewards with surrogate rewards, despite of the noises in observing rewards. This result is not surprising - though the surrogate rewards introduce larger variance, we are grateful of their unbiasedness, which grants us the convergence. In other words, the addition of the perturbed reward does not destroy the convergence guarantees of Q-Learning.
Sample complexity To establish our sample complexity results, we first introduce a generative model following previous literature (Kearns & Singh, 1998; 2000; Kearns et al., 1999). This is a practical MDP setting to simplify the analysis. Definition 1. A generative model G(M) for an MDPM is a sampling model which takes a stateaction pair (st, at) as input, and outputs the corresponding reward r(st, at) and the next state st+1 randomly with the probability of Pa(st, st+1), i.e., st+1 ∼ P(·|s, a).
Exact value iteration is impractical if the agents follow the generative models above exactly (Kakade, 2003). Consequently, we introduce a phased Q-Learning which is similar to the ones presented in Kakade (2003); Kearns & Singh (1998) for the convenience of proving our sample complexity results. We briefly outline phased Q-Learning as follows - the complete description (Algorithm 2) can be found in Appendix A. Definition 2. Phased Q-Learning algorithm takesm samples per phase by calling generative model G(M). It uses the collected m samples to estimate the transition probability P and update the estimated value function per phase. Calling generative model G(M̂) means that surrogate rewards are returned and used to update value function per phase.
The sample complexity of Phased Q-Learning is given as follows: Theorem 2. (Upper Bound) Let r ∈ [0, Rmax] be bounded reward, C be an invertible reward confusion matrix with det(C) denoting its determinant. For an appropriate choice ofm, the Phased Q-Learning algorithm calls the generative model G(M̂) O ( |S||A|T
2(1−γ)2det(C)2 log |S||A|T δ
) times in

heading: T epochs, and returns a policy such that for all state s ∈ S , |Vπ(s)− V ∗(s)| ≤ , > 0, w.p.

text:
≥ 1− δ, 0 < δ < 1.
Theorem 2 states that, to guarantee the convergence to the optimal policy, the number of samples needed is no more than O(1/det(C)2) times of the one needed when the RL agent observes true rewards perfectly. This additional constant is the price we pay for the noise presented in our learning environment. When the noise level is high, we expect to see a much higher 1/det(C)2; otherwise when we are in a low-noise regime , Q-Learning can be very efficient with surrogate reward (Kearns & Singh, 2000). Note that Theorem 2 gives the upper bound in discounted MDP setting; for undiscounted setting (γ = 1), the upper bound is at the order of O ( |S||A|T 3 2det(C)2 log |S||A|T δ ) . Lower bound result is omitted due to the lack of space. The idea of constructing MDP in which learning is difficult and the algorithm must make ( |S||A|T
log 1 δ
) calls to G(M̂), is similar to Kakade (2003).
While the surrogate reward guarantees the unbiasedness, we sacrifice the variance at each of our learning steps, and this in turn delays the convergence (as also evidenced in the sample complexity bound). It can be verified that the variance of surrogate reward is bounded when C is invertible, and it is always higher than the variance of true reward. This is summarized in the following theorem: Theorem 3. Let r ∈ [0, Rmax] be bounded reward and confusion matrix C is invertible. Then, the variance of surrogate reward r̂ is bounded as follows: Var(r) ≤ Var(r̂) ≤ M 2
det(C)2 ·R 2 max.
To give an intuition of the bound, when we have binary reward, the variance for surrogate reward bounds as follows: Var(r) ≤ Var(r̂) ≤ 4R 2 max
(1−e+−e−)2 . As e− + e+ → 1, the variance becomes unbounded and the proposed estimator is no longer effective, nor will it be well-defined. In practice, there is a trade-off question between bias and variance by tuning a linear combination of R and R̂, i.e., Rproxy = ηR + (1− η)R̂, and choosing an appropriate η ∈ [0, 1].

heading: 3.3 ESTIMATION OF CONFUSION MATRICES

text:
In Section 3.1 we have assumed the knowledge of reward confusion matrices, in order to compute the surrogate reward. This knowledge is often not available in practice. Estimating these confusion matrices is challenging without knowing any ground truth reward information; but we’d like to note that efficient algorithms have been developed to estimate the confusion matrices in supervised learning settings (Bekker & Goldberger, 2016; Liu & Liu, 2017; Khetan et al., 2017; Hendrycks et al., 2018). The idea in these algorithms is to dynamically refine the error rates based on aggregated rewards. Note this approach is not different from the inference methods in aggregating crowdsourcing
labels, as referred in the literature (Dawid & Skene, 1979; Karger et al., 2011; Liu et al., 2012). We adapt this idea to our reinforcement learning setting, which is detailed as follows.
At each training step, the RL agent collects the noisy reward and the current state-action pair. Then, for each pair in S × A, the agent predicts the true reward based on accumulated historical observations of reward for the corresponding state-action pair via, e.g., averaging (majority voting). Finally, with the predicted true reward and the accuracy (error rate) for each state-action pair, the estimated reward confusion matrices C̃ are given by
c̃i,j =
∑ (s,a)∈S×A# [r̃(s, a) = Rj |r̄(s, a) = Ri]∑
(s,a)∈S×A#[r̄(s, a) = Ri] , (4)
where in above # [·] denotes the number of state-action pair that satisfies the condition [·] in the set of observed rewards R̃(s, a) (see Algorithm 1 and 3); r̄(s, a) and r̃(s, a) denote predicted true rewards (using majority voting) and observed rewards when the state-action pair is (s, a). The above procedure of updating c̃i,j continues indefinitely as more observation arrives.
Algorithm 1 Reward Robust RL (sketch)
Input: M̃, α, β, R̃(s, a) Output: Q(s), π(s, t)
Initialize value function Q(s, a) arbitrarily. while Q is not converged do
Initialize state s ∈ S while s is not terminal do
Choose a from s using policy derived from Q Take action a, observe s′ and noisy reward r̃ if collecting enough r̃ for every S ×A pair then
Get predicted true reward r̄ using majority voting Estimate confusion matrix C̃ based on r̃ and r̄ (Eqn. 4) Obtain surrogate reward ṙ (R̂ = (1− η) ·R + η ·C−1R) Update Q using surrogate reward s← s′
return Q(s) and π(s)
Our final definition of surrogate reward replaces a known reward confusion C in Eqn. (2) with our estimated one C̃. We denote this estimated surrogate reward as ṙ.
We present (Reward Robust RL) in Algorithm 14. Note that the algorithm is rather generic, and we can plug in any exisitng RL algorithm into our reward robust one, with only changes in replacing the rewards with our estimated surrogate rewards.

heading: 4 EXPERIMENTS

text: In this section, reward robust RL is tested in different games, with different noise settings. Due to space limit, more experimental results can be found in Appendix D.

heading: 4.1 EXPERIMENTAL SETUP

text:
Environments and RL Algorithms To fully test the performance under different environments, we evaluate the proposed robust reward RL method on two classic control games (CartPole, Pendulum) and seven Atari 2600 games (AirRaid, Alien, Carnival, MsPacman, Pong, Phoenix, Seaquest), which encompass a large variety of environments, as well as rewards. Specifically, the rewards could be unary (CartPole), binary (most of Atari games), multivariate (Pong) and even continuous (Pendulum). A set of state-of-the-art reinforcement learning algorithms are experimented with while training under different amounts of noise (See Table 3)5. For each game and algorithm, three policies are trained based on different random initialization to decrease the variance.
Reward Post-Processing For each game and RL algorithm, we test the performances for learning with true rewards, learning with noisy rewards and learning with surrogate rewards. Both symmetric and asymmetric noise settings with different noise levels are tested. For symmetric noise, the confusion matrices are symmetric. As for asymmetric noise, two types of random noise are tested: 1) rand-one, each reward level can only be perturbed into another reward; 2) rand-all, each reward could be perturbed to any other reward, via adding a random noise matrix. To measure the amount of noise w.r.t confusion matrices, we define the weight of noise ω in Appendix B.2. The larger ω is, the higher the noise rates are.
4One complete Q-Learning implementation (Algorithm 3) is provided in Appendix C.1. 5The detailed settings are accessible in Appendix B.

heading: 4.2 ROBUSTNESS EVALUATION

text:
CartPole The goal in CartPole is to prevent the pole from falling by controlling the cart’s direction and velocity. The reward is +1 for every step taken, including the termination step. When the cart or pole deviates too much or the episode length is longer than 200, the episode terminates. Due to the unary reward {+1} in CartPole, a corrupted reward −1 is added as the unexpected error (e− = 0). As a result, the reward space R is extended to {+1,−1}. Five algorithms Q-Learning (1992), CEM (2006), SARSA (1998), DQN (2016) and DDQN (2016) are evaluated.
rewards (r̃) and estimated surrogate rewards (ṙ) (η = 1) . Note that reward confusion matrices C are unknown to the agents here. Full results are in Appendix D.2 (Figure 6).
In Figure 1, we show that our estimator successfully produces meaningful surrogate rewards that adapt the underlying RL algorithms to the noisy settings, without any assumption of the true distribution of rewards. With the noise rate increasing (from 0.1 to 0.9), the models with noisy rewards converge slower due to larger biases. However, we observe that the models always converge to the best score 200 with the help of surrogate rewards.
In some circumstances (slight noise - see Figure 6a, 6b, 6c, 6d), the surrogate rewards even lead to faster convergence. This points out an interesting observation: learning with surrogate reward even outperforms the case with observing the true reward. We conjecture that the way of adding noise and then removing the bias introduces implicit exploration. This implies that for settings even with true reward, we might consider manually adding noise and then remove it in expectation.
Pendulum The goal in Pendulum is to keep a frictionless pendulum standing up. Different from the CartPole setting, the rewards in pendulum are continuous: r ∈ (−16.28, 0.0]. The closer the reward is to zero, the better performance the model achieves. Following our extension (see Section 3.1), the (−17, 0] is firstly discretized into 17 intervals: (−17,−16], (−16,−15], · · · , (−1, 0], with its value approximated using its maximum point. After the quantization step, the surrogate rewards can be estimated using multi-outcome extensions presented in Section 3.1.
We experiment two popular algorithms, DDPG (2015) and NAF (2016) in this game. In Figure 2, both algorithms perform well with surrogate rewards under different amounts of noise. In most cases, the biases were corrected in the long-term, even when the amount of noise is extensive (e.g., ω = 0.7). The quantitative scores on CartPole and Pendulum are given in Table 1, where the
rewards (r̃) and surrogate rewards (r̂) (η = 1) . Both symmetric and asymmetric noise are conduced in the experiments. Full results are in Appendix D.2 (Figure 8).
scores are averaged based on the last thirty episodes. The full results (ω > 0.5) can be found in Appendix D.1, so does Table 2. Our reward robust RL method is able to achieve consistently good scores. Atari We validate our algorithm on seven Atari 2600 games using the state-of-the-art algorithm PPO (Schulman et al., 2017). The games are chosen to cover a variety of environments. The rewards in the Atari games are clipped into {−1, 0, 1}. We leave the detailed settings to Appendix B.
and surrogate rewards (η = 1) (r̂) . The noise rates increase from 0.1 to 0.9, with a step of 0.1.
Results for PPO on Pong-v4 in symmetric noise setting are presented in Figure 3. Due to limited space, more results on other Atari games and noise settings are given in Appendix D.3. Similar to previous results, our surrogate estimator performs consistently well and helps PPO converge to the optimal policy. Table 2 shows the average scores of PPO on five selected Atari games with different amounts of noise (symmetric & asymmetric). In particular, when the noise rates e+ = e− > 0.3, agents with surrogate rewards obtain significant amounts of improvements in average scores. We do not present the results for the case with unknown C because the state-space (image-input) is very large for Atari games, which is difficult to handle with the solution given in Section 3.3.

heading: 5 CONCLUSION

text:
Only an underwhelming amount of reinforcement learning studies have focused on the settings with perturbed and noisy rewards, despite the fact that such noises are common when exploring a realworld scenario, that faces sensor errors or adversarial examples. We adapt the ideas from supervised
learning with noisy examples (Natarajan et al., 2013), and propose a simple but effective RL framework for dealing with noisy rewards. The convergence guarantee and finite sample complexity of Q-Learning (or its variant) with estimated surrogate rewards are given. To validate the effectiveness of our approach, extensive experiments are conducted on OpenAI Gym, showing that surrogate rewards successfully rescue models from misleading rewards even at high noise rates.

heading: A PROOFS

text:
Proof of Lemma 1. For simplicity, we shorthand r̂(st, at, st+1), r̃(st, at, st+1), r(st, at, st+1) as r̂, r̃, r, and let r+, r−, r̂+, r̂− denote the general reward levels and corresponding surrogate ones:
Er̃|r(r̂) = Pr̃|r(r̂ = r̂−)r̂− + Pr̃|r(r̂ = r̂+)r̂+. (5) When r = r+, from the definition in Lemma 1:
Pr̃|r(r̂ = r̂−) = e+, Pr̃|r(r̂ = r̂+) = 1− e+. Taking the definition of surrogate rewards Eqn. (1) into Eqn. (5), we have
Er̃|r(r̂) = e+ · r̂− + (1− e+) · r̂+
= e+ · (1− e+)r− − e−r+
1− e− − e+ + (1− e+) · (1− e−)r+ − e+r− 1− e− − e+ = r+.
Similarly, when r = r−, it also verifies Er̃|r[r̂(st, at, st+1)] = r(st, at, st+1).
Proof of Lemma 2. The idea of constructing unbiased estimator is easily adapted to multi-outcome reward settings via writing out the conditions for the unbiasedness property (s.t. Er̃|r[r̂] = r.). For simplicity, we shorthand r̂(r̃ = Ri) as R̂i in the following proofs. Similar to Lemma 1, we need to solve the following set of functions to obtain r̂: R0 = c0,0 · R̂0 + c0,1 · R̂1 + · · ·+ c0,M−1 · R̂M−1 R1 = c1,0 · R̂0 + c1,1 · R̂1 + · · ·+ c1,M−1 · R̂M−1 · · ·
RM−1 = cM−1,0 · R̂0 + cM−1,1 · R̂1 + · · ·+ cM−1,M−1 · R̂M−1
where R̂i denotes the value of the surrogate reward when the observed reward is Ri. Define R := [R0;R1; · · · ;RM−1], and R̂ := [R̂0, R̂1, ..., R̂M−1], then the above equations are equivalent to: R = C · R̂. If the confusion matrix C is invertible, we obtain the surrogate reward:
R̂ = C−1 ·R. According to above definition, for any true reward level Ri, i = 0, 1, · · · ,M − 1, we have
Er̃|r=Ri [r̂] = ci,0 · R̂0 + ci,1 · R̂1 + · · ·+ ci,M−1 · R̂M−1 = Ri.
Furthermore, the probabilities for observing surrogate rewards can be written as follows:
P̂ = [p̂1, p̂2, · · · , p̂M ] = ∑ j pjcj,1, ∑ j pjcj,2, · · · , ∑ j pjcj,M  , where p̂i = ∑ j pjcj,i, and p̂i, pi represent the probabilities of occurrence for surrogate reward R̂i and true reward Ri respectively. Corollary 1. Let p̂i and pi denote the probabilities of occurrence for surrogate reward r̂(r̃ = Ri) and true reward Ri. Then the surrogate reward satisfies,∑
s′∈S Pa(st, st+1)r(st, a, st+1) = ∑ j pjRj = ∑ j p̂jR̂j . (6)
Proof of Corollary 1. From Lemma 2, we have,∑ st∈S Pa(st, st+1)r(st, a, st+1) = ∑ st+1∈S;Rj∈R Pa(st, st+1, Rj)Rj
= ∑ Rj∈R ∑ st+1∈S Pa(st, st+1)Rj = ∑ Rj∈R pjRj = ∑ j pjRj .
Consequently, ∑ j p̂jR̂j = ∑ j ∑ k pkck,jR̂j = ∑ k pk ∑ j ck,jR̂j
= ∑ k pkRk = ∑ st∈S Pa(st, st+1)r(st, a, st+1).
To establish Theorem 1, we need an auxiliary result (Lemma 3) from stochastic process approximation, which is widely adopted for the convergence proof for Q-Learning (Jaakkola et al., 1993; Tsitsiklis, 1994). Lemma 3. The random process {∆t} taking values in Rn and defined as
∆t+1(x) = (1− αt(x))∆t(x) + αt(x)Ft(x) converges to zero w.p.1 under the following assumptions:
• 0 ≤ αt ≤ 1, ∑ t αt(x) =∞ and ∑ t αt(x) 2 <∞;
• ||E [Ft(x)|Ft] ||W ≤ γ||∆t||, with γ < 1;
• var [Ft(x)|Ft] ≤ C(1 + ||∆t||2W ), for C > 0.
Here Ft = {∆t,∆t−1, · · · , Ft−1 · · · , αt, · · · } stands for the past at step t, αt(x) is allowed to depend on the past insofar as the above conditions remain valid. The notation || · ||W refers to some weighted maximum norm.
Proof of Lemma 3. See previous literature (Jaakkola et al., 1993; Tsitsiklis, 1994).
Proof of Theorem 1. For simplicity, we abbreviate st, st+1, Qt, Qt+1, rt, r̂t and αt as s, s′, Q, Q′, r, r̂, and α, respectively.
Subtracting from both sides the quantity Q∗(s, a) in Eqn. (3): Q′(s, a)−Q∗(s, a) = (1− α) (Q(s, a)−Q∗(s, a)) + α [ r̂ + γmax
b∈A Q(s′, b)−Q∗(s, a)
] .
Let ∆t(s, a) = Q(s, a)−Q∗(s, a) and Ft(s, a) = r̂ + γmaxb∈AQ(s′, b)−Q∗(s, a). ∆t+1(s
′, a) = (1− α)∆t(s, a) + αFt(s, a). In consequence,
E [Ft(x)|Ft] = ∑
s′∈S;r̂∈R
Pa(s, s′, r̂) [ r̂ + γmax
b∈A Q(s′, b)
] −Q∗(s, a)
= ∑
s′∈S;r̂∈R Pa(s, s′, r̂)r̂ + ∑ s′∈S Pa(s, s′) [ γmax b∈A Q(s′, b)− r − γmax b∈A Q∗(s′, b) ]
= ∑
s′∈S;r̂∈R Pa(s, s′, r̂)r̂ − ∑ s′∈S Pa(s, s′)r + ∑ s′∈S Pa(s, s′)γ [ max b∈A Q(s′, b)−max b∈A Q∗(s′, b) ]
= ∑ j p̂j r̂j − ∑ s′∈S Pa(s, s′)r + ∑ s′∈S Pa(s, s′)γ [ max b∈A Q(s′, b)−max b∈A Q∗(s′, b) ]
= ∑ s′∈S Pa(s, s′)γ [ max b∈A Q(s′, b)−max b∈A Q∗(s′, b) ] (using Eqn. (6))
≤ γ ∑ s′∈S Pa(s, s′) max b∈A,s′∈S |Q(s′, b)−Q∗(s′, b)|
= γ ∑ s′∈S Pa(s, s′)||Q−Q∗||∞ = γ||Q−Q∗||∞ = γ||∆t||∞.
Finally,
Var [Ft(x)|Ft] = E  r̂ + γmax
b∈A Q(s′, b)− ∑ s′∈S;r̂∈R P′(s, s′, r̂) [ r̂ + γmax b∈A Q(s′, b)
]2
= Var [ r̂ + γmax
b∈A Q(s′, b)|Ft ] .
Because r̂ is bounded, it can be clearly verified that
Var [Ft(x)|Ft] ≤ C(1 + ||∆t||2W )
for some constantC. Then, due to the Lemma 3, ∆t converges to zero w.p.1, i.e.,Q′(s, a) converges to Q∗(s, a).
The procedure of Phased Q-Learning is described as Algorithm 2:
Algorithm 2 Phased Q-Learning Input: G(M): generative model ofM = (S,A,R,P, γ), T : number of iterations. Output: V̂ (s): value function, π̂(s, t): policy function.
1: Set V̂T (s) = 0 2: for t = T − 1, · · · , 0 do
1. Calling G(M) m times for each state-action pair.
P̂a(st, st+1) = #[(st, at)→ st+1]
m
2. Set
V̂ (s) = max a∈A ∑ st+1∈S P̂a(st, st+1) [ rt + γV̂ (st+1) ] π̂(s, t) = arg max
a∈A V̂ (s)
3: return V̂ (s) and π̂(s, t)
Note that P̂ here is the estimated transition probability, which is different from P in Eqn. (6).
To obtain the sample complexity results, the range of our surrogate reward needs to be known. Assuming reward r is bounded in [0, Rmax], Lemma 4 below states that the surrogate reward is also bounded, when the confusion matrices are invertible:
Lemma 4. Let r ∈ [0, Rmax] be bounded, whereRmax is a constant; suppose CM×M , the confusion matrix, is invertible with its determinant denoting as det(C). Then the surrogate reward satisfies
0 ≤ |r̂| ≤ M det(C) Rmax. (7)
Proof of Lemma 4. From Eqn. (2), we have,
R̂ = C−1 ·R = adj(C) det(C) ·R,
where adj(C) is the adjugate matrix of C; det(C) is the determinant of C. It is known from linear algebra that,
adj(C)ij = (−1)i+j ·Mji,
where Mji is the determinant of the (M − 1)× (M − 1) matrix that results from deleting row j and column i of C. Therefore, Mji is also bounded:
Mji ≤ ∑ σ∈Sn
( |sgn(σ)|
∏ m=1 c′m,σn ) ≤ M−1∏ m=0 ( M−1∑ n=0 cm,n ) = 1M = 1,
where the sum is computed over all permutations σ of the set {0, 1, · · · ,M − 2}; c′ is the element of Mji; sgn(σ) returns a value that is +1 whenever the reordering given by σ can be achieved by successively interchanging two entries an even number of times, and −1 whenever it can not. Consequently, ∣∣∣R̂i∣∣∣ = ∑j |adj(C)ij | · |Rj |
det(C) ≤ M det(C) ·Rmax.
Proof of Theorem 2. From Hoeffding’s inequality, we obtain:
P ∣∣∣∣∣∣ ∑ st+1∈S Pa(st, st+1)V ∗t+1(st+1)− ∑ st+1∈S P̂a(st, st+1)V ∗t+1(st+1) ∣∣∣∣∣∣ ≥
≤ 2 exp ( −2m 2(1− γ)2
R2max
) ,
because Vt(st) is bounded within Rmax1−γ . In the same way, r̂t is bounded by M det(C) · Rmax from Lemma 4. We then have,
P  ∣∣∣∣∣∣∣∣ ∑
st+1∈S r̂t∈R̂
Pa(st, st+1, r̂t)r̂t − ∑
st+1∈S r̂t∈R̂
P̂a(st, st+1, r̂t)r̂t ∣∣∣∣∣∣∣∣ ≥  ≤ 2 exp(−2m 2det(C)2M2R2max ) .
Further, due to the unbiasedness of surrogate rewards, we have∑ st+1∈S Pa(st, st+1)rt = ∑
st+1∈S;r̂t∈R̂
Pa(st, st+1, r̂t)r̂t.
As a result,∣∣∣V ∗t (s)− V̂t(s)∣∣∣ = max a∈A ∑ st+1∈S Pa(st, st+1) [ rt + γV ∗ t+1(st+1) ] −max
a∈A ∑ st+1∈S P̂a(st, st+1) [ r̂t + γV ∗ t+1(st+1) ]
≤ 1 + γmax a∈A ∣∣∣∣∣∣ ∑ st+1∈S Pa(st, st+1)V ∗t+1(st+1)− ∑ st+1∈S P̂a(st, st+1)V ∗t+1(st+1) ∣∣∣∣∣∣ + max
a∈A ∣∣∣∣∣∣ ∑ st+1∈S Pa(st, st+1)rt − ∑ st+1∈S;r̂t∈R̂ Pa(st, st+1, r̂t)r̂t ∣∣∣∣∣∣ ≤ γmax
s∈S ∣∣∣V ∗t+1(s)− V̂t+1(s)∣∣∣+ 1 + γ 2 In the same way, ∣∣∣Vt(s)− V̂t(s)∣∣∣ ≤ γmax
s∈S
∣∣∣V ∗t+1(s)− V̂t+1(s)∣∣∣+ 1 + γ 2
Recursing the two equations in two directions (0→ T ), we get
max s∈S ∣∣∣V ∗(s)− V̂ (s)∣∣∣ ≤ ( 1 + γ 2) + γ( 1 + γ 2) + · · ·+ γT−1( 1 + γ 2) =
( 1 + γ 2)(1− γT ) 1− γ
max s∈S ∣∣∣V (s)− V̂ (s)∣∣∣ ≤ ( 1 + γ 2)(1− γT ) 1− γ
Combining these two inequalities above we have:
max s∈S |V ∗(s)− V (s)| ≤ 2( 1 + γ 2)(1− γ T ) 1− γ ≤ 2( 1 + γ 2) 1− γ .
Let 1 = 2, so maxs∈S |V ∗(s)− V (s)| ≤ as long as
1 = 2 ≤ (1− γ) 2(1 + γ) .
For arbitrarily small , by choosing m appropriately, there always exists 1 = 2 = (1−γ) 2(1+γ) such that the policy error is bounded within . That is to say, the Phased Q-Learning algorithm can converge to the near optimal policy within finite steps using our proposed surrogate rewards.
Finally, there are |S||A|T transitions under which these conditions must hold, where | · | represent the number of elements in a specific set. Using a union bound, the probability of failure in any condition is smaller than
2|S||A|T · exp ( −m 2(1− γ)2
2(1 + γ)2 ·min{(1− γ)2, det(C)
2 M2 } ) .
We set the error rate less than δ, and m should satisfy that
m = O
( 1
2(1− γ)2det(C)2 log |S||A|T δ
) .
In consequence, afterm|S||A|T calls, which is,O (
|S||A|T 2(1−γ)2det(C)2 log |S||A|T δ
) , the value function
converges to the optimal one for every state s, with probability greater than 1− δ.
The above bound is for discounted MDP setting with 0 ≤ γ < 1. For undiscounted setting γ = 1, since the total error (for entire trajectory of T time-steps) has to be bounded by , therefore, the error for each time step has to be bounded by T . Repeating our anayslis, we obtain the following upper bound:
O
( |S||A|T 3
2det(C)2 log |S||A|T δ
) .

heading: Proof of Theorem 3.

text:
Var(r̂)−Var(r) = E [ (r̂ − E[r̂])2 ] − E [ (r − E[r])2 ] = E[r̂2]− E[r̂]2 + E[r2]− E[r]2
= ∑ j p̂jR̂j 2 − ∑ j p̂jR̂j 2 − ∑ j pjRj 2 − ∑ j pjRj 2  = ∑ j p̂jR̂j 2 − ∑ j pjRj 2 = ∑ j ∑ i pici,jR̂j 2 − ∑ j pj (∑ i cj,iR̂i )2 = ∑ j pj ∑ i cj,iR̂i 2 − (∑ i cj,iR̂i )2 .
Using the CauchySchwarz inequality,∑ i cj,iR̂i 2 = ∑ i √ cj,i 2 · ∑ i (√ cj,iR̂i )2 ≥ (∑ i cj,iR̂i )2 .
So we get, Var(r̂)−Var(r) ≥ 0.
In addition,
Var(r̂) = ∑ j p̂jR̂j 2 − ∑ j p̂jR̂j 2 ≤∑ j p̂jR̂j 2
≤ ∑ j p̂j M2 det(C)2 ·R2max = M2 det(C)2 ·R2max.

heading: B EXPERIMENTAL SETUP

text:
We set up our experiments within the popular OpenAI baselines (Dhariwal et al., 2017) and kerasrl (Plappert, 2016) framework. Specifically, we integrate the algorithms and interact with OpenAI Gym (Brockman et al., 2016) environments (Table 3).
B.1 RL ALGORITHMS
A set of state-of-the-art reinforcement learning algorithms are experimented with while training under different amounts of noise, including Q-Learning (Watkins, 1989; Watkins & Dayan, 1992), Cross-Entropy Method (CEM) (Szita & Lörincz, 2006), Deep SARSA (Sutton & Barto, 1998), Deep Q-Network (DQN) (Mnih et al., 2013; 2015; van Hasselt et al., 2016), Dueling DQN (DDQN) (Wang et al., 2016), Deep Deterministic Policy Gradient (DDPG) (Lillicrap et al., 2015), Continuous DQN (NAF) (Gu et al., 2016) and Proximal Policy Optimization (PPO) (Schulman et al., 2017) algorithms. For each game and algorithm, three policies are trained based on different random initialization to decrease the variance in experiments.

heading: B.2 POST-PROCESSING REWARDS

text:
We explore both symmetric and asymmetric noise of different noise levels. For symmetric noise, the confusion matrices are symmetric, which means the probabilities of corruption for each reward choice are equivalent. For instance, a confusion matrix
C = [ 0.8 0.2 0.2 0.8 ] says that r1 could be corrupted into r2 with a probability of 0.2 and so does r2 (weight = 0.2).
As for asymmetric noise, two types of random noise are tested: 1) rand-one, each reward level can only be perturbed into another reward; 2) rand-all, each reward could be perturbed to any other reward. To measure the amount of noise w.r.t confusion matrices, we define the weight of noise as follows: C = (1− ω) · I + ω ·N, ω ∈ [0, 1], where ω controls the weight of noise; I and N denote the identity and noise matrix respectively. Suppose there are M outcomes for true rewards, N writes as:
N = [ n0,0 n0,1 · · · n0,M−1 · · · · · · · · · · · ·
nM−1,0 nM−1,1 · · · nM−1,M−1
] ,
where for each row i, 1) rand-one: randomly choose j, s.t ni,j = 1 and ni,k 6= 0 if k 6= j; 2) randall: generate M random numbers that sum to 1, i.e., ∑ j ni,j = 1. For the simplicity, for symmetric noise, we choose N as an anti-identity matrix. As a result, ci,j = 0, if i 6= j or i+ j 6= M .

heading: B.3 PERTURBED-REWARD MDP EXAMPLE

text:
To obtain an intuitive view of the reward perturbation model, where the observed rewards are generated based on a reward confusion matrix, we constructed a simple MDP and evaluated the performance of robust reward Q-Learning (Algorithm 1) on different noise ratios (both symmetric and asymmetric). The finite MDP is formulated as Figure 4a: when the agent reaches state 5, it gets an instant reward of r+ = 1, otherwise a zero reward r− = 0. During the explorations, the rewards are perturbed according to the confusion matrix C2×2 = [1− e−, e−; e+, 1− e+].
There are two experiments conducted in this setting: 1) performance of Q-Learning under different noise rates (Table 4); 2) robustness of estimation module in time-variant noise (Figure 4b). As shown in Table 4, Q-Learning achieved better results consistently with the guidance of surrogate rewards and the confusion matrix estimation algorithm. For time-variant noise, we generated varying amount of noise at different training stages: 1) e− = 0.1, e+ = 0.3 (0 to 1e4 steps); 2) e− = 0.2, e+ = 0.1 (1e4 to 3e4 steps); 3) e− = 0.3, e+ = 0.2 (3e4 to 5e4 steps); 4) e− = 0.1, e+ = 0.2 (5e4 to 7e4 steps). In Figure 4b, we show that Algorithm 1 is robust against time-variant noise, which dynamically adjusts the estimated C̃ after the noise distribution changes. Note that we set a maximum memory size for collected noisy rewards to let the agents only learn with recent observations.

heading: B.4 TRAINING DETAILS

text:
CartPole and Pendulum The policies use the default network from keras-rl framework. which is a five-layer fully connected network6. There are three hidden layers, each of which has 16 units and followed by a rectified nonlinearity. The last output layer is activated by the linear function. For
6https://github.com/keras-rl/keras-rl/examples
CartPole, We trained the models using Adam optimizer with the learning rate of 1e−3 for 10,000 steps. The exploration strategy is Boltzmann policy. For DQN and Dueling-DQN, the update rate of target model and the memory size are 1e−2 and 50, 000. For Pendulum, We trained DDPG and NAF using Adam optimizer with the learning rate of 5e−4 for 150, 000 steps. the update rate of target model and the memory size are 1e−3 and 100, 000.
Atari Games We adopt the pre-processing steps as well as the network architecture from Mnih et al. (2015). Specifically, the input to the network is 84×84×4, which is a concatenation of the last 4 frames and converted into 84 × 84 gray-scale. The network comprises three convolutional layers and two fully connected layers7. The kernel size of three convolutional layer are 8 × 8 with stride 4 (32 filters), 4 × 4 with stride 2 (64 filters) and 3 × 3 with stride 1 (64 filters), respectively. Each hidden layer is followed by a rectified nonlinearity. Except for Pong where we train the policies for 3e7 steps, all the games are trained for 5e7 steps with the learning rate of 3e−4. Note that the rewards in the Atari games are discrete and clipped into {−1, 0, 1}. Except for Pong game, in which r = −1 means missing the ball hit by the adversary, the agents in other games attempt to get higher scores in the episode with binary rewards 0 and 1.

heading: C ESTIMATION OF CONFUSION MATRICES

heading: C.1 REWARD ROBUST RL ALGORITHMS

text:
As stated in Section 3.3, the confusion matrix can be estimated dynamically based on the aggregated answers, similar to previous literature in supervised learning (Khetan et al., 2017). To get a concrete view, we take Q-Learning for an example, and the algorithm is called Reward Robust Q-Learning (Algorithm 3). Note that is can be extended to other RL algorithms by plugging confusion matrix estimation steps and the computed surrogate rewards, as shown in the experiments (Figure 6).
Algorithm 3 Reward Robust Q-Learning

heading: Input:

text:
M̃ = (S,A, R̃,P, γ): MDP with corrupted reward channel T : transition function T : S ×A → S N ∈ N: upper bound of collected noisy rewards α ∈ (0, 1): learning rate in the update rule η ∈ (0, 1): weight of unbiased surrogate reward R̃(s, a): set of observed rewards when the state-action pair is (s, a). Output: Q(s): value function; π(s, t): policy function Initialize Q: S ×A → R arbitrarily Set confusion matrix C̃ as zero while Q is not converged do
Start in state s ∈ S while s is not terminal do
Calculate π according to Q and exploration strategy a← π(s) s′ ← T (s, a) Observe noisy reward r̃(s, a) and add it to R̃(s, a) if ∑
(s,a) |R̃(s, a)| ≥ N then Get predicted true reward r̄(s, a) using majority voting in every R̃(s, a) Estimate confusion matrix C̃ based on r̃(s, a) and r̄(s, a) (Eqn. (4)) Empty all the sets of observed rewards R̃(s, a)
Obtain surrogate reward ṙ(s, a) using Rproxy = (1− η) ·R + η ·C−1R Q(s′, a)← (1− α) ·Q(s, a) + α · (r̂(s, a) + γ ·maxa′ Q(s′, a′)) s← s′
return Q(s) and π(s)
7https://github.com/openai/baselines/tree/master/baselines/common

heading: C.2 EXPECTATION-MAXIMIZATION IN ESTIMATION

text:
In Algorithm 3, the predicted true reward r̄(s, a) is derived from majority voting in collected noisy sets R̃(s, a) for every state-action pair (s, a) ∈ S × A, which is a simple but efficient way of leveraging the expectation of aggregated rewards without assumptions on prior distribution of noise. In the following, we adopt standard Expectation-Maximization (EM) idea in the our estimation framework (arguably a simple version of it), inspired by previous works (Zhang et al., 2014).
Assuming the observed noisy rewards are independent conditional on the true reward, we can compute the posterior probability of true reward from the Bayes’ theorem:
P(r = Ri|r̃(1) = R1, · · · , r̃(n) = Rn) = P(r̃(1) = R1, · · · , r̃(n) = Rn|r = Ri) · P(r = Ri)∑ j P(r̃(1) = R1, · · · , r̃(n) = Rn|r = Rj) · P(r = Rj)
= P(r = Ri) · ∏n k=1 P(r̃(k) = Rk|r = Ri)∑
j [P(r = Rj) · ∏n k=1 P(r̃(k) = Rk|r = Rj)]
(8)
where P(r = Rj) is the prior of true rewards, and P(r̃ = Rk|r = Rj) is estimated by current estimated confusion matrix C̃: P(r̃ = Rk|r = Rj) = c̃j,i. Note that the inference should be conducted for each state-action pair (s, a) ∈ S × A in every iteration, i.e., P(r(s, a) = Ri|r̃(s, a, 1) = R1, · · · , r̃(s, a, n) = Rn), abbreviated as P(r̄(s, a) = Ri), which requires relatively greater computation costs compared to the majority voting policy. It also points out an interesting direction to check online EM algorithms for our perturbed-RL problem.
After the inference steps in Eqn. (8), the confusion matrix C̃ is then updated based on the posterior probabilities:
c̃i,j =
∑ (s,a) P(r̄(s, a) = Ri) ·# [r̃(s, a) = Rj |r̄(s, a) = Ri]∑
(s,a) P(r̄(s, a) = Ri) ·#[r̄(s, a) = Ri] , (9)
where P(r̄(s, a) = Ri) denotes the inference probabilities of true rewards based on collected noisy rewards sets R̃(s, a). To utilize EM algorithms in the robust reward algorithms (e.g., Algorithm 3), we need to replace Eqn. (4) by Eqn. (9) for the estimation of reward confusion matrix.

heading: C.3 STATE-DEPENDENT PERTURBED REWARD

text:
In previous sections, to let our presentation stay focused, we consider the state-independent perturbed reward environments, which share the same confusion matrix for all states. In other words, the noise for different states is generated within the same distribution. More generally, the generation of r̃ follows a certain function C : S × R → R̃, where different states may correspond to varied noise distributions (also varied confusion matrices). However, our algorithm is still applicable except for maintaining different confusion matrices Cs for different states. It is worthy to notice that Theorem 1 holds because the surrogate rewards produce an unbiased estimation of true rewards for each state, i.e., Er̃|r,st [r̂(st, at, st+1)] = r(st, at, st+1). Furthermore, Theorem 2 and 3 can be revised as:
Theorem 4. (Upper bound) Let r ∈ [0, Rmax] be bounded reward, Cs be invertible reward confusion matrices with det(Cs) denoting its determinant. For an appropriate choice of m, the Phased Q-Learning algorithm calls the generative model G(M̂)
O
( |S||A|T
2(1− γ)2 mins∈S{det(Cs)}2 log |S||A|T δ ) times in T epochs, and returns a policy such that for all state s ∈ S, |Vπ(s)− V ∗(s)| ≤ , > 0, w.p. ≥ 1− δ, 0 < δ < 1. Theorem 5. Let r ∈ [0, Rmax] be bounded reward and all confusion matrices Cs are invertible. Then, the variance of surrogate reward r̂ is bounded as follows:
Var(r) ≤ Var(r̂) ≤ M 2
mins∈S{det(Cs)}2 ·R2max.
C.4 VARIANCE REDUCTION IN ESTIMATION
As illustrated in Theorem 3, our surrogate rewards introduce larger variance while conducting unbiased estimation which are likely to decrease the stability of RL algorithms. Apart from the linear combination idea (appropriate trade-off), some variance reduction techniques in statistics (e.g., correlated sampling) can also be applied into our surrogate rewards. Specially, Romoff et al. (2018) proposed to a reward estimator to compensate for stochastic corrupted reward signals. It is worthy to notice that their method is designed for variance reduction under stochastic (zero-mean) noise, which is no longer efficacious in more general perturbed-reward setting. However, it is potential to integrate their method with our robust-reward RL framework because surrogate rewards guarantee unbiasedness in reward expectation.
To verify this idea, we repeated the experiments of Cartpole in Section 4.2 but included variance reduction step for estimated surrogate rewards. Following Romoff et al. (2018), we adopted sample mean as a simple approximator during the training and set sequence length as 100. As shown in Figure 5, the models with only variance reduction technique (red lines) suffer from huge biases when the noise is large, and cannot converge to the optimal policies like those under noisy rewards. Nevertheless, they benefits from variance reduction for surrogate rewards (purple lines), which achieve faster convergence or better performance in many cases (e.g., Figure 5a (ω = 0.7), 5b (ω = 0.3)). It is also not surprising that the integrated algorithm (purple lines) outperforms better as the noise rate increases (indicating larger variance from Theorem 3, e.g., ω = 0.9). Similarly, Table 5 provides quantitative results which show that our surrogate benefits from variance reduction techniques (“ours + VRT”), especially when the noise rate is large.
game with true rewards (r) , noisy rewards (r̃) (η = 1) , sample-mean noisy rewards (η = 1) , estimated surrogate rewards (ṙ) and sample-mean estimated surrogate rewards . Note that confusion matrices C are unknown to the agents here. From top to the bottom, the noise rates are 0.1, 0.3, 0.7 and 0.9. Here we repeated each experiment 10 times with different random seeds and plotted 10% to 90% percentile area with its mean highlighted.

heading: C.5 EXPERIMENTAL RESULTS

text:
To validate the effectiveness of robust reward algorithms (like Algorithm 3), where the noise rates are unknown to the agents, we conduct extensive experiments in CartPole. It is worthwhile to notice that the noisy rates are unknown in the explorations of RL agents. Besides, we discretize the
observation (velocity, angle, etc.) to construct a set of states and implement like Algorithm 3. The η is set 1.0 in the experiments.
Figure 6 provides learning curves from five algorithms with different kinds of rewards. The proposed estimation algorithms successfully obtain the approximate confusion matrices, and are robust in the unknown noise environments. From Figure 7, we can observe that the estimation of confusion matrices converges very fast. The results are inspiring because we don’t assume any additional knowledge about noise or true reward distribution in the implementation.
CartPole game with true rewards (r) , noisy rewards (r̃) (η = 1) and estimated surrogate rewards (ṙ) . Note that confusion matrices C are unknown to the agents here. From top to the bottom, the noise rates are 0.1, 0.3, 0.7 and 0.9. Here we repeated each experiment 10 times with different random seeds and plotted 10% to 90% percentile area with its mean highlighted.

heading: D.1 SUPPLEMENTARY QUANTITATIVE RESULTS

heading: D SUPPLEMENTARY EXPERIMENTAL RESULTS

text:
D.2 VISUALIZATIONS ON CONTROL GAMES
(r) , noisy rewards (r̃) and surrogate rewards (r̂) (η = 1) . Both symmetric and asymmetric noise are conduced in the experiments. From top to the bottom, the noise rates are 0.1, 0.3, 0.7 and 0.9, respectively. Here we repeated each experiment 6 times with different random seeds and plotted 10% to 90% percentile area with its mean highlighted.
D.3 VISUALIZATIONS ON ATARI GAMES8
D.3.1 PONG
Asymmetric Noise (rand-one)
8For the clarity purpose, we remove the learning curves (blue ones in previous figures) with true rewards except for Pong-v4 game.
Asymmetric Noise (rand-all)

heading: D.3.2 AIRRAID

text: D.3.3 ALIEN

heading: D.3.4 CARNIVAL

heading: D.3.5 MSPACMAN

text:
D.3.6 PHOENIX
D.3.7 SEAQUEST


summaries: This paper discusses the effect of increasing the widths in deep neural networks on the convergence of optimization. To this end, the paper focuses on RNNs and applications to NLP and speech recognition, and designs several groups of experiments/measurements to show that wider RNNs improve the convergence speed in three different aspects: 1) the number of steps taken to converge to the minimum validation loss is smaller; 2) the distance from initialization to final weights is shorter; 3) the step sizes (gradient norms) are larger. This in some sense complements the theoretical result in Arora et al. (2018) for linear neural networks (LNN), which states that deeper LNNs accelerates convergence of optimization, but the hidden layers widths are irrelevant. This also shows some essential difference between LNNs and (practical) nonlinear neural networks.

summaries: Understanding the effects of over-parametrization in neural network training has been a major challenge, albeit a lot of progress has been made in the past few years. The present paper is another attempt in this direction, with a slightly different point of view: the work characterizes the impact of over-parametrization in the number of iterations it takes an algorithm to converge. Along the way, it also presents further empirical observations such as the distance between the initial point and the final point and the angle between the gradients and the line that connects the initial and final points. Even though the observations presented are very interesting, unfortunately, the paper doesn't have the level of rigor required that would make it a solid reference.

abstractText: A long-held conventional wisdom states that larger models train more slowly when using gradient descent. This work challenges this widely-held belief, showing that larger models can potentially train faster despite the increasing computational requirements of each training step. In particular, we study the effect of network structure (depth and width) on halting time and show that larger models—wider models in particular—take fewer training steps to converge. We design simple experiments to quantitatively characterize the effect of overparametrization on weight space traversal. Results show that halting time improves when growing model’s width for three different applications, and the improvement comes from each factor: The distance from initialized weights to converged weights shrinks with a power-law-like relationship, the average step size grows with a power-law-like relationship, and gradient vectors become more aligned with each other during traversal.

authors:
Dario Amodei
Rishita Anubhai
Eric Battenberg
Carl Case
Jared Casper
Bryan Catanzaro
JingDong Chen
Mike Chrzanowski
Adam Coates
Greg Diamos

title: Deep Speech 2: End-to-End Speech Recognition in English and Mandarin

venue: In Proceedings of The International Conference on Machine Learning (ICML),

authors:
Sanjeev Arora
Nadav Cohen
Elad Hazan

title: On the optimization of deep networks: Implicit acceleration by overparameterization

venue: arXiv preprint arXiv:1802.06509,

authors:
Ciprian Chelba
Tomas Mikolov
Mike Schuster
Qi Ge
Thorsten Brants
Phillipp Koehn
Tony Robinson

title: One Billion Word Benchmark for Measuring Progress in Statistical Language Modeling

venue: arXiv preprint arXiv:1312.3005,

authors:
Lingjiao Chen
Hongyi Wang
Jinman Zhao
Dimitris Papailiopoulos
Paraschos Koutris

title: The effect of network width on the performance of large-batch training

venue: arXiv preprint arXiv:1806.03791,

authors:
Anna Choromanska
Mikael Henaff
Michael Mathieu
Gérard Ben Arous
Yann LeCun

title: The loss surfaces of multilayer networks

venue: In Artificial Intelligence and Statistics,

authors:
Jan K. Chorowski
Dzmitry Bahdanau
Dmitriy Serdyuk
Kyunghyun Cho
Yoshua Bengio

title: Attention-based Models for Speech Recognition

venue: In Advances in Neural Information Processing Systems,

authors:
Yann N Dauphin
Razvan Pascanu
Caglar Gulcehre
Kyunghyun Cho
Surya Ganguli
Yoshua Bengio

title: Identifying and attacking the saddle point problem in high-dimensional non-convex optimization

venue: In Advances in neural information processing systems,

authors:
Rong Ge
Furong Huang
Chi Jin
Yang Yuan

title: Escaping from saddle pointsonline stochastic gradient for tensor decomposition

venue: In Conference on Learning Theory, pp

authors:
Ian J Goodfellow
Oriol Vinyals
Andrew M Saxe

title: Qualitatively characterizing neural network optimization problems

venue: arXiv preprint arXiv:1412.6544,

authors:
Alex Graves
Santiago Fernández
Faustino Gomez
Jürgen Schmidhuber

title: Connectionist Temporal Classification: Labelling Unsegmented Sequence Data with Recurrent Neural Networks

venue: In Proceedings of the International Conference on Machine Learning (ICML),

authors:
Awni Hannun
Carl Case
Jared Casper
Bryan Catanzaro
Greg Diamos
Erich Elsen
Ryan Prenger
Sanjeev Satheesh
Shubho Sengupta
Adam Coates

title: Deep Speech: Scaling Up End-to-End Speech Recognition

venue: arXiv preprint arXiv:1412.5567,

authors:
Rafal Jozefowicz
Oriol Vinyals
Mike Schuster
Noam Shazeer
Yonghui Wu

title: Exploring the Limits of Language Modeling

venue: arXiv preprint arXiv:1602.02410v2,

authors:
Nitish Shirish Keskar
Dheevatsa Mudigere
Jorge Nocedal
Mikhail Smelyanskiy
Ping Tak Peter Tang

title: On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima

venue: arXiv preprint arXiv:1609.04836,

authors:
Yann LeCun
Ido Kanter
Sara A Solla

title: Second order properties of error surfaces: Learning time and generalization

authors:
David Saad
Sara A Solla

title: Exact solution for on-line learning in multilayer neural networks

venue: Physical Review Letters,

authors:
Levent Sagun
V Ugur Guney
Gerard Ben Arous
Yann LeCun

title: Explorations on high dimensional landscapes

venue: arXiv preprint arXiv:1412.6615,

authors:
Levent Sagun
Thomas Trogdon
Yann LeCun

title: Universal halting times in optimization and machine learning

venue: arXiv preprint arXiv:1511.06444,

authors:
Andrew M Saxe
James L McClelland
Surya Ganguli

title: Exact solutions to the nonlinear dynamics of learning in deep linear neural networks

venue: arXiv preprint arXiv:1312.6120,

authors:
Dong Yin
Ashwin Pananjady
Max Lam
Dimitris Papailiopoulos
Kannan Ramchandran
Peter Bartlett

title: Gradient diversity: a key ingredient for scalable distributed learning

venue: arXiv preprint arXiv:1706.05699,

authors:
Julian Georg Zilly
Rupesh Kumar Srivastava
Jan Koutnik
Jurgen Schmidhuber

title: Recurrent Highway Networks

heading: 1 INTRODUCTION

text:
How does overparametrization affect the convergence? Arora et al. (2018) have shown that for a simple LNN increasing depth can accelerate optimization, but increasing width does not affect convergence. However, the conclusion of ”width does not matter” is a consequence of an implicit assumption that minimum width is larger than input dimensionality. If hidden dimension is wide enough to absorb all the information within the input data, increasing width obviously would not affect convergence. For many real problems, however we are operating in a regime where hidden dimension is generally smaller than input dimension. In particular, RNN operate in this regime.
Using the machinery introduced in the work of Yin et al. (2017), we will show that convergence rate is a function of direct distance from initialization point to final point, average step size and the average angle between gradient vectors and the path that connects current weights to final wights.
In this paper, we present a variety of experiments designed to characterize the effect of width on error surface. These experiments are designed to qualitatively answer simple questions. How does width affect the convergence? Why does wider network converge faster? Which factors contribute more to the convergence, increase in the step size, better alignment of gradient vectors towards the final weights or the reduction in direct distance? Is the improvement the result of increasing model capacity or there is a true acceleration phenomenon? Why does the convergence improvement slows down beyond a certain model size?
We study the characteristics of convergence curve and show that it can be characterized into a powerlaw region within which the number of gradient updates to convergence has a reciprocal relationship to model size and linear relationship to dataset size, and a flat region within which increasing model size does not affect convergence.
We analyze the error surface characteristics of overparametrized models. Our qualitative results suggest that as models get wider (1) direct distance from initial weight to final weights shrinks. (2) Total path length traveled gets shrinks. (3) path length shrinks faster than direct distance. (4) step size gets larger. These results collectively suggests that number of local minimas in higher dimensional space grows asymmetrically wrt. origin and there exists a shorter path within the extra
dimension to the newly-found local minimas. We also provide a simple theoretical analysis for a simplified problem of LNN and show that direct distance is expected to shrink as models get wider.

heading: 2 RELATED WORK

text:
Error Surface Characterization Researchers have extensively studied the properties of error surface in linear neural network (Choromanska et al. (2015); Goodfellow et al. (2014)) and saddle points impact on optimization (Dauphin et al. (2014); Keskar et al. (2016); Ge et al. (2015)).
Halting time Researchers have studied the relationship between the learning time and the second order properties of the error surface (LeCun et al. (1991)). A large body of work has studied the halting time (number of iterations to reach to a given accuracy) for multi-layer NN from statistical physics perspective (Saad & Solla (1995); Saxe et al. (2013); Sagun et al. (2015; 2014)).
Effect of Network Structure on Convergence Arora et al. (2018) studies the effect of depth on convergence. Chen et al. (2018) has studied the effect of network width on the performance of large batch training and have shown that increasing width allows larger batch training.

heading: 3 EXPERIMENTS

heading: 3.1 SETUP

text: When training a learner with an iterative method, such as gradient descent, we often observe that training error decreases steadily while validation/test set error decreases but to rise again or flattens when the model overfits or runs out of capacity. We define time-to-convergence as the number of iterations to reach to 1% of the minimum validation loss. For some application, validation curves are very noisy and so we need a margin of error. When validation curves flatten out, we measure the time before it gets to 1% of the minimum value. We increase the model size by increasing the model’s width, while keeping all the other architecture parameters fixed (same learning rate, same batch size, etc.). We loot at three established RNN models: character-level language model (LM), word-level LM and speech recognition. The details of their configurations can be found in Appendix A.

heading: 3.2 CONVERGENCE CURVES

text:
Convergence curve shows the number of iterations (steps) to minimum validation loss for different model sizes.
Baseline Large learning rate are known to speedup the training process, while small learning rate slow down the training process. So to begin with, we use vanilla SGD, with fixed learning rate (0.8 for character model and 0.3 for word model) to train language models. Figure 1a and 1b show the convergence curve for character model and world model. X-axis and Y-axis are in logarithmic-scale.
Different lines presents different dataset sizes. We can make the following observations from these figures:
• The number of steps to convergence drops and the drop-down pattern is well approximated with power law relationship (a ∗Model Size−k + b).
• Increasing training size increases the number of steps to convergence. • Power law slope is a function of application and its dataset.
Effect of Learning Rate on Convergence Pattern As mentioned previously, increasing the learning rate is expected to reduce the number of steps to minimum validation loss. We study how changing learning rate affects the power law trend. We train models once with learning rate 0.8 and once with learning rate 0.3. As depicted in Figure 2(a) increasing the learning rate simply shifts down the curve (scaling down the a) without changing the slop (k). We also study how changing learning rate during the training process affect the power law trend. For this study, we use Adam optimizer which adaptively changes the learning rate during the training process. As shown in Figure 2 (b), using adaptive learning rate changes both the slope and intercept (changing both a and k).
Effect of Depth on Convergence Pattern So far we studied how the number of steps to minimum validation loss drops as models grows wider. Here, we will show same pattern holds for deeper model too. As shown in Figure 10a as models get deeper, the number of steps to minimum validation loss drops. These results are for character LM with vanilla SGD.
Effect of Training Set Size on Convergence Pattern As shown before, increasing dataset size increases the number of steps. As shown in Figure 10b the relationship between number of steps
and dataset size is almost linear. We can approximate the number of training step to minimum validation loss with D/Mk, where D is the size of training set, M is the model size in terms of the number of parameters, and k is a constant specific to the application and optimization techniques. Therefore, if we scale the dataset size by S, model size can be scaled by SK to keep the number of training steps the same.

heading: 4 ANALYSIS

heading: 4.1 CONVERGENCE CURVE PROFILE

text: Figure 4 shows a sketch of a model’s convergence curve—the reduction in number of steps to convergence as model size grows in number of parameters. Our empirical results indicate the curve begins in a seemingly “power-law” region where each new weight absorbs extra information from each sample, reducing the total number of samples observed before convergence. However, curves are likely to end in a “minimum data region” where number of steps cannot further decline—the data can offer no more information per sample. One can imagine this is one epoch if there is no redundancy in data, but can be potentially less than one if there is redundancy in data. Further study is required to understand the behavior of the convergence curve for small models.

heading: 4.2 THEORETICAL MACHINERY

text:
We use the machinery introduced by Yin et al. (2017) to characterize convergence as follows. Consider fi(W (t)) to be the model’s loss on sample i at time step t of gradient descent. Therefore, total loss and gradient at time step t can be presented as follows:
F (W ) := 1
n n−1∑ i=0 fi(W )
∇F (W ) := 1 n n−1∑ i=0 ∇fi(W )
(1)
From the gradient descent formula, we have:
W (t) = W (t−1) − α∇F (W (t−1))( W (t) −W ∗ ) = ( W (t−1) −W ∗ ) − α∇F (W (t−1))
||W (t) −W ∗||2 = ||W (t−1) −W ∗||2 + α2||∇F (W (t−1))||2
− 2α〈W (t−1) −W ∗,∇F (W (t−1))〉
(2)
Where W ∗ ∈ argminW F (W ) presents the parameters of the best model. By applying these equation recursively, we find that:
||W (T ) −W ∗||2 = ||W (0) −W ∗||2 + α2 T−1∑ t=0 ||∇F (W (t))||2
− 2α T−1∑ t=0 〈W (t) −W ∗,∇F (W (t))〉
(3)
Therefore, to find the minimum number of gradient updates required to reach within -proximity of the best answer, we can evaluate the following expectation:
E [ ||W (T ) −W ∗||2 ] ≤
E [ ||W (0) −W ∗||2 ] + α2 T−1∑ t=0 E [ ||∇F (W (t))||2 ] − 2α T−1∑ t=0 E [ 〈W (t) −W ∗,∇F (W (t))〉 ] ≤
E [ ||W (0) −W ∗||2 ] + α2T E [ ||∇F (W (t))||2 ] − 2αT E [ 〈W (t) −W ∗,∇F (W (t))〉 ] ≤
(4)
Note here that in the above inequality, the first term presents the average distance from initialization point to the best answer (squared). Second term, presents the average step length (squared), and the third term captures the average degree of misalignment of gradient vectors from the direct path towards to the best answer, average distance from the best answer and average step size.

heading: 4.3 ERROR SURFACE CHARACTERIZATION

text:
To characterize the effect of overparametrization on convergence, we study how the network structure affects each of the following components: direct distance from initial point to final point, the average step length and average angle between weight vector and the path towards the best answer.
The results in this section are for character language model with SGD optimizer, described in subsection 3.1. We study the effect of overparametrization across different components of the model, i.e. embedding layer, hidden layers, softmax layer and all layers together. Y-axis in all the graphs are in log domain, unless otherwise specified. For every model size, we have repeated the experiment 10 times, starting from different random initialization point within the proximity of origin, therefore we use violin plot to show the distribution for each data point.
Figure 5(a) shows how model accuracy varies as model size grows. On the X-axis we have model size (in million parameters) and on the Y-axis we have the best accuracy at convergence point. As depicted, increasing model size beyond 1.2 million parameters pushes the model into an over-fitting regime. Figure 5(b) shows that number of steps to convergence drops with a power law relationship within the interval of study. Training char LM with SGD optimizer is very slow and we did not run these experiments beyond 13 billion parameter models. Further study is required to see where this pattern starts to slow down. We know from Figure 2 that this pattern does not continue forever and indeed slows down and eventually stops. This implies there is a minimum number of epochs, or number of times to go through the data. Further study required to figure out if this number can go below one.
Direct Distance from Initial Point to Final Point As shown in Figure 6, the direct distance from initial weights to final weights shrinks with model size (specifically model’s width) across all layers.
This behavior is expected and can be explained theoretically (see Section B). One interpretation of this is that in higher dimensional space the number of locals minimas that are as good as global minimas exponentially increases ( Sagun et al. (2014)) and if they are not symmetrically distibuted wrt. origin where the initial point lives around, there exists a potential for the direct distance to get shorter.
A closer look at Figure 6 also reveals that
1. For narrow models, weights within softmax layer travel farther than weights within hidden layers. However, for wider models the pattern is reverse. This transition happens at 2.3 million parameters. We know from Figure 5 that models greater than 1.2 million parameters are already overfitted, therefore the fact that hidden weights travel less than softmax layer for narrow models and reverse for larger models cannot be fully contributed to the lack of capacity in hidden layers for narrow models.
2. Softmax layer benefits the most from the width increase (25% reduction for softmax vs. 15% and 13% reduction for hidden and embedding layer, respectively).
3. A curve fitting reveals a logarithmic relationship between the direct distance and model’s width. These results match with results presented in Yin et al. ’s work where they showed that number of steps to convergence has a logarithmic relationship to direct distance, if the function is γ-strongly-convex, or β-smooth and µ-Polyak-Lojasiewicz (Theorem 4 and 7).
Step Size As shown in Figure 7, average step size grows with model size. Step size is basically the norm of the gradient vector and the norm of a vector has a square root relationship with the vector length, under the assumption that data distribution per element stays unchanged. This can happens if the new weight is independent of the previous weights. If the weights are correlated, one might expect the range of the values presented within each weight gets smaller as models gets wider since the error will be amortized across more weights. Therefore the growth in norm would be lower than square root relationship in the number of weights. Another extreme case is where the extra weights do not carry any signals and the norm does not change with hidden dimension.
A closer look at Figure 7 reveals that:
1. Step size for softmax layer grows with almost square root relationship with model’s width. This indicates that weights within softmax layer are absorbing new information as model’s width grows.
2. Step size for hidden layer grows with Hidden Dimension0.21. This indicates either some of the new weights are zero or correlated with previous weights.
3. Weights within hidden layers take larger steps than weights within softmax layer and embedding layer. This can be partially contributed to larger number of weights in hidden dimension.
4. Weights within embedding layer do not show much improvement with model’s width growth (10% increase for 16.5× larger model). This implies embedding does not extract much new information from extra weights.
Misalignment Figure 8 shows how misaligned are the gradient vectors with respect to the line connecting their position in the weight space to the starting point. Precisely, it is the average of the angle specified above measured along the path traveled from the starting point to the end point. In precise term, we measure As = arccos 〈W (t)−W (0),∇F (W (t)〉 ||W (t)−W (0)||.||∇F (W (t)|| . We use this as a proxy to the measure of misalignment of the gradeint vectors with respect to the line connecting their positions in the weight space to the final point, i.e. Ae = arccos 〈W (t)−W ∗,∇F (W (t)〉 ||W ∗−W (0)||.||∇F (W (t)|| . In the extreme case, where all gradient vectors are along the path connecting starting point to the end point, we expect to have Ae = π − As. Therefore increase in As implies reduction in Ae. As depicted, angles towards the origin are in average roughly π2 and very slowly opens up as models get larger. This implies width does not affect angle alignment much and therefore, the reduction effect should come from increased step size and/or reduced distance.
A long-held conventional wisdom states that larger models train more slowly when using gradient descent. We challenge this widely-held belief, showing that larger models can potentially train
faster despite the increasing computational requirements of each training step. We study the effect of network structure on halting time and show that larger models—wider models in particular—take fewer training steps to converge. Results show that halting time improves when growing model’s width for three different applications, and the improvement comes from each factor: The distance from initialized weights to converged weights shrinks with a power-law-like relationship, the average step size grows with a power-law-like relationship, and gradient vectors become more aligned with each other during traversal.

heading: A BENCHMARKS

text:
We evaluate our finding on three established deep learning models: character-level LM, word-level LM and speech recognition. Language models (LMs) aim to predict probability distributions for the next character, word, or other textual grams conditioned on previous sequence of input text. LMs are very important model features for domains such as speech recognition and machine translation, helping to identify most probable sequences of grams. Relative to other machine learning domains, LMs have low-dimensional input and output spaces, and can be trained with very large labeled sets. Speech recognition technologies convert acoustic speech signals into text or commands. Speech recognition is used in diverse applications such as voice-powered machine controls and conversational user interfaces. Researchers have spent decades developing hand-engineered speech recognition pipelines, and recently, have shifted to end-to-end deep learning based methods that show promising results (Hannun et al. (2014); Chorowski et al. (2015); Amodei et al. (2016)). Speech recognition provides an interesting contrast to LMs as speech input data is medium-dimensionality time-series data.
Next we outline the configuration detail of each of these models.
• Word LM: We implement LSTM-based word LMs as described in Jozefowicz et al. (2016) with some small changes. To reduce the computational requirements of the models, we restrict the vocabulary to the top 10,000 most frequent words in the Billion Word Dataset (Chelba et al. (2013)). The networks are 2-layer LSTMs, with sequence length of 80, the same number of hidden nodes in each layer. We scale the number of hidden nodes to increase the model size.
• Character LM: We use character-level LMs, which uses Recurrent Highway Networks (RHNs) ( Zilly et al. (2017)). Specifically, we train a single-layer, depth 10 RHN, sequence length 150, which we found to achieve SOTA accuracy on the Billion Word data set. We scale the number of hidden nodes and depth to increase the model size.
• Speech recognition: We train a recent SOTA model Deep Speech 2 (DS2). The DS2 model (Amodei et al. (2016)) consists of two 2D convolution layers followed by four bidirectional LSTM recurrent layers. We use Adam to optimize CTC as the loss function (Graves et al. (2006)). The inputs to this model is a sequence of log-spectrograms of power normalized audio clips, calculated on 20ms windows. Outputs are the English alphabet along with the blank symbol. These speech models do not include language models for output sequence beam search. We train on shards of labeled data set comprising 11,940 hours of speech containing 8 million utterances Amodei et al. (2016). To vary the number of parameters, we vary the number of nodes in all LSTM layers, so that all layers have the same number of nodes. For the DS2 model, model sizes range between 300K to 193M parameters.

heading: B THEORETICAL RESULTS

text:
We begin with a simple example to show the effect of width on D0 – the average distance from initial weights to final weights within the weight space. For a simple linear neural network with L2 loss, we show that the increase in width results in reduction in D0.
Consider a simple case of two-layer linear neural network where the weights of second layer are assumed to be always one. Let’s also assume that the input is scalar x. This is basically same as linear regression. Let’s begin with hidden dimension one. The loss function can be formulated as follows and depicted geometrically as in Figure 9:
F (w) := 1
n n−1∑ i=0 (wxi − yi)2
Where w are the weights of the first layer. If we increase the hidden dimension to two and keep the weights of the second layer at 1, the loss function will be re-formulated as follows and depicted as in Figure 10:
F (w1, w2) := 1
n n−1∑ i=0 ((w1 + w2)xi − yi)2
For K=1, as shown in Figure 9, the best answer is a point on w-axis at distance C from origin and the initial point lies somewhere within (−R,R) interval around the origin. Therefore the average distance from initial point to final point can be formulated as follows:
1
2R ∫ C+R C−R xdx = C
For K=2, as shown in Figure 10, the best answer lies on a straight line with slope of -1 crossing w1 axis at distance C, and the initial points lies somewhere within the the disk of radius R. Starting from the initial point within the disk and moving along the direction of the gradient, the average distance from initial point to final point can be formulated as follows:
1
πR2 ∫ r=R r=0 ∫ θ=2π θ=0 ( C√ 2 − r cos θ)rdrdθ = C√ 2
As can be seen the average distance in n-dimensional space is always the projection of distance in (n− 1)-dimensional space to the gradient direction in n-dimensional space. Therefore, the average distance is always expected to be smaller than the distance in previous dimension, so reduction in average distance from start point to final point is expected.
Note that this relationship is found under so many simplifying assumptions, including the assumption that new weights do not add any additional model capacity. Therefore, best-case loss will be the same as we add parameters. Further analysis is required to generalize this observation to non-scalar input, arbitrary matrix sizes and considering non-linearity.