{'fraction_non_alphanumeric': 0.03182935466400033, 'fraction_numerical': 0.010165395992167646, 'mean_word_length': 4.727511333810546, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A General Family of Robust Stochastic Operators for Reinforcement Learning

We consider a new family of operators for reinforcement learning with the goal of alleviating the negative effects and becoming more robust to approximation or estimation errors. Various theoretical results are established, which include showing on a sample path basis that our family of operators preserve optimality and increase the action gap. Our empirical results illustrate the strong benefits of our family of operators, significantly outperforming the classical Bellman operator and recently proposed operators.


Introduction
Reinforcement learning has a rich history within the machine learning community to solve a wide variety of decision making problems in environments with unknown and unstructured dynamics. Through iterative application of a convergent operator, value-based reinforcement learning generates successive refinements of an initial value function. Q-learning [14] is a particular reinforcement learning technique in which the value iteration computations consist of evaluating the corresponding Bellman equation without a model of the environment.
While Q-learning continues to be broadly and successfully used to determine the optimal actions of an agent in reinforcement learning, the development of new Q-learning approaches that improve convergence speed, accuracy and robustness remains of great interest. One approach might be based on having the agent learn optimal actions through the use of optimality conditions which are weaker than the Bellman equation such that value iteration continues to converge to an action-value function Q associated with an optimal policy, while at the same time increasing the separation between the value function and Q-function limits. Exploiting these weaker conditions for optimality could lead to alternatives to the classical Bellman operator that improve convergence speed, accuracy and robustness in reinforcement learning, especially in the company of estimation or approximation errors.
A recent study by Bellemare et al. [3] considers the problem of identifying new alternatives to the Bellman operator based on having the new operators satisfy the properties of optimalitypreserving, namely convergence to an optimal action policy, and gap-increasing, namely convergence to a larger deviation between the Q-values of optimal actions and suboptimal actions. Here the former ensures optimality while the latter can help the learning algorithm determine the optimal actions faster, more easily, and with less errors of mislabeling suboptimal actions. The authors propose a family of operators based on two inequalities between the proposed operator and the Bellman operator, and they show that the proposed family satisfies the properties of optimality-preserving and gap-increasing. Then, after empirically demonstrating the benefits of the proposed operator, the authors [3] raise open fundamental questions with respect to the possibility of weaker conditions for optimality, the statistical efficiency of the proposed operator, and the possibility of a maximally efficient operator.
At the heart of the problem is a fundamental tradeoff between violating the preservation of optimality and increasing the action gap. Although the benefits of increasing the action gap in the presence of approximation or estimation errors are well known [8], increasing the action gap beyond a certain region in a deterministic sense can lead to violations of optimality preservation, thus resulting in value iterations that may not converge to optimal solutions. Our approach is intuitively based on the idea that the action gap can be increased beyond this region for individual value iterations as long as the overall value iterations are controlled in a probabilistic manner that ensures the preservation of optimality in a stochastic sense. In devising a family of operator endowed with these properties, we provide a more general approach that yields greater robustness to approximation or estimation errors.
In this paper we propose a general family of robust stochastic operators, which subsumes the family of operators in [3] as a strict subset, and we address many of the open fundamental questions raised in [3]. Our approach is applicable to arbitrary Q-value approximation schemes and is based on support to devalue suboptimal actions while preserving the set of optimal policies in a stochastic sense. This makes it possible to increase the action gap between the Q-values of optimal and suboptimal actions to a greater extent beyond the aforementioned deterministic region, which can be critically important in practice because of the advantages of increasing the action gap in the company of approximation or estimation errors [8]. Since the value-iteration sequence generated under our family of stochastic operators will be based on realizations of random variables, our theoretical results include establishing the fact that the random variables converge almost surely [5] to the same limit that produces the optimal actions. In addition, our theoretical results include showing that our robust stochastic operators are optimality-preserving and gap-increasing on a sample-path basis [5], establishing that our family of operators significantly broadens the set of weaker conditions for optimality over those in [3], and showing that a statistical ordering of the key components of our operators leads to a corresponding ordering of the action gaps. Key implications of these results include: the search space for the maximally efficient operator should be an infinite dimensional space of random variables, instead of the finite space alluded to in [3]; our statistical ordering results can lead to order relationships among the operators in terms of action gaps, which can in turn lead to maximally efficient operators.
We subsequently apply our robust stochastic operators to obtain empirical results for a wide variety of problems in the OpenAI Gym framework [6], and then compare these empirical results against those under both the classical Bellman operator and the consistent Bellman operator from [3]. These experimental results consistently show that our robust stochastic operators outperform both the Bellman operator and the consistent Bellman operator.

Preliminaries
We consider a standard reinforcement learning (RL) framework (see, e.g., [4]) in which a learning agent interacts with a stochastic environment. This interaction is modeled as a discrete-time discounted Markov Decision Process (MDP) given by (X, A, P, R, γ), where X is the set of states, A is the set of actions, P is the transition probability kernel, R is the reward function mapping state-action pairs to a bounded subset of R, and γ ∈ [0, 1) is the discount factor. Let Q and V denote the set of bounded real-valued functions over X × A and X, respectively. For Q ∈ Q, we define V (x) := max a Q(x, a) and use the same definition forQ ∈ Q andṼ (x), and so on. Let x always denotes the next state random variable. For the current state x in which action a is taken, i.e., (x, a) ∈ X × A, we denote by P(·|x, a) the conditional transition probability for the next state x and we define E P := E x ∼P(·|x,a) to be the expectation with respect to P(·|x, a).
A stationary policy π(·|x) : X → A defines the distribution of control actions given the current state x, which reduces to a deterministic policy when the conditional distribution renders a constant action for state x; with slight abuse of notation, we always write policy π(x). The stationary policy π induces a value function V π : X → R and an action-value function Q π : X × A → R where V π (x) := Q π (x, π(x)) defines the expected discounted cumulative reward under policy π starting in state x, and Q π satisfies the Bellman equation Our goal is to determine a policy π * that achieves the optimal value function V * (x) := sup π V π (x), ∀x ∈ X, which also produces the optimal action-value function The Bellman operator T B is known (see, e.g., [4]) to be a contraction mapping in supremum norm whose unique fixed point coincides with the optimal action-value function, namely . This in turn indicates that the optimal policy π * can be obtained by As noted by Bellemare et al. [3] and illustrated through a simple example, the optimal state-action value function obtained through the Bellman operator does not always describe the value of stationary policies. Although these nonstationary effects cause no problems when the MDP can be solved exactly, such nonstationary effects in the presence of estimation or approximation errors, which may lead to small differences between the optimal state-action value function and the suboptimal ones, can result in errors in identifying the optimal actions. To address issues of nonstationarity of this and related forms arising in practice, Bellemare et al. [3] propose the so-called consistent Bellman operator defined as where 1 {·} denotes the indicator function. The consistent Bellman operator T C preserves a local form of stationarity by redefining the action-value function Q such that, if an action a ∈ A is taken from the state x ∈ X and the next state x = x, then action a is taken again. Bellemare et al. [3] proceed to show that the consistent Bellman operator yields the optimal policy π * , and in particular T C is both optimality-preserving and gap-increasing, each of which is defined as follows.
The operator property of optimality-preserving is important because it ensures that at least one optimal action remains optimal and that suboptimal actions remain suboptimal. As suggested above, the operator property of gap-increasing is important from the perspective of robustness when the inequality (5) is strict for at least one (x, a) ∈ X × A. In particular, as the action gap of an operator increases while remaining optimality-preserving, the end result is greater robustness to approximation or estimation errors [8].

Robust Stochastic Operator
In this section we propose a general family of robust stochastic operators and then establish that this general family of operators are optimality-preserving and gap-increasing. We further show that our family of robust stochastic operators are strictly broader and more general than the family of consistent Bellman operators, while also addressing some of the fundamental open questions raised in [3] concerning weaker conditions for optimality-preserving, statistical efficiency of new operators, and maximally efficient operators. It is important to note, as also emphasized in [3], that our approach can be extended to variants of the Bellman operator such as SARSA [10], policy evaluation [11] and fitted Q-iteration [7].
For all Q 0 ∈ Q, x ∈ X, a ∈ A and {β k : k ∈ N}, a sequence of independent nonnegative random variables with finite support and expectation β : a)). Then the members of the general family of robust stochastic operators include the T β k defined over all probability distributions for the sequences {β k } with β ∈ [0, 1). Furthermore, we define T F β to be the general family of robust stochastic operators comprising all T such that there exists a sequence of {β k } and the following inequalities hold It is obvious that these are strictly weaker conditions than those identified in [3]; and since realizations of β k can clearly take on values outside of [0, 1), the family of operators T F β subsumes the family of operators identified in [3]. Our theorem establishes that the general family of robust stochastic operators are also optimality-preserving and gap-increasing. Theorem 3.1. Let T B be the Bellman operator defined in (2) and T β k the robust stochastic operator defined in (6). Considering the sequence Q k+1 := T β k Q k with Q 0 ∈ Q, the conditions of optimality-preserving and gap-increasing hold almost surely and therefore the the operator T β k is both optimality-preserving and gap-increasing almost surely. Moreover, all operators in the family T F β are optimality-preserving and gap-increasing almost surely.
Proof. We first consider aspects of the optimality-preserving properties of the family of robust stochastic operators. Since the conditions of Lemma A.1 due to Bellemare et al. [3] hold, it follows that the sequence {V k (x) : k ∈ N} converges asymptotically on a sample path basis [5] such that lim k→∞ V k (x) =Ṽ (x) ≤ V * (x), for all x ∈ X. Defining Q(x, a) := lim sup k→∞ Q k (x, a) = lim sup k→∞ T β k Q k (x, a) and applying a derivation from the proof of Theorem 2 in [3] for each sample path, we can conclude that holds almost surely [5].
Meanwhile, we have Taking conditional expectation with respect to the filtration F k = σ(β 1 , β 2 , . . . , β k ), renders Since β = E[β k ] ∈ [0, 1), we know from Lemma A.1 that Q k (x, a) converges on each sample path. Hence, for any > 0 on each sample path, we observe that Q k+1 (x, a) − Q k (x, a) < when k is sufficiently large. We therefore have, for sufficiently large k, Because is arbitrary, we can conclude that holds for large k. Taking the limit superior on both sides, we obtaiñ which in combination with (8) leads to the conclusion thatṼ (x) = V * (x) almost surely.
Next, to prove that T β k is gap-increasing, the above arguments render lim k→∞ V k (x) = V * (x) on a sample path basis, and thus (5) is equivalent to almost surely. This inequality follows on a sample path basis from T β k Q(x, a) ≤ T B Q(x, a) by definition and Lemma A.1, and therefore we have the desired result for the operators T β k . Furthermore, it can be readily verified that the above arguments can be similarly applied to cover all of the operators in T F β . Lastly, from the above results of (5) andṼ (x) = V * (x) almost surely, it follows that (4) also holds almost surely for T β k as well as all operators in T F β , thus completing the proof.
The definition of T F β and Theorem 3.1 significantly enlarges the set of optimality-preserving and gap-increasing operators identified in [3]. In particular, our new sufficient conditions for optimality-preserving operators implies that significant deviation from the Bellman operator is possible without loss of optimality. More importantly, the definition of T F β and Theorem 3.1 implies that the search space for maximally efficient operators should be an infinite dimensional space of random variables, instead of the finite dimensional space that is alluded to in [3]. We now establish results on certain statistical properties for the sequences {β k } within our general family of robust stochastic operators, which offer key relational insights into important orderings of different operators in T F β in terms of their action gaps. This can then be exploited in searching for and attempting to find maximally efficient operators in practice. Proof. The desired result can be readily seen from and The theorem concludes that a larger variance for β k in fact leads to a larger variance for Q k (x, a). We know that, in the limit, the optimal action will maintain its state-action value function. Then, when k is sufficiently large, we can expect that the state-value function for the optimal action will be very close to the optimal value. In this case, a larger variance implies that the smaller sub-optimal values will have larger probability, and thus they can be understood to have a larger action gap.
The results of Theorem 3.2 are consistent with our observations from the numerical experiments in Section 4 where the operator T β k associated with the sequence {β k } drawn from a uniform distribution outperforms the operator Tβ k associated with the constant sequence {β}.

Experimental Results
Within the general RL framework of interest, we consider a standard, yet generic, form for Q-learning so as to cover the various experimental programs examined in this section. Specifically, for all Q 0 ∈ Q, x ∈ X, a ∈ A and an operator of interest T , we consider the sequence of action-value Q-functions based on the following generic update rule: where α k is the learning rate for iteration k. Our empirical comparisons comprise the Bellman operator T B , the consistent Bellman operator T C , and instances of our family of robust stochastic operators T β k , denoted hereafter as RSO.
We conduct numerous experiments on several well-known problems using the OpenAI Gym framework [6], namely Mountain Car, Acrobot, Cart Pole and Lunar Lander. This collection of problems span a wide variety of RL examples with different characteristics, dimensions, parameters, and so on; in each case, the state space is continuous and discretized to a finite set of states. For every problem, the specific Q-learning algorithms considered are defined as in (10) where the appropriate operator of interest T B , T C or T β k is substituted for T ; at each timestep, (10) is applied to a single point of the Q-function at the current state and action. The experiments for every problem from the OpenAI Gym were run using the existing code found at [13,1] exactly as is with the sole change comprising the replacement of the Bellman operator in the code with corresponding implementations of either the consistent Bellman operator or RSO; see Appendix B for the corresponding python code. Multiple experimental trials are run for each problem, where we ensured the setting of the random starting state to be the same in each experimental trial for all three types of operators by initializing them with the same random seed. We observe that for different problems and different variants of the Q-learning algorithm, simply replacing the Bellman operator or the consistent Bellman operator with the Robust Stochastic operator generally results in improved performance.

Mountain Car
This problem is first discussed in [9]. The state vector is 2-dimensional with a total of three possible actions, and the score represents the number of timesteps needed to solve the problem. We ran 20 experimental trials over 10, 000 episodes for training, each of which consists of up to 200 steps; then the problem is solved for 1000 episodes using the policy obtained from the Q-function training. In both cases, the goal is to minimize the score. The RSO considered in each experimental trial consists of β k uniformly distributed over [0, 2).
For the training phase, Figure 1a plots the score, averaged over moving windows of 500 episodes across the 20 trials, as a function of the number of episodes. We observe that the average score under the RSO exhibits much better performance than under the Bellman operator or the consistent Bellman operator. Moreover, as can be seen from the smoothness of the curves in Figure 1a, the standard deviation is relatively small for all three operators. For the testing phase, the average score and the standard deviation of the score over the 20 experimental trials, each comprising 1000 episodes, are respectively given by: 129.93 and 32.68 for the Bellman operator; 127.58 and 30.90 for the consistent Bellman operator; and 122.70 and 7.25 for the RSO. Here we observe that both the average score and its standard deviation under the RSO exhibit better performance than under the Bellman operator or the consistent Bellman operator.

Acrobot
This problem is first discussed in [12]. The state vector is 6-dimensional with three actions possible in each state, and the score represents the number of timesteps needed to solve the problem. We ran 20 experimental trials over many episodes, with a goal of minimizing the score. The RSO considered in each experimental trial consists of β k ∼ U [0, 2).  operator. Furthermore, as can be seen from the smoothness of the curves in Figure 1b, the standard deviation is relatively small for all three operators.

Cart Pole
This problem is first discussed in [2]. The state vector is 4-dimensional with two actions possible in each state, and the score represents the number of steps where the cart pole stays upright before either falling over or going out of bounds. We ran 20 experimental trials over many episodes, each of which consists of up to 200 steps with a goal of maximizing the score. When the score is above 195, the problem is considered solved. Two RSOs are considered for each experimental trial, namely one in which β k is uniformly distributed over [0, 2) and another in which β k is fixed to be 1.0. Figure 2a plots the score, averaged over moving windows of 1000 episodes across the 20 trials, as a function of the number of episodes. A plot of the corresponding standard deviation, taken over the same number of score values, is presented in Figure 2b. We observe that both the average score and its standard deviation under the RSOs exhibit better performance than under the Bellman operator or the consistent Bellman operator. In particular, the average score over the last 100 episodes across the 20 trials is 190.92 under the RSO with β k ∼ U [0, 2) in comparison with 183.67 and 184.07 under the Bellman and consistent Bellman operators, respectively; the corresponding standard deviations of the scores are 19.44, 28.87 and 27.82 for the RSO, Bellman operator and consistent operator, respectively. We also observe that the RSO with β k ∼ U [0, 2) tends to performs better than the RSO with fixed β k = 1.0 over the sequences of episodes.

Lunar Lander
This problem is discussed in [6]. The state vector is 8-dimensional with a total of four possible actions, and the physics of the problem is known to be more difficult than the foregoing problems. The score represents the cumulative reward comprising positive points for successful degrees of landing and negative points for fuel usage and crashing. We ran 20 experimental trials over many episodes, each of which consists of up to 200 steps with a goal of maximizing the score. The RSO considered in each experimental trial consists of β k uniformly distributed over [0, 2).
For the training phase, Figure 3a plots the score, averaged over moving windows of 1000 episodes across the 20 trials, as a function of the number of episodes. We observe that the average score under the RSO exhibits better performance than under the Bellman operator or the consistent Bellman operator. Moreover, as can be seen from the smoothness of the curves in Figure 3a, the standard deviation is relatively small for all three operators. For the testing phase, the average score over the 20 experimental trials, each comprising 1000 episodes, is respectively given by: −241.94 for the Bellman operator; −188.44 for the consistent Bellman operator; and −167.51 for the RSO. (Once again, the standard deviation is comparable across all three operators.) Here we observe once again that the average score under the RSO exhibits better performance than under the Bellman operator or the consistent Bellman operator. The improved performance under the RSO can be explained by Figure 3b that shows the distribution of scores for both the RSO and the consistent Bellman operator. Here we observe that the distribution for the RSO is shifted further to the right.

Conclusions
We proposed and analyzed a new general family of robust stochastic operators for reinforcement learning, which subsumes the classical Bellman operator and a recently proposed family of operators. Our goal was to provably preserve optimality while significantly increasing the action gap, thus providing robustness with respect to approximation or estimation errors. We establish and discuss fundamental theoretical results for our general family of robust stochastic operators. In addition, our collection of empirical results -based on several well-known problems within the OpenAI Gym framework spanning a wide variety of reinforcement learning examples with diverse characteristics -consistently demonstrates and quantifies the significant performance improvements obtained with our operators over existing operators. We believe our work can lead to opportunities to find maximally efficient operators in practice.