Stability and Generalisation in Batch Reinforcement Learning
Authors: Matthew J. A. Smith
Shimon Whiteson
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement Learning
Algorithmic Stability
Generalisation
Overfitting
Target Network
Fitted TD
Off-Policy
Batch Reinforcement Learning

Abstract: Overfitting has been recently acknowledged as a key limiting factor in the capabilities of reinforcement learning algorithms, despite little theoretical characterisation. We provide a theoretical examination of overfitting in the context of batch reinforcement learning, through the fundamental relationship between algorithmic stability (Bousquet & Elisseeff, 2002)–which characterises the effect of a change at a single data point–and the generalisation gap–which quantifies overfitting. Examining a popular fitted policy evaluation method with linear value function approximation, we characterise the dynamics of overfitting in the RL context. We provide finite sample, finite time, polynomial bounds on the generalisation gap in RL. In addition, our approach applies to a class of algorithms which only partially fit to temporal difference errors, as is common in deep RL, rather than perfectly optimising at each step. As such, our results characterise an unexplored bias-variance trade-off in the frequency of target network updates. To do so, our work extends the stochastic gradient-based approach of Hardt et al. (2016) to the iterative methods more common in RL. We find that under regimes where learning requires few iterations, the expected temporal difference error over the dataset is representative of the true performance on the MDP, indicating that, as is the case in supervised learning, good generalisation in RL can be ensured through the use of algorithms that learn quickly.


Under review as a conference paper at ICLR 2022
STABILITY AND GENERALISATION IN BATCH RL
Anonymous authors
Paper under double-blind review
ABSTRACT
Overfitting has been recently acknowledged as a key limiting factor in the capabili- ties of reinforcement learning algorithms, despite little theoretical characterisation. We provide a theoretical examination of overfitting in the context of batch reinforce- ment learning. through the fundamental relationship between algorithmic stability (Bousquet& & Elisseeff 20h2) characterises the effect of a change at a single data point-and the generalisation gap-which quantifies overfitting. Examining a popular fitted policy evaluation method with linear value function approximation, we characterise the dynamics of overfitting the RL context. We provide finite sample, finite time, polynomial bounds on the generalisation gap in RI. In addition, our approach applies to a class of algorithms which only partially fit to temporal difference errors, as is common in deep RL, rather than perfectly optimising each step. As such, our results characterise an unexplored bias-variance trade-off in the frequency of target network updates. To do so, our work extends the stochas- tic gradient-basse based approach of Hardt et al. (2016) to the iterative methods more common in RL. We find that under regimes where learning requires few iterations, the expected temporal difference error over the dataset is representative of the true performance on the MDP, indicating that, is the case in supervised learning, good generalisation in RL can be ensured through the use of algorithms that learn quickly.
INTRODUCTION
A central aim of machine learning theory is to provide wort-case bounds on overfitting. However, in reinforcement learning (RL., which typically employs online learning on an unlimited stream of data and does not minimise an empirical risk, generalisation is more difficult to characterise than in the supervised lcarning case. This said, overfitting is still observed in RL settings, with various definitions of data scarcity. This work looks to characterise generalisation and overfitting in batch, off-policy RL. Batch RL has been of particular recent interest, for reasons of data efficiency, policy safety, or as component of a more complex online algorithm. Despite this, overfitting has never been directly characterised in this context. Fortunately, batch RL makes use of a limited data regime close to the ERM formulation, allowing us contribute such analysis.
Algorithmic stability (Bousquet & Elisseeff 2002) describes the change in the model Icarned by an algorithm when the data employed changed at a single point. a useful property, as it bounds the generalisation gap-the difference between error on our dataset, and the true population error. As such, if we can bound the stability of batch RL algorithm, we can also make guarantees about how prone it is to overfitting: how well the error on our dataset represents the error across the whole MDP.
Specifically, this work formulates an distribbutioon notion of uniform stability (Bousquet & Elisseeff 2002), suitable for batch policy evaluation algorithms. We show the relationship between this variant of stability and an off-policy generalisation gap. This allows us to characterise overfitting in batch RI. via stability, answering the question: when can expect batch RL algorithm to generalise well? This framework is then applied to a partially fitted variant of temporal difference (TD) learning, that bridges the gap between fitted and traditional TD methods. Importantly, realisability assumptions about the ability of the function class to fit values are needed.
The iterative, partially fitted batch method employed here means that our result characterises the use of target networks (Mnih et al. 2015), common in deep RL algorithms. Our bound expresses a bias-variance trade-off in the number of steps taken between updates of the target network-as more

---

Under review as a conference paper at ICLR 2022
steps taken, less data is incorporated into the update dynamics, leading higher variance, but lower bias procedure, as the value targets are also less correlated with the value parameters.
2 RELATED WORK
Our work builds directly on the results of HHrdd et al. (2016), which establishes stability bounds for stochastic gradient methods in non-convex optimisation settings. That work in turn builds on algorithmic stability, a topic in learning theory that characterises the generalisation gap in a manner agnostic to model capacity (Rogers & Wagner 1978 Devroye & Wagner 1979 Boouquue & Elisseeff 2002).
Bounds for batch RL have seen significant recent interest, especially for linearly parameterised value estimators. Existing bounds in this setting study generalisation by directly bounding the suboptimality of value function estimators, rather than the generalisation gap. Most relevant here is the work of Duan & Wang (2020), where tight upper bounds on finite time regret are given for linear value function approximators applied to fitted off-policy evaluation, but restricted to the Enite-horizon RI. problem, where data can be separated into specific trajectories, and under function approximation class that is closed under Bellman backups. Faan al. (2020) provides generalisation bounds in deep RL with use of target network but these are capacity dependent and do not characterise partial fitting. Other key bounds for batch fitted methods include those of Murphy| (2005); Antos al. (007); Munos & Szepesvári (2008); Tosatto et al. (2017), though settings and assumptions differ from those used here. Zhang et al. (2021) also characterise the convergence properties of a target network used with linear function approximation.
Furthermore, exponential worst-case lower bounds have been constructed for batch RL., Chen & Jiang (2019) show that concentration assumptions needed for polynomial-time time learning without strong assumptions on the function approximation class. Zanette (2021); Wang et al. (2020); Amortila al. (2200) provide exponential lower bounds for batch RL with only realizability and coverage assumptions. Wang et al. (202T) investigate these lower bounds empirically for fitted Q-iteration, and provides upper bounds using either realizability, or strong concentration assumptions.
Direct characterisation of overfitting in RL has seen more interest recently, though the vast majority of work thus far is empirical. To our knowlege, WWng al. (2019) provide the only theoretical characterisation of the generalisation gap beyond this work, though it applies in the online setting, depends on the model complexity, and makes the restrictive assumption that the reparameterization trick (Kingma& & Welling 2013) can be applied to the random variables of the MDP, [Francois- ct al. (2019) characterise overfitting asymptotically for batch RL as applied to partially observable Markov decision processes with finite observation, state, and action spaces. Empirical characterisation of overfitting in RL across several settings can be found in Zhang et al. (2018a). Zhang et al. (2018b); Cobbe et al. (2019). and Packer et al. (2019).
PRELIMINARIES
We consider the infinite horizon discounted RL setting. The agent interacts with an environment, formalised as a Markov Decision Process, M with (potentially infinite) state space S, a finite action space A. transition kernel P S x A x S + 10, bounded stochastic reward kernel R: S x A + P(-rmarr Mm where P(a, b) is a probability distribution with bounded support on the interval [a, b) and scalar discount factor 7 E [0. The agent's behaviour determined by policy that maps a state to a distribution over actions: pi S x A + [0, 1]. We seek to optimise (in the control case), or estimate (in the policy evaluation case) the expected discounted sum of future rewards starting from a given state. This quantity is given by the state value function,
V(S)= = EAE (S, (S, A), with Q S A + [-Tmaz/[ - >)), Tmaz/ - 7)], the action value function, given recursively through the Bellman equation:
Q(S, A) = F(S, A) - P.S.. [Q(S", A())
(1)
where F(S, A) is the mean reward sampled from the reward kemnel. The Bellman operator " projects functions forwards by one step through the dynamics of the MDP:
(Q) A) F(S, A) EI P(S.AA (EA' [Q(S", A')]]
(2)
2

---

Under review as a conference paper at ICLR 2022
T is y-contractive mapping and thus has fixed point. The fixed point of this operator corresponds to the true value of the policy in question (Puterman) 2014). We make use of a feature mapping to encode states and actions, S x x R.. When estimating MDP values, we employ parameterised value functions with a linear approximation: (w( A)) = & (S, A)w.
3.1 BATCH RL
In batch RL, rather than interacting directly with the MDP, the algorithm is given fixed dataset, with samples drawn from the transition and reward kernels of the MDP. The agent uses these samples estimate either the value of fixed target policy æ, or lear an optimal policy, R.. Usually, the acteon distribution induced by the target policy differs from that of the dataset, so batch RI. is generally viewed as an extreme case off-policy RI., in which additional data cannot be generated from any policy. In this paper, we focus on off-policy evaluation, leaving control to future work.
Fitted temporal difference methods are class of batch RL algorithms that iteratively fix a target estimator for the value function, y S x A + I, and then minimise the mean squared empirical Bellman error (MSBE) of a separate estimator, fw S x A R, over batch of data:
min(J 7 Tg(s;,
(3)
D
where T is the pointwise empirical Bellman operator:
7"t (Q)(S,A) = r ? Σ T T(A1)))((""
(4)
A1'
and and S' are sampled by taking action in state S. Once the minimum is attained, g is updated to match fw- This procedure repeats until convergence.
In practice, particularly when using neural networks, the minimiser of (3) cannot be found in closed form. Furthermore, it may be too computationally expensive, or undesirable from the perspective of learning dynamics, to reach this optimum. Instead, partial optimisation performed: few updates of an iterative optimisation procedure often suffice. We summarise this process using linear function approximation and expected SARSA as our off off-policy estimator of the Bellman error Algorithm)
Algorithm 1 Partially Fitted Linear Expected SARSA
Input: D Dp, learning rate a, target policy æ
Output: value parameters
1: initialize value parameters wio
2: for epoch O,.... N do
3: fix の = W.K
4: sample minibatch of size K, = ((,
5: for update h = 1,... K do
6:
ik
7: (u(w) (6 Ax) J w Ra- En + A') AT)
8: Wi = w + a Su, A Am)du (w)=1)
9: end for
10: project w = argmin | W || w/l
11: end for
12: return Wt
Algorithm also includes projection step for the purposes of the theory in Section 4 After each epoch i, the value parameters, w are projected to a closed ball of fixed radius. This prevents the step sizes from growing too quickly, as update rule is non-Lipschitz for unbounded parameter spaces.
By varying the hyperparameters of Algorithm] we move between traditional and fitted temporal difference algorithms. If the minimiser of (3) exists. setting K large enough allow for convergence recovers fitted expected SARSA, while setting K = 1 recovers expected SARSA applied to the uniform distribution over data.
3

---

Under review as a conference paper at ICLR 2022
Update Rules and Parameterisation One challenge that arises when treating the stability of Algorithm [ comes from the fact that we need to reason over the behaviour two separate sets of purameters-boote the value and target parameters affect the update rule. In order to manage this, we propose a unified parameterisation for which we maintain a single set of parameters, v which combines the value parameters and the frozen ones:
With this setup we need to use two update rules that operate on the same set of parameters. The parameter fitting update is given by:
G(i)s,a,, い |
a)
--r-2-
- E a')
(5)
Where is the zero vector in dimensions. This is identical to performing the fitted TD update on w and does not alter the value of w. When we need to update the frozen parameters, we simply use an assignment:
w
((w)
(6)
This setup allows update rules to depend only on the data being used to perform that update, rather than having an implicit dependency on previous updates, due to the fact that there are two sets of parameters being maintained.
3.2 ALGORITIMICC STABILITY
While most learning theory characterises generalisation performance as a function of the complexity of the model class, algorithmic stability (Bousquet & Elisseeff (2002) uses the statistical properties of the learning algorithm itself to provide bounds on generalisation.
Let Ω the space of all data points, and let W the class of models that we are learning over. Let 'D be probability distribution over Ω. In general, a (stochastic) machine learning algorithm A maps a sampled dataset of size n, D = X1, Xn X, ~ D to model, w E W with the aim of minimising scalar loss function (risk), / W Ω I. over the population:
R(w)r E (e>D(((w;;)))
(7)
Generally, we only have access to the data in the dataset, and thus cannot optimize 7 directly; instead optimise the empirical counterpart:
Σ ((A(D):.). (emp(((()) (A(D)) = [
(
RED
However, 8 can be optimised by memorising D and guessing randomly for other data, leading to
overfitring and poor performance of A(D) on 7 An algorithm overfits if is low while ( high,
i.e. it has high expected generalisation gap:
G(A)p = ED-P.A Remp (A(D)) R(A(D)))))
(9)
Small ((AA) implies that minimising Remp is a reasonable way to minimise Rp.
In supervised learning, there is intimate connection between the generalization gap and stability (Devroye & Wagner 1179). the sensitivity of an algorithm to small perturbations in the data set. Intuitively, suppose
fix learning algorithm's 's randomness, then apply it to two datasets that differ at exactly one point. If the algorithm outputs two similar models that yield similar loss, then the algorithm is stable and generalises well. While many forms of stability have been investigated, the simplest and most popular is uniform stability (Bousquet & Elisseeff 2002) An algorithm is e-uniformly stable if satisfies:
sup EAll(A(DUz), -
3,0,0'
4

---

Under review as a conference paper at ICLR 2022
where, 2, 2, and z' are all data points. The expectation is taken over algorithmic randomness. The idea is to bound the worst case difference in losses we apply the same algorithm to datasets that differ at exactly one point. In supervised learning, the expected generalization gap of algorithm bounded by its stability, i.e., if A c-uniformly stable, then G(A)D S (Bousquet & Elisseeff 2002).
STABILITY AND GENERALISATION IN BATCH RL
In this section, we characterise the propensity of Algorithm for overfitting. To do so, first we develop novel off-distribution notion of uniform stability. Then, we characterise the deviation of our model parameters (and thus the loss) when Algorithm [ applied to a perturbed dataset, as opposed to the original data. To do so, we bound this gap recursively as is done by Hardt et al. (206), with key adaptations to handle correlated updates and nonstationary objectives. As more parameter updates of the algorithm are performed, the effects of the changed data point compound and its stability declines.
To bound the distance between our two sets of parameters, we introduce some relevant assumptions:
Assumption @ maps a compact set in R.,, and uniformly bounded, with ||ø|| S Φmar-
The assumption of bounded features is common in the literature (Munos & Szepesvári 2008) and in general can be satisfied by scaling features without loss of generality.
4.1 OFF-DISTRIBUTEE ALGORITHMIC STABILITY
Due to the off-policy nature of batch RL, the notion of uniform stability cannot be directly applied. While we fit our value function over fixed data distribution, interested in the loss over the target distribution D'. Formally, we want to optimise:
R(A(D)) D~
(10)
Therefore, we employ an off-distribution generalisation gap, which compares expected empirical regret to the population regret of the output model with respect distribution other that from which the training data was sampled:
(AA D, D') EADD-D (eep(((D)) - R(A(D))
(1I)
This quantity characterizes how overfit our algorithm is to our dataset, relative to our expected performance on the targer data distribution.
In order to bound the off-distribution generalisation gap, we introduce a new notion of stability:
Definition (Uniform Off-Distribution Stability) An algorithm A e-uniformly off- distributionally stable with source DD and targel D' distributions, if D and D' share support
and:
EA (AA(DU))) - Po P Se Pp(=)
sup 8.8,2'
(12)
This definition is similar to uniform stability but one of the losses is corrected with the ratio of the probabilities of the test point, under target and source distributions. While importance sampling methods appear frequently in RL (Precupl 2000), this ratio particularly resembles the one treated marginalised importance sampling methods (Xie et al. 2019), which perform policy evaluation by directly estimating this ratio, where D is the (potentially mixed) data distribution, and D' is the steady state distribution induced by the target policy.
Crucially, the relationship between uniform off-distribution stability and the off-distribution gen- eralisation gap identical to that between uniform stability and the on-distribution generalisation gap:
Lemma If an algorithm A is e-uniformly off-distribution stable shared support, then:
for distributions D and D'' with
G(A,D,D') S.
5

---

Under review as a conference paper at ICLR 2022
The proof of Lemmal found in the appendix, closely follows the proof for the supervised setting, with the probability ratio introduced to correct for distribution shift. However, this ratio is problematic, as it can grow large if likely event under D' is unlikely under D. While it does not depend product of ratios like return-based importance sampling methods do (Munos et al. (016). it can grow unboundedly. As such, make additional assumption bounding the ratio.
Assumption The density ratio in
T2 is bounded from above:
PD (3) sup (=
S Pmaxx
This is the weakest form of a "low distributional shift" assumption that is common in the literature (Munos Szepesvári 2008 Fan et al. 2020, Wang et al.) 2019). Chen & Jiang (2019) demonstrate that this assumption is necessary for polynomial learning guarantees absent strict assumptions on function approximation class. our context, it ensures that our choice distributions does not already ensure overfitting, by concentrating the data that we are learning on in regions of the MDP that are not relevant to the target distribution.
4.2 LINEAR PARTIALLY FITTED EXPECTED SARSA IS --EXPANSIVEE
Given the smoothness of our linear function approximators, to bound the uniform off-distribution stability and thus bound the generalisation gap, we only need to bound the difference between the parameters of two models encountering datasets that differ at point. Since our algorithm is iterative we can bound this gap recursively. This gives rise to one of two cases: the data points encountered by the models different, the losses different and the parameters diverge; if the data encountered by our two models is the same, the update still may increase the distance between their parameters, since the initial parameters differ. We defer bounding of the first case divergence Section 4.3 In this section, we bound the second case using the notion of p-expansivity. An update θ is expaassivve if:
rule, G
[[ - G(w)l
sup v
S E1 < xC.
The following lemma describes the expansivity of the TD update rule given by (5) in the inner loop of Algorithm[] I It will be applied whenever update is performed on data that does not correspond to the perturbed point.
Lemma Under Assumption reexpansive, with:
i and the additional projection step, the update rule G(ū)x x is
n $ 1 &
(13)
The proof, found in the appendix, follows directly from the definition of expansivity. Our choice of parameterisation allows the update to depend only on the current data point, rather than all previous data points the epoch. It means that once the parameters of our algorithms are no longer the same, we can still provide a tight bound on how much further they become on subsequent updates that use the same data.
4.3 LINEAR PARTIALLY FITTED EXPECTED SARSA IS G-BOUNDED
When the two algorithm rollouts encounter the data point that differs between them, the update rules used for each model is different, so we cannot use 7-expansivity to govern the parameter gap. this situation, employ the worst case gap, which simply limits the size of steps in parameter space. An update rule is o-bounded if:
sup |[G(w) - wil S wEW
Thanks to the projection step, updates cannot grow without bound. However, the magnitude of the update can depend exponentially on the number of steps taken since the last projection.

---

Under review as a conference paper at ICLR 2022
Lemma 3 Under Assumption 1 for finite integers i and p. and the additional projection step, the update rule G(w)xe Xx is o-bounded, with:
S axmmar ((1 + D) Wmar -Tmaa)
(ard mao + 1)*
(14)
The proof is found in the appendix. While this bound is highly pessimistic, and thus exponential in k, in practice algorithms typically employ only a few updates between batches. This acts as a Lipschitz-style constant, uniformly bounding the size of the parameter update step. This is possible because at the start of every epoch, the parameters are bounded by ||w|| I Wmaz- When K finite, since only finite number of finitely sized steps taken, there exists second ball beyond which the parameters never reach. Since feature vectors are bounded and the TD error is finite for bounded R. W, and σ, we can compute this effective upper limit on step sizes. Because the parameters cannot take arbitrarily big steps, when the algorithm (infrequently) encounters the data point that has been changed, we can provide a limit on how far the parameters of the algorithm will move.
The dependence on K here suggests that, when the target network parameters are updated infrequently, step sizes can increase. Later we will see that this increase in step size makes the algorithm more sensitive to the data encountered, potentially leading to an increase in overfitting.
4.4 LINEAR PARTIALLY FITTED EXPECTED SARSA IS UNIFORMLY STABLE
Using the boundedness and expansivity properties of our update rule, we proceed main result:
Theorem Under Assumptions | under supremum norm) and and d the projection step applied under supremum norm, for monotonically decreasing ar q. after T =NK updates, Algorithm I e-uniformly off dittiiittibulilaalyy stable, with:
é S (1 (1-Pan ((1 + )dddman Wmaz + )max)² )2 + Pmaz E,
(15)
where:
E = ((1 + 7d man
mon Wmas + T Tmax)
2dc PEFI
1
Be
(2Mvdle)
3o01 TOtiI
[
1
and:
M = (d (1 + 2 u Wman + vd2(1 + 7) mmaaTmax)
and:
= Ømaz (11+))mmal Wma + Tmax) (ar max + 1) K
and:
B = + +7+ 2
The full proof of Theorem I can be found in the appendix, though we sketch relevant details here. First, by the effective boundedness of both our loss function and the ratio p, we have (41 -pl2) = (1-p)le p-p]11 + p(1 - 12) S sc. Noting that this primarily depends on the gap between our (uncorrected) loss functions. As such we proceed by bounding the expected gap between the squared Bellman errors of our two parallel algorithms. We use a hitting time argument, which suggests the perturbed data point is unlikely to be encountered early, the sets of parameters will not diverge until the step size has significantly decayed. This gives rise to a key lemma in the proof of Theorem [
Lemma 4 Let wi and wi be the output from running Algorithm I on our original dataset, and the perturbed datasel respectively, with algorithm randomness held constant across both runs. Let G represent the parameter gap in supremum norm at time L: |w;, - w/] oc- Then, under Assumption 7 with supremum norm, and using supremum norm for the projection step. for every to E {1,,..., D) Ω we have:
2ta D
E ( ()
((1+7) (d07)ddmmaa Wman +rmaa) )2 P+M MM dE (T = 0).
(16)
7

---

Under review as a conference paper at ICLR 2022
This lemma is similar to Lemma 3.11 of Hardt et al. (2016), with several modifications for our setting. The first term is the worst-case loss gap. representing the situation where the perturbed point is encountered before to. The second term gives the loss gap at time T in the event that the parameters have not yet diverged by time In, as the data encountered by the two instances of the algorithm has been the same up that point.
The use of the supremum norm is unconventional here. We do this because under the supremum norm, the target network update is nonexpansive. While this leads dependence on the dimension of the state space, it allows us to manage what would otherwise become a quickly intractable dependence on data previously encountered in the epoch.
Once Lemma iis established, all that remains is to bound the parameter gap, which we can do using our expansivity and boundedness rules from above. These rules allow us to recursively bound the gap at time T as function of fo. using the expansivity rule for when each set of parameters encounters the same data, and the boundedness rule for when the parameter sets encounter the perturbed data point. We then minimize for to. and the proof is complete.
This result implies that Algorithm | does not overfit arbitrarily, despite the non-convexity of the overall optimisation problem. While our bound may become loose beyond the trivial bound for high T. for certain parameter regimes, and after few time steps, we can provide meaningful guarantees on generalisation, allowing us to ensure that performance the MDP is not too much worse than the performance on our batch of data. This means that under certain conditions, we can be confident that our policy evaluation is accurate.
Bias-variance tradeoff of target network. Another key insight here is the bias-variance tradeoff that our result demonstrates in K. While target networks are common in practice, they have never been analysed in the partial fitting setting used here, which allows us to compare the use of the target network with traditional TD methods. is well-known (see, e.g. Fan et al. (2020)) that application of (5) with K- = 1 does not correspond with optimisation of the MSBE, but rather a biased version, given by:
E. [MSBF(w;; =)] + B Va (''s',a)"Te
(17)
While if K is taken to infinity, we recover the "minimax" formulation for fitted policy evaluation. which does optimise the MSBE (Zhang et al. (022). As such, we can interpret the exponential dependence of our bound on K as describing bars-variance tradeoff, where for low K, we optimise biased objective but with less variance and thus increased stability. On the other hand, for large K, step sizes increase, and thus so does the dependency on the data, but we recover an unbiased objective.
While our bound provides unique characterisation of overfitting in batch RL, it suffers limitations in its applicability well. As a bound in expectation, it is significantly weaker than a high-probaben bound. In this respect. it suffers from the same challenges that prevent application of concentration inequalities discussed by Hardt al. (016)).
EMPIRICAL RESULTS
While the main goal of this paper to establish the theoretical results presented above, we also present some empirical results in this section. In order to verify that our worst-case analysis holds true in practice, we examine the effects of varying the parameters of Fitted Linear Expected SARSA
(Alg M on noisy variant of the episodic Boyan chain environment (Boyan 2002).
The first state in the chain is given by the axis-aligned unit vector 0, 0, 0). Advancing along the chain involves interpolation between subsequent single-componet vectors, with the next component increasing by 0.25 for each state advanced, and decreasing the previous by the same. The agent can either move one state ahead or two, save for the second to last state, in which the agent must advance one. our variant, in order to examine the effects of overfitting, we add mean-zero noise to both the transition and reward functions. Centered Gaussian noise is added to the rewards and uniform noise in (-0.125, 0.125) to each state. We use bounded uniform noise to prevent state aliasing and thus maintain the Markov property. In order to allow for multiple solutions and more possibility of overfitting, we augment the state space with polynomial features up to degree four. Our target policy selects uniformly between moving ahead one state and moving ahead two states, while the dataset
8

---

Under review as a conference paper at ICLR 2022
Figure I: Results of empirical investigation of stability. Increasing the number of iterations per epoch and increasing the divergence between the sampling and the target distribution significantly decrease stability and thus generalisation.
undersamples states where the first component is nonzero. This is extreme case, the sampling distribution does not even correspond to policy, since the initial state is undersampled as well.
The most important parameters in bound are the number of steps taken between epochs, k, and upper bound of the off-policy coefficient, Pmaz, which trades off between our vacuous upper bound, and the dearning-dependerr one. Running fitted linear expected SARSA datasets with one point changed between rollouts, and randomness held constant, we investigate the effects of varying these parameters on various empirical proxies for the stability: namely the parameter gap (/w- w')), the Bellman error gap a held out test set sampled from the target policy (E]/MSBE(wr;
identical
MSBE(wt 2)), and the gap between statewise true errors, where ([T ((w) - (ww' (w))), where
TE(w)= =
(b(s,a)T w Qr(s,a))² S.A
and the sum is taken over the true states, without noise added. While these are all computed in expectation rather than supremum, they give indications as to how varying relevant parameters can influence the stability of the algorithm. Each configuration is run for 5000 parameter updates. The results of the experiment appear in Fig. I Experiments were repeated over 500 random seeds, with lines representing the mean gap and shaded areas give standard error. We find that, reflected in the bound's ' dependence on T, until convergence, across all runs, the parameter gap increases with the number of updates. Furthermore, depencence on k; increasing the number of iterations per epoch leads to an increase in overfitting, where divergence of parameters, MSBE, and TE are all higher than when fewer iterations used. Finally, we find that increasing the degree to which the data is sampled off- leads similarly to an increase in overfitting, which though smaller in terms of parameter divergence, leads comparable instability as the increased number of iterations.
find that in correspondence with the bound's exponential
CONCLUSIONS
We have provided a finite update bound on generalisation in the batch RL context for fitted TD methods. In doing so, we have established an off-distribution formulation of algorithmic stability and directly characterised overfitting in fitted TD methods. Furthermore, we have shed new light on a bias-variance tradeoff in the frequency of updates of the target network. In future, look to find high-probability bounds rather than bounds in expectation, as well as investigate the generalisation properties of control algorithms.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Philip Amortila, Nan Jiang, and Tengyang Xie. A variant of the wang-foster-kakade lower bound for the discounted setting, arXiv preprint arXiv:2011.01075, 2020.
András Antos, Rémi Munos, and Csaba Szepesvári. Fitted q-iteration continuous action-space mdps. 2007.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-528 526,526622202 2002.
Justin A Boyan. Technical update: Least-squares temporal difference learning. Machine learning, 49 (2):233-24) 246, 2002.
Jinglin Chen and Nan Jiang. Information-theoreti considerations in batch reinforcement learning, 2019.
Karl Cobbe, Oleg Klimov, Chris Hesse, Tachoon Kim, and John Schulman. Quantifying generalization in reinforcement learning, 2019.
Luc Devroye and Terry Wagner. Distribation-free inequalities for the deleted and holdout error estimates. IEEE Transactions on Information Theory, 25(2):202-277, 1979.
Yaqi Duan and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approxi- mation, 2020.
Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning, 2020.
Vincent Francois-Lavet, Guillaume Rabusseau, Joelle Pineau, Damien Ernst, and Raphael Fonteneau. On overfitting and asymptotic bias in batch reinforcement learning with partial observability, 2019.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234. PMLR, 2016.
Diederik P Kingma and Max Welling. arXiv:1312.6114 2013.
Auto-encoding variational bayes.
arXiv preprint
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning, nature, 51 518(7540):529-55 553-533, 2015.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008
Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Mare G. Bellemare. Safe and efficient off-policy reinforcement learning, 2016.
Susan A Murphy, A generalization error for q-learning. 2005.
Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song. Assessing generalization in deep reinforcement learning, 2019.
Doina Precup. Eligibility traces for off- off-policy policy evaluation. Computer Science Department Faculty Publication Series, pp. 80, 2000.
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John
Wiley & Sons, 2014.
W. Rogers and T. J. Wagner. Finite Sample Distribution-Free Performance Bound for Local Discrimination Rules. The Annals of Statistics, 6(3):506 514, 1978. doi: 10. 176344196. URL https::/
Samuele Tosatto, Mattco Pirotta, Carlo Eramo, and Marcello Restelli. Boosted fitted q-iteration. In International Conference Machine Learning, pp. 3434-3443, PMLR, 2017.
10

---

Under review as a conference paper at ICLR 2022
Huan Wang, Stephan Zheng, Caiming Xiong, and Richard Socher. On the generalization gap in reparameterizable reinforcement learning, 2019.
Ruosong Wang, Dean P. Foster, and Sham M. Kakade. What are the statistical limits of offline rl with linear function approximation?, 2020.
Ruosong Wang, Yifan Wu, Ruslan Salakhutdinov, and Sham M. Kakade. Instabilities of offline with pre-trained neural representation, 2021.
Tengyang Xie, Yifei Ma, and Yu-X Yu-Xiang Wang. Towards optimal off-policy evaluation for rein- forcement learning with marginalized importance sampling. arXiv preprint 19XXiv1906.0330 2019.
Andrea Zanette. Exponential lower bounds for batch reinforcement learning: Batch rl can be exponentially harder than online rl, 2021.
Amy Zhang, Nicolas Ballas, and Joelle Pineau. A dissection of overfitting and generalization in continuous reinforcement learning, 2018a.
Chiyuan Zhang, Oriol Vinyals, Remi Munos, and Samy Bengio. study on overfitting in deep reinforcement learning, 2018b.
Shangtong Zhang, Hengshuai Yao, and Shimon Whiteson. Breaking the deadly triad with target network, 2021.


Reviews:
[{"review_id": "cAJPZ47x2Z8", "reviewer": "Reviewer_P8Es", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is firstly poorly written and it makes it very difficult to understand the setting of the problem, nature of the algorithm and the result and identify the correctness or implications of the final results. More importantly, the authors discuss the results as 'first' results on overfitting stating that \"overfitting has never been directly characterised in this context\". This is highly misleading as there is a substantial literature on understanding the necessary and sufficient conditions on the sample complexity of batch RL under varying assumptions on the data distribution, approximation power and statistical complexity of the value function/model class and algorithmic schemes. Various important quantities and the relevant expressions, thereof, are not well defined or not defined altogether at various places. Please see below for more details.\n\n**Problem setting**: The paper studies the batch RL problem of offline policy evaluation for a discounted MDP when the data has been collected using a distribution $\\mathcal{D}$. The authors study a value function based approach where the value function class is a set of linear functions of the state action features $\\phi(s,a)$. The algorithm (Partially fitted linear expected SARSA) can be summarised as follows:\n\n1. The algorithm runs in epochs where the two sets of linear value functions are maintained: $\\phi \\cdot w$ and $\\phi \\cdot \\bar w$ where the latter plays the role of a target function.\n2. In each epoch, the agent makes updates to the parameter $w$ by using gradient updates over $K$ transition tuples and the loss function: $\\left( f_w(s,a) - r - \\gamma E_{a' \\sim \\pi}[f_{\\bar w}(s',a')] \\right)^2$.\n3. Projects the updated parameters $w$ onto a bounded ball and in the next epoch updates the target network to $\\bar w = w$.\n\n**Technical issues:** Now, this is where the details start to get murky. This is clearly an iterative algorithm which is performing a version of sample fitted value iteration. The only difference here from the well studied fitted policy evaluation problem (FPE) (see Le et al, 2019) is that the target network for the next epoch is updated only after partially minimizing the Bellman error instead of the full update in the usual case. This is what the authors refer to as 'partially fitted'. However, then the authors simply view this as a stochastic gradient update to a fixed objective and go on to study the stability properties of this SG method. The technical tools and proof approach used here is basedf on the paper by Hardt et al (2016) which analyzed the stability and generalization properties of stochastic gradient method for convex, strongly convex and non-convex losses. The main loss function which the authors study, the MSBE quantity, is never mentioned in the main paper or in the appendix. It is not clear as to how the authors view this as a single optimization objective and therefore, it is not clear as to what 'generalization' or 'overfitting' aspect is studied in the paper. In my initial reading, because of the strong optimization connection, I had expected an analysis of a residual Bellman error based method which actually minimizes a fixed objective instead of the iterative template of FQE.\n\nSince the authors clearly have two steps of updating the target network as well as the main Q function, how is it equivalent to minimizing a mean-squared Bellman error (MSBE). Further, in the empirical loss written in the paper in eq 3, the expectation of the loss will not be equivalent to the desired Bellman error anyway. This has to do with the excess variance term which the authors mention later in the text. Therefore, how is the theory of ERM directly applied here without having a direct sum of decomposable loss function to begin with? \n\nIn the update rules and parameterization paragraph, the authors discuss the update $G(w)$ in detail, but how does $\\hat G(w)$ factor into the analysis? I'm assuming one cannot simply ignore that in the stability bounds. The changes in magnitude of parameter changes in $w$ are discussed in the analysis, but the target network update is completely ignored. Hence, it will be helpful to expand on the whole setup and the exact reduction to the stochastic loss minimization setting in detail and then discuss how the tools from stability and generalization of ERM can be used. Along the same lines, clarifying the complete details of where smoothness is assumed (start of section 4.2), random permutation vs random sampling protocol for training, effect of K on the magnitude of parameter updates among other things seems necessary. \n\nThe above mismatch is evidently clear at many places where the authors simply lift the interpretation of results from Hardt et al in their setting. For instance, the authors use the following statement in their discussion in section 4.4: \"ms. We use a hitting time argument, which suggests the perturbed data point is unlikely to be encountered early, so the sets of parameters will not diverge until the step size has significantly decayed\". While the first part is true that for two datasets, the probability of the algorithm encountering the changed datapoint is proportional to $1/|D|$, the second does not make any sense in the paper's setting. For the Hardt paper, the discussion was in the context of SGM for non-convex losses with decreasing step sizes $\\alpha_t = c/t$. However, for the iterative algorithm studied in this setting, having a decreasing sequence of step sizes can be counterproductive as the Bellman error for later target functions will not decrease and is antithetic to the underlying dynamic programming principle. Also, in the proof of Lemma 4, the last para says that $M$ comes from the definition of MSBE, which again is not defined anywhere.\n\nOverall, I would recommend the authors to review the current version and carefully see what is the exact reduction to ERM that the authors are studying. If the loss function is not fixed, the studied analysis approach cannot be directly used and more caution is required. In my opinion, a Bellman residual error minimization setting (Antos et al, 2008) will be more relevant here and can be studied with the two phase update scheme in Algorithm 1. In the current version, the setting does not seem plausible for a reduction to ERM and I'm therefore not sure of the correctness of the results/claims.\n\n**Specific comments**:\n1. A more thorough and detailed literature review is required. As mentioned, generalization and overfitting of policy evaluation is actually well studied in literature starting from the finite sample based fitted value iteration schemes to FQE, DICE style methods in the literature. \n2. In the references section, the citations are not proper as complete reference to publication venue and details are not included.\n3. \"No realizability assumptions on the ability of function class to fit values are needed\": This is a wrong interpretation as the accuracy of any fitted evaluation procedure *will depend* on the approximation power of the value function class. Using a stability based analysis is helpful because it allows one to circumvent the uniform convergence argument and no assumption on the structural complexity of the function class are required. \n4. In the first two pages, partial fitting is mentioned without any explanation, and therefore, it is hard to understand what it actually means.\n5. Section 3, pg 2: \"distribution over actions: \\pi\": \\pi instead of pi.\n6. Section 3.1: Significant updates required. Define MSBE, discuss how this is equivalent to ERM and how it connects to the stability analysis in Hardt et al.\n7. Algorithm 1: line 7,10: t index is missing. \n8. Paragraph right after algorithm 1: \"...s. This prevents the step sizes from growing too quick...\" $\\alpha$ is step size not the whole update?\n9. Instead of fitted expected SARSA, refer to this as FQE as used in previous works.\n10. Section 3.2: More context is needed here as to how Algorithm 1 connects to this. Simply using a sample based minimization doesn't mean that it directly reduces to the same setting.\n11. Assumption 2: It is one of the strongest assumptions used in the literature as it directly makes the assumption on a per-state basis. Refer to Chen and Jiang 2019 for more details.\n12. Section 4.2: What is smoothness here for the linear function approximators?\n13. Theorem 1: Whatever generalization the result implies, the implications of the value of k seem unclear. Is it correct to notice that keeping $K=1$ is the best possible bound? If true, what is the bias-variance tradeoff?\n14. Again, in this section, various references to structure of the optimization problems are made, but the optimization problem itself is unclear.\n15. In appendix, what does the subscript $X_{0:k}$ means at different places? The steps don't seem to use $k$ anywhere in certain proofs.\n16. A full and detailed proof for Theorem 1 would have cleared the paper for both the authors and the reader. Flushing out the whole detailed proof will be helpful. \n\n\n**References**\nLe, Hoang, Cameron Voloshin, and Yisong Yue. \"Batch policy learning under constraints.\" International Conference on Machine Learning. PMLR, 2019.", "summary_of_the_paper": "The paper aims to study the effect of stability on generalization of a particular off-policy policy evaluation algorithm. Specifically, the authors study a version of Fitted Q-evaluation where the iterative procedure is instead thought of as a gradient update and is performed by only partially fitting the new Q-function to the current target Q function. The authors look at a linear function approximation setting and connect the recent results on stability of stochastic gradient methods (Hardt et al, 2016) with their method and show stability results, and connect that with overfitting of the policy evaluation scheme. The authors discuss the effect of the number of updates performed in each epoch during the partially fitted linear-update scheme and further show empirical simulations.", "summary_of_the_review": "The paper attempts to connect an iterative fitted policy evaluation method with stability based generalization bound analysis of stochastic minimization algorithms. However, the reduction to a fixed risk measure for the partially fitted procedure is not discussed and is likely not applicable in this setting. Hence, the analysis, claims and connections of the proposed algorithm and stability of ERM are not clear in this paper. Further, various key quantities are not defined in the paper and therefore are not adequately discussed in the formal analysis. As such, I feel that this paper is not ready for publication and needs a significant and detailed revision.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TFJbEd1xQ6M", "reviewer": "Reviewer_HjVF", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "PROS\n\nI'd like to say that extending the stability-based analyses to bath RL settings is an interesting line of thought.\n\nCONS\n\nThis paper is not sufficiently close to publishable form, in my opinion. This comment has to do with the amount of editorial changes that would need to be addressed (see my editorial feedback below), and also with concerns around definitions and mathematical formalism.\n\nI found it difficult to follow the switch from RL settings to supervised learning settings, and how the latter helps the former. In particular, Section 4 focuses on definitions that, as far as I understand, are framed in the supervised learning context, while the intention is to carry them over to the setting ob batch RL. Perhaps this means that the way the paper is written isn't helping.\n\nPerhaps the difficulty starts from Sections 3.1 and 3.2. Section 3.1 describes the batch RL setting and notations. Section 3.2 describes algorithmic stability and sets the definitions and notation, which are borrowed from the supervised learning setting I think. Perhaps what's missing is some connection between these two sections: That the loss function $l$ of Section 3.2 will be taken to be the squared loss so that the empirical risk defined in Eq. (8) corresponds to the empirical mean squared Bellman error defined in Eq. (3)?\n\nIn general it is unclear what content is from previous works (or even well-known) and what content is novel.\n\nThe previous is related to an overall lack of referencing, to attribute to the literature and to support claims.\n\n\nEDITORIAL FEEDBACK\n\nFirst line of abstract: delete \"recently\" \n\nSuggested rewrite: \"We provide a theoretical examination of overfitting in the context of batch reinforcement learning, through the fundamental relationship between algorithmic stability and the generalisation gap---the former characterises the effect changing at a single data point, and the latter can be used to quantify overfitting.\"\n\n[No need for a reference here, it is better to give the reference in the introduction and related literature.]\n\nSuggested rewrite: \"To do so, our work extends the stability analysis of stochastic gradient methods given in previous work, to the iterative methods that are more common in RL\"\n\n[Again, no need for a reference here, which is more suitable to be given in the main body rather than the abstract.]\n\nReplace \"performance on the MDP\" with \"performance on the whole environment\"\n\n[Declare and use the acronym \"MDP\" in the introduction.]\n\nSection 1 (Introduction):\n\nI think the central aim of machine learning theory is to characterize learning. Studying overfitting might be one aspect at best. The claim that the aim is \"worst-case bounds\" may need to be supported, according to what is the intended message.\n\nThe sentence \"overfitting is still observed in RL settings\" calls for a reference.\n\nSo does the sentence \"Batch RL has been of particular recent interest\"\n\n[Or at least insert something like \"(see the related literature in Section 2 below)\"]\n\nReplace \"close to the ERM formulation\" with \"close to the supervised learning setting\"\n\nNext paragraph: It is not clear what notion of \"error\" the authors have in mind. This is regarding the sentence that says \"error on our dataset\" and \"error across the whole MDP\" -- please clarify to help the readers.\n\nNote that the meaning of \"MDP\" has not been declared.\n\nLast line of page 1: Replace the dash with a colon.\n\nSection 2 (Related Work):\n\n\"the results of Hardt et al. (2016), who established [...]\"\n\nNext paragraph: \"linearly parametrised value function estimators\" (insert \"function\")\n\n\"though their settings and assumptions differ from those used here.\" (insert \"their\")\n\nNext paragraph, sentence about Wang et al. (2021): replace \"provides\" with \"provide\"\n\nBritish vs. American spellings: choose one and use consistently throughout the paper.\n\n[e.g. currently both \"realisability\" and \"realizability\" are used, and \"characterises\" and \"characterizes\" and may be others.]\n\nSection 3 (Preliminaries):\n\n\"formalised as a Markov Decision Process (MDP), denoted $\\mathcal{M}$, with [..]\"\n\nInsert a reference where the reader may see all the details of these definitions.\n\nReplace \"pi\" with \"$\\pi$\"\n\nSuggested rewrite: \"Typical problems seek to estimate (in the policy evaluation case) or optimise (in the control case) the expected discounted sum of future rewards [..]\"\n\nTo make things clear I suggest to show explicitly the two expectation signs in the right hand side of Eq. (1). This means to show the expectation w.r.t. $S' \\sim P(S,A)$, and separately the expectation w.r.t. $A' \\sim \\pi (S')$.\n\nLine after Eq. (1): write the mathematical definition of $\\bar{r}(S,A)$.\n\nThe expectations in Eq. (2) seem to be in the wrong order: First $S' \\sim P(S,A)$ and next $A' \\sim \\pi (S')$, therefore the inner expectation should be w.r.t. $S' \\sim P(S,A)$ and the outer expectation w.r.t. $A' \\sim \\pi (S')$. This order should be used also in Eq. (1).\n\nNext paragraph: \"The operator $\\mathcal{T}^\\pi$ is $\\gamma$-contractive, and thus has a fixed point.\" \n\nNext sentence: \"The fixed point of $\\mathcal{T}^\\pi$ corresponds to the true value of the policy $\\pi$ in question\"\n\nLast line of this paragraph: write \"$\\mathcal{Q}_w(\\phi(S,A)) = w^\\top \\phi(S,A)$\" or \"$\\mathcal{Q}_w(\\phi(S,A)) = \\phi(S,A)^\\top w$\"\n\nSection 3.1:\n\nReplace \"to estimate either\" with \"either to estimate\"\n\nEq. (3): The minimum should be outside the sum, I think?\n\nThe sentence \"In practice, particularly when using neural networks, the minimiser of (3) cannot be found in closed\nform\" should be followed by some suitable reference(s) to support it.\n\nIi is not clear why it may be \"undesirable from the perspective of learning dynamics, to reach this optimum\" -- clarify or elaborate.\n\nA reference for \"expected SARSA\" might be relevant.\n\nReplace \"Bellman error in Algorithm 1.\" with \"Bellman error. The procedure is described in Algorithm 1.\"\n\nNext paragraph: \"the value parameters $w$ are projected\" (remove the comma after \"parameters\")\n\nNext paragraph: \"By varying the hyperparameters of Algorithm 1, namely [..], we move between\" (and fill in what should be in [..])\n\nOverall, it looks that this section is presenting things that are known, but references are missing.\n\nLine after Eq. (5): \"where [,,]\" (not capitalized)\n\nSection 3.2:\n\nSecond paragraph: \"Let $\\mathcal{X}$ be the space of all data points, and let $\\mathcal{W}$ be the space of parameters corresponding to the class of models [..]\"\n\n\"a sampled dataset of size $n$, say $D = (X_1, ..., X_n)$ where $X_i \\sim \\mathcal{D}$, to a model $w \\in W$, with the aim of [..]\"\n\n\"the aim of minimising the \\emph{risk}, which is the \\emph{expected loss} for a given loss function $l : \\mathcal{W}\\times\\mathcal{X} \\to \\mathbb{R}$ over the population distribution $D$:\"\n\nUse \"$\\mathcal{R}_\\mathcal{D} (w)$\" instead of \"$\\mathcal{R}(w)_\\mathcal{D}$\"\n\nThe discussion after Eq. (8) is misleading. Note that minimizing the risk entails minimizing the empirical risk and the gap. This is because minimizing only the empirical risk could lead to overfitting (big gap), and minimizing only the gap could be done with constant functions which may not minimise the risk.\n\nEq. (9): might be better to write $\\mathcal{G}_\\mathcal{D}(\\mathcal{A})$ or $\\mathcal{G}(\\mathcal{A},\\mathcal{D})$ on the left hand side.\n\nNext paragraph: Replace \"the simplest and most popular is\" with \"we focus on the notion of\"\n\nWarning: what's written at the bottom of page 4 looks like stability in expectation, this is different from the \"uniform stability\" defined by Bousquet and Elisseeff (2002), see their Definition 6 (their Eq. (7)).\n\nThe paper \"Sharper bounds on uniform stability\" (Bousquet, Klochkov, Zhivotovskiy, 2020) is relevant and as its title says it gave the sharper generalization bounds cased on uniform stability (sharper than the 2002 paper).\n\nSection 4:\n\nIn Assumption 1, the second part is redundant: If the range of $\\phi$ is compact, then $\\sup_{(s,a)} \\Vert \\phi(s,a) \\Vert$ is finite. Then you can take $\\phi_\\mathrm{max} = \\Vert \\phi \\Vert$ (the sup norm).\n\nSection 4.1:\n\nFirst paragraph: It could be helpful for the reader to point of what are the fixed distribution that generates the training data, and the target distribution? With the batch RL problem in mind, these distributions must come from the interaction of policies with an environment?\n\nIt is not obvious what's the connection between optimization of Eq. (10) and the batch RL problem.\n\nMissed some motivation for Definition 1. Why does the ratio of probabilities appear? Technically it is obvious, it is a trivial change of variable. What I am asking is for some motivation for why to define this as the proposed novel stability notion. Also whether/how it is computable.\n\nSection 4.2:\n\nWhat's called \"$\\eta$-expansive\" is more commonly called \"$\\eta$-Lipschitz\"\n\nSection 4.3:\n\nThe name \"$\\sigma$-bounded\" is not very informative. What this condition tries to do is control the distance between $G(w)$ and $w$ uniformly for all $w$'s.\n\nSection 4.4:\n\nParagraph after Theorem 1: The reader may wonder what are $l_1$ and $l_2$? In order to understand the sketch of the proof.\n\n\nSection 5:\n\nThe axis labels are extremely small, this makes the plots very difficult to read.\n\nWould it be possible to see specific examples of batch RL problems where early stopping is advisable and gives better results than long training times? This would strengthen the support in favor of the argument that fast training improves generalization.", "summary_of_the_paper": "As far as I can see, this work tries to leverage the connection between stability and generalization studied in supervised learning settings, and tries to build a similar connection for batch RL settings. To reason about stability in a batch RL problem, this work proposes a modified definition of stability that takes into account the two different distributions involved: the distribution generated by the interaction between the environment and the policy that generated the data, and the distribution corresponding to the policy being evaluated. Then the main result of the paper (Theorem 1) proposes an upper bound on the stability for fitted expected SARSA (and linear value function approximation).", "summary_of_the_review": "One big concern is the writing of the paper: I do not think it is nearly ready to publishable form, as it looks that a large amount of work needs to be done to get there. These deficiencies affect the paper's readability and quality. \n\nI think the main idea of the paper might be interesting, and the results may have some value. I did not find any obvious flaws. The theoretical contribution is not groundbreaking, as the presented results largely re-use proofs of existing results, but nevertheless there is some merit in extending to a new setting. I am not so sure that the section on experiments adds much value.  \n\nMy evaluation is based mainly on considering the amount of fixes that need to be done for this work to be acceptable for publication.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "C26Y9cboI3u", "reviewer": "Reviewer_ZmZV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe assumptions, lemmas and theorems are clearly stated. The target algorithm to analyze is clear from the pseudo code. The paper is clearly written.\n\nIt attempts to analyze the \"generalization\" properties of a batch RL learning target through a definition of stability, which is novel.\n\nWeaknesses:\nThe main weakness of the paper is its usefulness to batch RL learning. It would be nice for the author to devote more time on clarifying how resting on many assumptions and viewed from a particular angle of stability, Theorem 1 actually can help us understand general batch RL learning better, or help us devise a better batch RL algorithm.\n\nOne part I didn't understand is that \"off-distributional stability\" from the paper seems to refer to stability in regard to data shuffling, whereas the term \"generalization\" in RL literature usually refers to how the model learned from a training distribution performs on a possibly different test distribution. \n\nIt would also be nice to see a discussion of the learning target of choice and particularly why using a target network is chosen for this analysis, instead of for example, using semi-gradient or using other off-policy learning algorithms altogether.\n\nNits:\n1. first line : \"wort-case bounds\"\n2. Figure 1 is really hard to read.\n", "summary_of_the_paper": "The paper analyzed a case of the stability property due to data shuffling for an expected SARSA update using linear function approximation and target networks.", "summary_of_the_review": "I think the paper makes an interesting theoretical contribution in a limited setting. It may need a bit more work to bring the message home and make it significantly meaningful and illuminating in designing new algorithms to practitioners in batch RL.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors studied algorithmic stability of batch reinforcement learning algorithms, as well as its connection to certain generalization bounds (motivated by the prior work Hardt et al developed for SGD on nonconvex optimization problems). While understanding the stability and generalization of batch RL is certainly an interesting and important direction, the paper in its current form is not yet ready to be published. As the reviewers pointed out, both the analyses and the claims need to be polished (in fact, important details and definitions are missing); and the theoretical contributions are only made in a limited setting.
Decision: Reject