Exploiting the Replay Memory Before Exploring the Environment: Enhancing Reinforcement Learning Through Empirical MDP Iteration
Authors: Hongming Zhang
Chenjun Xiao
Chao Gao
Han Wang
bo xu
Martin Müller
Venue: NeurIPS 2024 poster (2024)
Keywords: Deep Reinforcement Learning; Empirical MDP Iteration;
Primary area: reinforcement_learning
TL;DR: Improving online reinforcement learning by regularizing such algorithms with Empirical MDP ITeration (EMIT).

Abstract: Reinforcement learning (RL) algorithms are typically based on optimizing a Markov Decision Process (MDP) using the optimal Bellman equation. Recent studies have revealed that focusing the optimization of Bellman equations solely on in-sample actions tends to result in more stable optimization, especially in the presence of function approximation. Upon on these findings, in this paper, we propose an Empirical MDP Iteration (EMIT) framework. EMIT constructs a sequence of empirical MDPs using data from the growing replay memory. For each of these empirical MDPs, it learns an estimated Q-function denoted as $\widehat{Q}$. The key strength is that by restricting the Bellman update to in-sample bootstrapping, each empirical MDP converges to a unique optimal $\widehat{Q}$ function. Furthermore, gradually expanding from the empirical MDPs to the original MDP induces a monotonic policy improvement. Instead of creating entirely new algorithms, we demonstrate that EMIT can be seamlessly integrated with existing online RL algorithms, effectively acting as a regularizer for contemporary Q-learning methods. We show this by implementing EMIT for two representative RL algorithms, DQN and TD3. Experimental results on Atari and MuJoCo benchmarks show that EMIT significantly reduces estimation errors and substantially improves the performance of both algorithms.

Exploiting the Replay Memory Before Exploring the Environment: Enhancing Reinforcement Learning Through Empirical MDP Iteration
Hongming Zhang', Chenjun Xiao², Chao Gao', Han Wang', Bo Xu', Martin Müller
'Department of Computing Science and Amii, University of Alberta Shenzhen
EEmonnon Research Center, Huawei Canada
Institute of Automation, Chinese Academy of Sciences hongmin20uallertaa.
Abstract
Reinforcement learning (RL) algorithms are typically based on optimizing a Markov Decision Process (MDP) using the optimal Bellman equation. Recent studies have revealed that focusing the optimization of Bellman equations solely on in-sample actions tends to result in more stable optimization, especially in the presence of function approximation. Upon on these findings, this paper, we pro- pose an Empirical MDP Iteration (EMIT) framework. EMIT constructs sequence empirical MDPs using data from the growing replay memory. For each of these empirical MDPs, it learns an estimated Q-function denoted as Q. The key strength is that by restricting the Bellman update in-sample hootstrapping, each empirical MDP converges to a unique optimal Q function. Furthermore, gradually expanding from the empirical MDPs to the original MDP induces monotonic policy improve- ment. Instead of creating entirely new algorithms, we demonstrate that EMIT can be seamlessly integrated with existing online RI. algorithms, effectively acting as a regularizer for contemporary Q-learning methods. We show this by implementing EMIT for two representative RL algorithms, DQN and TD3. Experimental results on Atari and MuJoCo benchmarks show that EMIT significantly reduces estimation errors and substantially improves the performance of both algorithms.
Introduction
Reinforcement learning (RL) has achieved remarkable success across various domains, such as games [1, 2, 4, 5], robotics [6, 7, 8] and industrial applications [9, 10], by modeling them Markov Decision Processes (MDPs). Most RL methods store transitions in a replay memory [11] and estimate an action-value function from batches of that data. They apply the Bellman optimality equation as an iterative update:
((s, a) + r(s,a) + y max Q(s' a').
(1)
a'
Such value iteration converges to the optimal action value Q' given infinite state-action visitation and updates [12, 13, 14, 15]. An optimal policy is derived by taking an action with maximum Q at each state approximated by parameterized policy [16, 17, 18, 19]. In practice. data coverage in the replay memory is limited to potentially small subset the whole state-action space, especially for complex environments. Indeed, the Bellman update in Eq. (1) suffers from estimation errors due the combination of applying the max operator to out-of-sampll actions and bootstrapping from a function approximator. In the examples in Fig. la, the well-known double Q-learning method [20] cannot
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Saurkrat
Mr
-00
R2.
190
0.2 044
85
0.
13
-00
200
025
M,
S
(a) Comparison of double Q technique with empirical @ We train
(b) In Empirical MDP Iteration (EMIT), consider transitions existing in the empirical MDP M,.
Double DQN [21] and TD3 [17] with the double technique. Con- currently, we Iearn @ based on Eq. (2), The graphs show the dif- ference between the Q value and discounted Monte Carlo return. Greater/less than 0 means ble Q technique overestimates Breakout hut underestimates on HalfCheetah. Q yields much more accurate estimation on both tasks,
play memory
then solve M; and collect more data. Re- peating this process yields refined empiri- cal MDPs MM, M2,.... which progres- sively approach the original MDP M.
The dou-
eliminate the estimation error. Its effects are heavily task-specific: it overestimates on Breakout game but underestimates on HalfCheetah.
We argue that the estimation error hard to correct for methods based on Eq. (1) that consider the entire MDP, because there are infinitely many suboptimal solutions consistent with the Bellman equation when the data incomplete. Errors due to such incomplete data can backpropagate to transitions in the replay memory and impede the whole learning process. However, bootstrapping only from sample actions without querying the values unseen actions greatly reduces the estimation error, even with function approximation. The function Q in Fig. 1a was learned in this way.
Motivated by these observations, we advocate for solving the empirical MDP M which only uses transitions in replay memory D collected from the environment.
((s.a) + max Qs',aa". al:(8' E
(2)
There is no out-of-sample hootstrapping in Eq. (2), and the solution in finite state-action space is unique. If 'D grows over time and gradually covers the entire MDP, then optimizing with Eq. (2) eventually leads to the solution to the original MDP. This observation instantly implies new iterative learning procedure: alternate between exploitation by solving an incumbent empirical MDP, and exploration for growing the empirical MDP with new data. This Empirical MDP Iteration (EMIT) process is illustrated in Fig. lb. How grow M? In principle, exploration should find missing strong actions that bring M closer to M. Following the well-known principle of optimism in the face of uncertainty [22], we argue that one option is to drive the exploration for growing M by the value difference between Q and @ EMIT can be applied to any RL algorithms that can learn both Q and Q [23]. We implement and evaluate two variants based DQN [16] and TD3 [17], for discrete action spaces and continuous control tasks respectively. Our contributions are summarized as follows:
1. We provide a thorough analysis to show why the estimation error is hard to eliminate when using the Bellman update with incomplete data, and that bootstrapping from in-sample transitions greatly reduces this error, both with and without function approximation.
2. In the tabular case, we prove that the in-sample bootstrapping guarantees a unique optimal Q for M. If the optimal trajectory for M is included in M, then the greedy policy derived from Q' is also optimal for M following the optimal trajectory. Further, monotonic improvement in learning
Q guaranteed with growing data coverage if M is deterministic. These imply that Q can be natural regularizer for Q.
3. We develop a novel framework EMIT, which can be used to enhance existing RL algorithms by iteratively solving a current empirical MDP for stable finite-time performance, and can progressively approach a solution to the original MDP. EMIT can be combined with any method that learns a Q function. We add EMIT to DQN and TD3, and conduct extensive experiments on Atari [24] and MuloCo [25] tasks. We show strong performance enhancements for both methods. Further analysis demonstrates that EMIT largely overcomes problems of estimation error.

---

2 Background
Markoy Decision Process (MDP). Reinforcement learning (RL) [26, 27] is a paradigm of agent learning via interaction. It can be modeled as Markov Decision Process (MDP), 5-tuple M A, R, P. S denotes the state space, A denotes the action space, P(s'|s, a) AxAxS + [0. I] is the environment dynamics, R[s a) S x A - IR is the reward function which is bounded, y E 10 is the discount factor. The goal of an RL agent is to learn an optimal policy æ that maximizes the expected discounted cumulative reward E, ?/re).
Value-Based Methods. Q-learning is classic algorithm based on the Bellman optimality equation (*,s, a) = E rr + 7 max, Q2"(",, a')] [28]. An optimal policy takes an action with maximum Q at each state. DQN [16] scales up from tabular Q-learning by using deep neural networks and experience replay [11]. Actor-critic methods [6] such as SAC [18] and TD3 [17] learn parameterized policy, which suitable for continuous action spaces. The policy is updated by gradient ascent of a Q network, V T E.EB Qa(s,a)), Ag ~ TT(-ss), where B is a batch of samples.
In-Sample Bellman Update. The in-sample constraint in Eq. (2) avoids bootstrapping from unseen actions when estimating target values. Several recent offline RI. [29] methods use Eq. (2) to approximate optimal action value function. For example, implicit Q-learning (IQL) [30] uses expectile regression to learn the optimal Q function without ever querying the values of unseen actions. Its learning goal is to minimize the expectile regression objective:
T())= = ("),a,"',')) [ (r(s + 7Qg(s' .') Qo(s,a)),,
where (u) = |- (u < 0) 2 is a weighted mean squared error loss, and Qa is the target network. This asymmetric loss function defines the entire spectrum of methods between SARSA (T = 0.5) and Q-learning (r -> 1). Eq. (2) can be approximated using Eq. (3) with 1, Other methods like In-Sample Actor-Critic (InAC) [31] and Extreme Q-learning (XQL) [32] are also based on Eq. (2), and EMIT straightforward to implement based on these offline methods.
3 Empirical MDP Iteration
replay memory D maintained store transitions (s, a, r, s'). In most cases, the original MDP M is too large, and 'D contains only a small subset of all transitions in M. Due to the incomplete data, infinitely many other MDPs can be consistent with M on transitions in D. For ease of notation, we denote (s, a) E 'D if 3 (s, 7, s') E 'D and E D if 3 (s, r, s') ) E D or 3 (š, a. n. s) E D. A visit count (ss, a, s') is defined as the number of times (s, a, s') appears in D. We define the empirical MDP M to be the lowest reward MDP that uses all data in D.
Definition 3.1 (Empirical MDP). Given a dataset DD from MDP M, the empirical MDP M == (S, R, P. 7), has state space = {>|s E DD, and action space == (al(s, a) E DD, with reward function R(ss a)- R(s, a) if (s, a) D, and R(s, a) = oo otherwise. P(s"| ss a) = Σ. N(s.a.s)) is the empirical transition dynamics based on visit counts in D, and y E (0, 1) is the discount factor.
N(s.o,8')
The empirical MDP M contains all information we can obtain from D. a (state, action) pair not in the data, its reward is set to oo and its transition probabilities are zero
We analyze two update rules in the tabular case with finite S A, the Bellman update and the in-sample Bellman update given in Eqs. (1) and (2). Both update rules try to minimize the Bellman residual [33], which is a surrogate objective to minimize the action value error and approximate the optimal value. Eq. (1) takes the maximum over all actions, while Eq. (2) only uses in-sample actions for a state. Let Q" and Q' be the optimal action values for M and M respectively. Then:
Proposition 3.2. If the data coverage D is incomplete, then the Bellman update Eq. (1) neither guarantees convergence to the optimal value Q* for the original MDP M nor to the optimal value Q' for the empirical MDP M, even in the limit of infinite updates.
The proof is straightforward. Given that D is incomplete, there exist transitions in M that are not present in M. These absent transitions can be assigned any initial values, and may bootstrap to in sampee transitions, thereby influencing the convergence process. This indicates that the Bellman
3

---

Paice Detaed
The CBT
The CRT
CUT
-05
(a) Value errors compared with Q" and Q"
(b) Policies after learning.
Figure 2: (a) illustrates two cases in the CliffWalk task: memory D only contains sub-optimal trajectory and misses many transitions (left); D contains all optimal state-action pairs but misses some sub-optimal actions (right). The curves show estimation emror Q and Q learned with Eqs. (1) and (2) compared with Q' and Q' (b) presents the greedy policies after learning. Red arrows indicate incorrect actions neither follow arg max Q' nor arg max Q- The blue shading signifies accurately estimated Q and overestimated Q values.
update is heavily influenced by the values of unseen sate-action pairs. A simple example is provided in Appendix A Fig. 7. In contrast, the in-sample Bellman update is not affected by unseen transitions, and thus converges to unique optimal value Q" for M..
Proposition 3.3. The in-sample Bellman update Eq. (2) uniquely converges to the optimal value Q' for the empirical MDP M in the limit of infinitely many updates. Furthermore, if the optimal trajectory for M is included in M, then the greedy policy derived from Q" is also optimal for M following the optimal trajectory.
We defer the proof to Appendix A, and provide toy example on CliffWalk [26] in Fig. illustrate the difference between the two update rules. CliffWalk is a simple navigation task. The goal is to reach the state G the bottom right starting from the bottom left. The reward of reaching G 1. Dropping into the cliff gives reward -1, and all other rewards are O. We present two cases: (1) D contains a sub-optimal trajectory and misses many acte-action pairs (Fig. 2a top left), and (2) D contains optimal action at each state but misses some sub-optimal actions (Fig. 2a top right).
We parameterize Q and Q with neural networks and sample batches of data to update them with gradient descent following Eqs. (1) and (2). The learning curves in Fig. 2a shows value errors comparing with the optimal values. A(Q1. Q2) denotes the averaged absolute eтrоr on state-action pairs in D between Q1 and Q2. AQQ. Q*) converges to O, indicates that Q converges to Q-. However, Q neither converges to Q" nor Q particular in the second case, all optimal actions are included in D. Q converges to global optimum while Q still fails due to missing actions. This highlights the heavy influence of missing transitions the Bellman update. Fig. 2b further presents the greedy policies derived from Q and Q after learning. Red arrows present actions that neither follow arg max Q" nor arg max Q-_ The blue shading indicates the action values. Q overestimates on most state-action pairs (top row of Fig. 2b). The policy derived from Q cannot learn the (current) optimal actions, while arg max Q represents best possible policy.
We solve each empirical MDP M, defined by the current memory D;, and add data progressively approach the original MDP M. If M is deterministic, a monotonic improvement of the learning is guaranteed by alternating between learning a currently best possible policy and collecting more data.
Proposition 3.4. Assume M has deterministic transitions. If (D:} are datasets collected from M with D1 C D2 C C Dn, and corresponding empirical MDPs (M.), then Qi s Q2 .... Q;
This result is intuitive. With more transitions in the replay memory. we take the maximum over wider range of actions, leading to better solution closer to Q". If the empirical MDP contains all transitions, then M = M and Q- = Q". The proof details are provided in Appendix A.
The in-sample Bellman update provides learning path improve a policy. The guarantee of the convergence to a unique optimal value on existing transitions a key property, which makes the in-sample Bellman update more robust choice for learning in the presence of missing transitions.

---

More importantly, if the globally optimal trajectory has been explored and included in the memory. then the in-sample Bellman update can learn an optimal policy catching up with the optimal trajectory even when some other transitions are missing. In contrast, the Bellman update is strongly affected by such missing transitions, and cannot guarantee learn even from optimal trajectories.
3.1 Enhancing Online RL Algorithms with EMIT
Two major questions in EMIT are how learn Q from M and how to grow M using out-of-the-box strong reinforcement learning algorithms. To take advantage of an existing value-based learning algorithm, we utilize Q to modify Q learning in two places, based on the value difference. First, given a sampled batch of data, we modify the standard mean squared error (MSE) loss function of Q by adding a MSE loss of Q as regularizer:
L = MSE(QQ. Qurga) + aMSE(Qe. ²),
(4)
Here, Quarest = r(s, a) +? max, Q(s', a'), and is parameter controlling the level of regularization. Second, we add an exploration bonus to the algorithm's 's behavior policy. The rationale is that since we regularize Q to approximate Q on existing transitions in the replay memory, the values of Q(s, a) and (s,, a) should be closer at known than unseen state-action pairs. Therefore, provide more incentive for the agent to explore those dissimilar states. Define the absolute difference between Q and Q at (s, a) when interacting with the environment by:
8(s,a) 1Q(s, a) (s,
(5)
For algorithms in discrete action spaces such as DQN, we can add an exploration bonus d(s, a) the greedy part of an e-greedy policy: with probability it chooses an random action usual, otherwise selects an action that is greedy w.n.t Q(s, a) + ó(s,a):
random action,
p == E arg max, (Q(x, a) + 0(s, a)),
π
(6)
==1 1 -
Eq. (6) adds targeted exploration mechanism c-greedy.
For algorithms in continuous action spaces such as TD3, where the policy is assumed to be a unimodal Gaussian distribution, we use 5 state-action dependent standard deviation and sample actions according to:
- (s) + e e~ clip(N a)), -c. c),
(7)
The added noise is clipped to keep the target close to the original action [17].
Algorithm shows pseudo-code for incorporating EMIT into Q learning algorithm Alg. Blue text highlights the components added or modified by EMIT. EMIT maintains Q and incorporates into the algorithm's 's action selection Alg.act() and Q update Alg. uuduuepd)e Any method based on Eq. (2) apply implicit Q-learning (IQI.) [30]. We learn Q using DQN [16] and TD3 [17] for discrete and continuous environments respectively. Clearly, framework, rather than fixed algorithm.
be used learn Q. In experiments,
Algorithm should be more appropriate be viewed
Algorithm Empirical MDP Iteration for Enhancing a Q Learning Algorithm Alg (EMIT-A1g
I: Alg. Initialize the replay memory D and action value network Qs
2: EMIT. Initialize Q
3: Alg.In Initialize the environment Se + Env
4: for environment step f = to do
5: Alg.Select an action a, Alg.act(s;, Qa) as Eq. (6) or (7) IQ guided exploration)
6: Alg. Execute a. Env and get Ft; 8c+1
7: Alg. Store transition (st, as, Ts, 81+11) in D
8: Alg. Sample random minibatch of transitions B from D
9: EMIT.update(() (Q,, B) w.r.t MSE loss derived by Eq.(2) (Learning of Q)
10:
Alg.update( (Qo, 23, Qa) as (4) (Q regularized learning for Q)
11: end for
5

---

DOx
1303
2700
1960
2D
5/0
130
1.0
520 B10
200 020
Figure 3: Performance on Atari (first row) and MuloCo (second row) tasks. The learning curves show mean scores and standard deviations over five runs. EMIT consistently boosts performance across diverse tasks.
Experiments
In this section, we present experimental results validate the effectiveness of our proposed method. We applied EMIT to both DQN [16] and TD3 [17], covering both discrete and continuous action spaces. Our results demonstrate significant performance improvement when EMIT is applied to these current DRL methods. Ablation studies underscore the importance of each component of our method in contributing to this improvement. Further analysis provides insights into why EMIT works. Notably, the in-sample Bellman update Eq. (2) is capable of learning a superior policy compared to the Bellman update Eq. (1), Regularization of Q by @ yields a more accurate estimate, and the estimation error in Q decreases. Additionally, the observed decrease in policy churn [34] may represent another potential benefit of our method, worth further investigation.
4.1 Setup
Environments. We evaluate EMIT on Atari [24] and MuJoCo [25] tasks based on OpenAl Gym interface [35]. Atari provides a diverse set of video games, making it an ideal platform for evaluating the general competency AI agents. The imput for these games image-based, and the dynamics are nearly deterministic. MuJoCo offers set of continuous control tasks, all of which have a standardized structure and interpretable rewards. These tasks are designed to facilitate research and development in the field of robotics, where the need for fast and accurate simulation is paramount. The dynamics in MuJoCo are deterministic and feature digh-diimnsional state features. More details about these environments can be found in Appendix B.
Baselines and Implementation Details. We benchmark EMIT against several established algorithms. For Atari games, we compare our method with DQN [16], C51 [36], IQN [37], and Rainbow [38]. Each run involves 10 million interaction steps. Performance evaluated by executing 30 episodes after every 100k environmental steps. For MuJoCo tasks, our method is compared with SAC [18, 39], TD3 [17], XQL [32], TRPO [40]. and PPO [41]. Each run involves 2 million interaction steps. Performance is evaluated by executing 10 episodes after every 10k environmental steps. We use the same network as in the original papers for each algorithm. We search the learning rates for baselines among (1e-3,3e-4,1e Ie-4) and report the best performance. Each experiment is run with 5 different random seeds. For our method, we set the learning rate the same as the backbone algorithm, and search for the best regularization parameter E (0.05, 0.1, 0.5). All other common parameters set as detailed in Appendix Tables I and 2. Further details can be found Appendices B.2 and B.3.
4.2 Performance Enhancement of EMIT for DQN and TD3
To demonstrate the effectiveness of EMIT, we initially compare it with its backbone algorithms. Fig. 3 depicts the learning curves for Atari games (first row) and MuJoCo tasks (second row). The solid line represents the mean score, while the shaded area indicates the standard deviation. The Q online result refers to an IQL agent run online with the learning rule Eq. (2). This agent attempts to solve the empirical MDP but lacks the exploration mechanism that augments the MDP. DQN and TD3 are agents that follow the learning rule Eq. (1). They have exploration mechanisms such as

---

1.0
Atari Games
1.0
MiJoCCo Tasks
0.8
0.8
0.6
Normalibed
Nomeliadd
0.4
0.4
0.2
0.2
0.0
0.0
EMITg-DQNN
DON
EMITip-TDS
XGI
TRPO
PPQ
Figure 4: Average performance on 20 Atari games and 8 MuJoCo tasks, with each method's score normalized between and 1. EMIT achieves the best average performance across these tasks.
e-greedy and random noise. They differentiate from the EMIT counterparts in that they do not learn from the empirical MDP, hence they lack the regularization and exploration bonus derived from Q Our EMIT methods learn both Q and Q. As depicted in Fig. 3, they achieve clear improvements on all tasks compared to other methods that solely learn Q or Q. EMIT can effectively augment and boost these existing RL algorithms. It provides principled framework for seamlessly integrating the strengths traditional learning based on the Q function and the more recent advancements in in-sample learning for Q. Additional results can be found in Appendix C Figs. 23 and 24.
4.3 Comparison with Other Baselines
We extend our comparison of EMIT with other strong baselines. For clearer presentation, display normalized scores. For each task, we define Rmax and Rmin as maximum minimum cumulative reward across all methods, respectively. The score for each method is then normalized using the formula (R Rmin)/ (Bmax Rain).
The overall performance various tasks is presented in Fig. 4. EMIT achieves the best average performance across these tasks. Specifically, EMIT either outperforms 10% difference) the best baselines on 19 out of 28 tasks. Details are given in Appendix C.2 Fig. 17. Notably, on MuJoCo tasks, EMIT significantly surpasses other baselines. These results corroborate our intuition that Empirical MDP Iteration is more effective approach than focusing the original MDP from the outset. This strategy circumvents bootstrapping error, thereby enhancing sample efficiency. While the Double Q technique mitigates overestimation by employing the target network to evaluate actions, the target network may still overestimate or underestimate certain state-action pairs. The distributional perspective of value estimation fosters more stable and risk-aware behavior. However, estimation error persists due to the maximization bootstrapping from sat-ol--ample actions. In contrast, EMIT seeks simplify the problem, addressing it incrementally and progressively approximating the original problem. This approach can provide accurate target values for each empirical MDP, leading to consistent improvement. In summary, EMIT reduces estimation error and provides accurate targets, thereby making the learning process more efficient. Detailed learning curves can be found in Appendix C.2.
on par with (within
4.4 How the In-Sample Bellman Update Benefits the Learning
In Section 3, we analyze beneficial properties of the in-sample Bellman update. In this section, we provide comprehensive empirical evidence for them.
We first demonstrate that the in-sample Bellman update is well-suited for passive learning [42, 29], without the need for active interaction with the environment. Since the policy under which the data collected is not a concern, this allows greater flexibility in designing exploration strategies. We execute DQN and TD3 (based on the Bellman update in Eq. (1)) on Breakout and HalfCheetah to learn policy म. Concurrently,
learn a policy á using another IQL agent with in in-sample Bellman updates Eq. (2). Policy и interacts with the environment and collects data into a replay memory. Both т and learn from this same dataset. Fig. 5a illustrates the performance of and स. Interestingly, # performs comparably, if not better than Despite á being learned without taking actions in the environment, we observe no performance degradation attributable to passive learning. This somewhat counterintuitive, active learning is generally considered superior [43].
7

---

-10
530
221
100 120
18
10
30
(a) Policy performance.
(b) Estimation error of Q after regularization.
Figure 5: (a) We DQN and TD3 on Breakout and HalfCheetah, and concurrently learn action value Q with the collected data. The curves show the performance of policies и and f, derived from Q and Q respectively. Remarkably, it, learned without active environment interaction, matches or even surpasses nt's performance. (b) EMIT helps reduce the error in Q and learns almost accurate value estimation during the learning process.
We conclude that the in-sample Bellman update can learn an effective policy from given data without the need for active interaction with the environment, and that the active policy does not fully utilize the collected data and fails to identify the optimal policy due to bootstrapping errors. This underscores that bootstrapping from -fample transitions hampers effple-efiicient learning. Similar results on additional environments can be found in Appendix C.3 Figs. 18 and 19.
Next, we demonstrate that the regularization of Q with Q significantly diminishes the estimation error in Q. At each evaluation, we obtain the true discounted Monte Carlo return, denoted as Q by executing the current policy for 30 episodes and calculating the actual discounted cumulative rewards, (St, a²) Σi= 7"r,. We then compute the average estimation difference between the learned Q and the ground truth Qruc.
Van Qiree)
1
Σ (Q(s, Quue (a,a)TT
(8)
T
Here, T represents the set of evaluation trajectories, and [T] denotes the total number of state-action pairs in T. We calculate Vai for our method and compare it with DQN and TD3 on Breakout and HalfCheetah', As shown in Fig. 5b, our method maintains the difference near zero, indicating that the estimation is remarkably close to the true value, with no significant overestimation or underestimation. Similar results for other environments can be found in Appendix C.3.
Another potential factor contributing the performance improvement is the reduction of policy churn, the rapid change of the greedy policy in value-based reinforcement learning, primarily induced by high-variance updates in deep learning. Much of this policy change could be unnecessary, particularly as learning converges [34]. Measuring policy change in continuous action space is not straightforward. Therefore, we assess the change on Breakout and Pong, which have discrete action spaces. The results are shown in Fig. 6a, with additional results in Fig. 22 in Appendix C.4. Our findings consistently indicate that our method reduces policy change compared to DQN, However, policy churn is not entirely detrimental, as it can serve as potentially beneficial form of implicit exploration. The optimal frequency of change that could enhance learning remains unclear and deserves further investigation.
4.5
Effect of Loss Regularization and Exploration Bonus
Our algorithm design comprises two key components: the regularization term, determined by the parameter a, and the exploration term, designed based on the value difference ö(s, a). The impact of each component on the Breakout and HalfCheetah environments is further shown in Figure 6b. The label w/o reg term signifies the absence of regularization for the function Q, i.e. a 0. w/o explore term indicates the use of existing exploration methods, such as e-greedy or random noise, without the addition of our exploration mechanism. w/o both refers to the backbone methods devoid of two enhancements. full method incorporates both the regularization and exploration terms. Figure 6b reveals that both components independently contribute to learning. We see more significant performance decline without the regularization term. This suggests that, by adhering to the paradigm of empirical MDP iteration, the current exploration mechanism can already yield substantial improvements. The introduction of an advanced exploration mechanism can further enhance performance. Similar results for more environments can be found in Appendix C.5.
Unlike Fig. la that measures the error of Q, here we measure the estimation enror of Q after regularization.
8

---

044
64
544
80
233
22
60 62
34
73 0.0
08
12
(a) The policy change over the learning.
(b) The contribution of each component of EMIT.
Figure 6: (a) EMIT helps reduce unnecessary policy change comparing with DQN, potentially contributing to the enhanced performance. (b) Both the regularization and the exploration mechanism benefit the online learning. The regularization term exerts greater impact than the exploration mechanism.
Related Work
Accurate value estimation is crucial for RL algorithms. The use of erroneous bootstrapping targets can degrade the Q function, resulting in suboptimal performance [44, 45, 46, 47]. Overestimation can occur when bootstrapping error is combined with maximizing over action values [20]. Double DQN [21] mitigates this overestimation by computing the maximum from two Q functions. Maxmin Q-larning [48] learns multiple Q functions strike balance between overestimation and underesti- mation. It requires meticulous hyper-parameter fine-tuning, which can be computationally intensive. CEER [49] constructs a graph to merge similar states and computes an additional conservative Q estimation akin to sol ving Eq. (2). However, CEER is effective only when the constructed graph dense. C51 [36] and IQN [37] are distributional RL methods that are generally more stable and risk-aware than DQN. Nonetheless, estimation error remains due to the maximization bootstrapping from -ft-lle actions. Rainbow [38] integrates six enhancements the DQN algorithm for im- proved empirical performance: double Q-learning [21], prioritized replay [50], dueling networks [5 l]. multi-step learning [52], distributional RL [36], and noisy nets [53].
Offline reinforcement learning [29] tries to fully use existing data without additional online data collection. They aim to extract best possible policy from the existing dataset. While earlier methods focused on constraining the distance between the learned policy and the behavior policy to avoid distributional shift caused by taking actions outside of the behavior distribution [54, 55, 56), recent studies found that selecting actions within the support of the dataset during training, similar to Eq. (2), is more effective [57, 30, 58, 31J. Implicit Q-Learning (IQL) [30] estimates the value of the best available action at given state with expectile regression, without ever directly querying the Q function for unseen actions. In-Sample Actor-Critic (InAC) [31] approximates an in-sample softmax using only actions in the dataset. Extreme Q-learning (XQL) [32] models the maximal value using Extreme Value Theory (EVT) and avoids computing Q-values using out-of-sample actions. In EMIT, we provide a framework for easy integration of any of these methods to solve Eq. (2).
6 Discussion and Limitations
We study the application of the Bellman equation as learning objective in scenarios with incomplete data. Bootstrapping from in-sample transitions with Eq. (2) theoretically leads to unique solution and significantly reduces the estimation error in practice, even with function approximation. We introduce novel learning paradigm, termed Empirical MDP Iteration (EMIT). Unlike previous methods that solely focus on solving the entire original MDP, we propose a regularization approach for learning by solving series of empirical MDPs using only the transitions present in the data. EMIT provides an iterative learning pathway that uniquely solves each empirical MDP and incrementally approaches the original MDP through new data collection. We instantiate EMIT with the Q-learning algorithm DQN and the actor-critic algorithm TD3. Results demonstrate a substantial improvement in performance in applications of both video games and continuous control tasks. A shortcoming that since the policy derived from Q lacks an exploration mechanism, we learn two Q functions in our algorithm design and the wall-clock time would be double. One future work could be designing a learning process that directly based on in-sample Bellman update to avoid out-of-sample bootstrapping and also taking the exploration mechanism into consideration.

---

Acknowledgements
Zhang and Müller acknowledge support from NSERC, the Natural Sciences and Engineering Research Council of Canada, UAHJIC, the Digital Research Alliance of Canada, and the Canada CIFAR Al Chair program. Wang acknowledges support from the Digital Research Alliance of Canada. Xiao acknowledges support from the National Natural Science Foundation of China (62406271).
References
[1] David Silver, Aja Huang, Christopher J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lil- licrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):48444555 2016.
[2] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. Mastering the game of Go without human knowledge. Nature, 550(7676):354 359, 2017.
[3] Hongming Zhang and Tianyang Yu. Alphazero. Deep Reinforcement Learning: Fundamentals, Research and Applications, pages 391-415, 2020.
[4] Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvit- skyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In International conference machine learning, pages 507-517. PMLR, 2020.
[5] Fengshuo Bai, Hongming Zhang, Tianyang Tao, Zhiheng Wu, Yanna Wang, and Bo Xu. Picor: Multi-task deep reinforcement learning with policy correction. Proceedings of the AAAI Conference on Artificial Intelligence, 37(6))6728 6736, Jun. 2023.
[6] Timothy P Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.080 1509002971 2015.
[7] Runze Liu, Fengshuo Bai, Yali Du, and Yaodong Yang. Meta-reward-net: Implicitly differen- tiable reward learning for preference-basee based reinforcement learning. S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Process- ing Systems, volume 35, pages 02270-22284 Curran Associates, Inc., 2022.
[8] Elia Kaufmann, Leonard Bauersfeld, Antonio Loquercio, Matthias Müller, Vladlen Koltun, and Davide Scaramuzza. Champion-leve drone racing using deep reinforcement learning. Nature, 620(7976):982 987, 2023.
[9] Xiaocheng Tang, Zhiwei Qin, Fan Zhang, Zhaodong Wang, Zhe Xu, Yintai Ma, Hongtu Zhu, and Jieping Ye. A deep value-network based approach for multi-driver order dispatching. In Proceedings of the 25th ACM SIGKDI international conference on knowledge discovery & data mining, pages 1780-1790, 2019.
[10] Jincheng Hu, Yang Lin, Jihao Li. Zhuoran Hou, Liang Chu, Dezong Zhao, Quan Zhou, Jingjing Jiang, and Yuanjian Zhang. Performance analysis of bi-based energy management in electric vehicles: A case study on classic reinforcement learning. Energy Conversion and Management, 300: 17964, 2024.
[11] Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3):293-3211 1992.
[12] Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279-292, 1992.
[13] Satinder Singh, Tommi Jaakkola, Michael I. Littman, and Csaba Szepesvári. Convergence results for single-step on-policy reinforcement-leamingg algorithms. Machine learning, 38:287- 308, 2000.
10

---

[14] William B Haskell, Rahul Jain, and Dileep Kalathil. Empirical dynamic programming. Mathe- matics of Operations Research, 41(2):402 2016.
[15] William B Haskell, Rahul Jain, Hiteshi Sharma, and Pengqian Yu. A universal empirical dynamic programming algorithm for continuous state mdps. IEEE Transactions on Automatic Control, 65(1):115-129 2019.
[16] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Pe- tersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 5 518(7540):529-5333 2015.
[17] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation in actor-critic methods. In International conference on machine learning, pages 1587-1596. PMLR, 2018.
[18] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In International conference on machine learning, pages 1861-1870. PMLR, 2018.
[19] Hongming Zhang, Tongzheng Ren, Chenjun Xiao, Dale Schuurmans, and Bo Dai. Provable representation with efficient planning for partially observable reinforcement learning. In Forty- first International Conference on Machine Learning, 2024.
[20] Hado Hasselt. Double q-learning. Advances in neural information processing systems, 23, 2010.
[21] Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q-learning. Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
[22] Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore. Reinforcement learning: A survey, Journal of artificial intelligence research, 4:237-285, 1996.
[23] Hongming Zhang and Tianyang Yu. Taxonomy of reinforcement learning algorithms. Deep Reinforcement Learning: Fundamentals, Research and Applicutions, pages 125-133, 2020.
[24] Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-279 2013.
[25] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RS international conference on intelligent robots and systems, pages 5026-5033. IEEE, 2012.
[26] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[27] Hao Dong, Zihan Ding, and Shanghang Zhang. Deep Reinforcement Learning: Fundamentals, Research and Applications. Springer Nature, 2020.
[28] Richard Bellman. Dynamic programming. Science, 153(3731):34-37 1966.
[29] Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005.01643 2020.
[30] Ilya Kostrikov, Ashvin Nair, and Sergey Levine. Offline reinforcement learning with implicit q-learning. In International Conference on Learning Representations, 2022.
[31] Chenjun Xiao, Han Wang, Yangchen Pan, Adam White, and Martha White. The in-sample softmax for offline reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.

---

[32] Divyansh Garg, Joey Hejna, Matthieu Geist, and Stefano Ermon. Extreme q-learning: Maxent RL without entropy. In The Eleventh International Conference on Learning Representations.
2023.
[33] Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pages 30-37. Elsevier, 1995.
[34] Tom Schaul, Andre Barreto, John Quan, and Georg Ostrovski. The phenomenon of policy churn. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[35] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. OpenAl Gym. arXiv preprint vr06v:/666.0/4 2016.
[36] Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective reinforce- ment learning. In International conference on machine learning, pages 449-458, PMLR, 2018.
[37] Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. In International conference on machine learning, pages 1096-1105, PMLR, 2018.
[38] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dab- ney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. Thirty-second AAAI conference on artificial intelligence, 2018.
[39] Tuomas Haarooja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprint 1rXhv:1812.05905. 2018
[40] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897. PMLR, 2015.
[41] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. arXiv preprint 1rXiv:170.006444 2017.
[42] Aviral Kumar, Justin Fu, Matthew Soh. George Tucker, and Sergey Levine. Stabilizing off- policy q-learning via bootstrapping eroor reduction. Advances in Neural Information Processing Systems, 32, 2019.
[43] Georg Ostrovski, Pablo Samuel Castro, and Will Dabney. The difficulty of passive learning in deep reinforcement learning. Advances in Neural Information Processing Systems, 34:23283- 23295, 2021.
[44] Su Young Lee, Choi Sungik, and Sae- Young Chung. Sample-efficient deep reinforcement learning via episodic backward update. Advances in Neural Information Processing Systems, 32, 2019.
[45] Aviral Kumar, Abhishek Gupta, and Sergey Levine. Discor: Corrective feedback in reinforce- ment learning via distribution correction. Advances in Neural Information Processing Systems, 33: 33:18560-18572. 2020.
[46] Zhang-Wei Hong, Tao Chen, Yen-Chen Lin, Joni Pajarinen, and Pulkit Agrawal. Topological experience replay. In International Conference on Learning Representations, 2022.
[47] Fengshuo Bai, Rui Zhao, Hongming Zhang, Sijia Cui, Ying Wen, Yaodong Yang, Bo Xu, and Lei Han. Efficient preference- based reinforcement learning via aligned experience estimation. arXiv preprint a40iv: 18688, 2024.
[48] Qingfeng Lan, Yangchen Pan, Alona Fyshe, and Martha White. Maxmin qelearning: Controlling the estimation bias of l-aannnnn. International Conference on Learning Representations, 2020.
12

---

[49] Hongming Zhang, Chenjun Xiao, Han Wang, Jun Jin. Bo Xu, and Martin Müller. Replay memory as an empiriaal MDP: Combining conservative estimation with experience replay. In The Eleventh International Conference on Learning Representations, 2023.
[50] Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. In ICLR (Poster). 2016.
[51] Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International conference on machine learning, pages 1995-2003. PMLR, 2016.
[52] Richard S Sutton, Learning to predict by the methods of temporal differences. Machine learning. 3:9 44, 1988.
[53] Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv:/706 10295, 2017.
[54] Yifan Wu, George Tucker, and Ofir Nachum. Behavior regularized offline reinforcement learning. arXiv preprint 1rXiv:1911.11661, 2019.
[55] Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine. Awac: Accelerating online reinforcement learning with offline datasets. arXiv preprint arXiv:2006.00 09359, 2020.
[56] Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning. Advances in neural information processing systems, 34:20132 32-40145, 2021.
[57] Wenxuan Zhou, Sujay Bajracharya, and David Held. Plas: Latent action space for offline reinforcement learning. In Conference Robot Learning, pages 1719-1735. PMLR, 2021.
[58] Hongchang Zhang, Yixiu Mao, Boyuan Wang, Shuncheng He, Yi Xu, and Xiangyang Ji. In- sample actor critic for offline reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.
[59] Scott Fujimoto, David Meger, Doina Precup, Ofir Nachum, and Shixiang Shane Gu. Why should trust you, Bellman? the Bellman error is a poor replacement for value error. In International Conference on Machine Learning, pages 6918 18-4993. PMLR, 2022.
[60] Andrzej Granas and James Dugundji. Fixed point theory, volume 14. Springer, 2003.
[61] Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures on artificial intelligence and machine learning, 4(1):1-103, 2010.
[62] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[63] Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence stochastic iterative dynamic programming algorithms. Advances in neural information processing systems, 6, 1993.
[64] Francisco S Melo. Convergence of q-learning: A simple proof. Institute Of Systems and Robotics, Tech. Rep, pages 1-4, 2001.
[65] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
[66] Mark Towers, Jordan K. Terry, Ariel Kwiatkowski, John U. Balis, Gianluca de Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Arjun KG, Markus Krimmel, Rodrigo Perez- Vicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Andrew Tan Jin Shen, and Omar G. Younis. Gymnasium, March 2023.
[67] William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. In International Conference Machine Learning, pages 3061-3071. PMLR, 2020.
13

---

[68] Zihan Ding, Tianyang Yu. Hongming Zhang, Yanhua Huang, Guo Li, Quancheng Guo, Luo Mai, and Hao Dong. Efficient reinforcement learning development with rizoo. In Proceedings of the 29th ACM International Conference Multimedia, pages 3759-3762, 2021.
[69] Jiayi Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Dubureq, Minghao Zhang, Yi Su, Hang Su, and Jun Zhu. Transhou A highly modularized deep reinforcement learning library. Journal of Machine Learning Research, 23(267):1-6 6, 2022.
[70] Pablo Samuel Castro, Subhodeep Moitra, Carles Gelada, Saurabh Kumar, and Marc G Belle- mare. Dopamine: A research framework for deep reinforcement learning. arXiv preprint arXiv:1812.00610, 2018.
14

---

A Proof of Propositions in Section 3
In this section, we analyze the property of the two update rules in Eqs. (1) and (2) for finite state-action space 8 x A discussed in Section 3.
Proposition 3.2. If the data coverage 'D incomplete. then the Bellman update Eq. (1) neither guarantees convergence to the optimal value Q" for the original MDP M nor to the optimal value Q' for the empirical MDP M, even in the limit of infinite updates.
We illustrate the property using an example in Fig. The original MDP comprises two states 82) and two actions {a,, (2). The memory D includes transitions {(s), a1); (81, 02); (82, a ai) but lacks (82, a2). Assuming reward r(s, a) = for all transitions for simplicity. this case, the optimal action value for all state-action pairs in M and M is 0, i... (' a) = Q* (s. a) 0, e (01,02): {si, $2).
However, the reward for the missing transition can take any value, leading to an infinite number of MDPs M, + M, where i I denotes different r(s2, (2) values. For the Bellman update Eq. (1), any action-value function can only converge to one of these Mi, depending on the initialization. The action value state 81 may be determined by the value of the missing transition (82, 02). For instance, (*2,, (2) is initialized with any positive value, Eq. (1) converges to Q(*1,a) = (Q (2) > 0, failing to approximate the optimal value 0 of either Q or Q-, This suggests that the Bellman update significantly affected by out-of-sample state-action pairs, and errors propagate back to in-sample transitions. A more formal proof is available in related work [59] Corollary 1.
a1
a1
S1
Sz
a2
a2
Figure 7: A toy MDP with two states and two actions. (82, .2) is missed in the replay memory.
Proposition 3.3. The in-samlle Bellman update Eq. (2) uniquely converges to the optimal value Q' for the empirical MDP M in the limit of infinitely many updates. Furthermore, if the optimal trajectory for M is included in M, then the greedy policy derived from Q is also optimal for M following the optimal trajectory.
We first present the established results for the Bellman update in Eq. (1), and then provide three-step proof for Proposition 3.3.
The Bellman (optimality) operator B for Eq. (1) is defined as:
(BQ) a) = Σ P(5lls,)) a)(r + max Q(s',
s'ES
Previous works have demonstrated that the operator is y-contraction with respect the supremum norm:
|BQ] - BQ2 S <11l1 - Q21loe.
(10)
where the supremum norm ||0||oc max [U:], and d is the dimension of vector According to Banach's 's fixed-point theorem [60]. Q converges to optimal action value Q" if we consecutively apply Q*. Furthermore, the update rule in Eq. (1), i.e. Q-learning, is
operator B Q. lim, (B) a sampling version that applies the 7-contraction operator B to Q. It can be viewed as a random process and will converge to Q", lim Qi Q", under certain mild conditions [61, 62, 63, 64).
In similar vein, we define the empirical Bellman (optimality) operator /3 for Eq. (2):
(BQ))s, Σ P(s'|s, +7 max (')(''a'))D
Q(5', (a))
(11)
E'ES
15

---

We prove Proposition 3.3 in three steps. Firstly, we demonstrate that ß is y-cotracctoon operator under supremum norm, and thus converges to the optimal action value Q", lim (B)) Q*
Next, we show that the sampling- based update rule Eq. (2) converges to Q", lim Q = Q*
Finally, we illustrate the greedy policy derived from Q" optimal for M if the optimal trajectory for M is included in M.
Lemma A.1. The operator B defined in Eq. (11) is y-contraction operator under supremumn norm,
[|B
BQ2 loc S 7 - Q211oo
(12)
Proof. We rewrite [|BQ, - BQ2lloo as follows:
||
BQ
max
Σ ((s'(s,a)lr++
max
Qi(s', P(s max
+7 + a
22(6',
8,a
of (s
Σ P( a
@2(s',a))) ab-(e',as)ED
max
y
max DED
max
8,0
#'ES
Σ
P(s" a.
(s
(2(5',0b))
max
max JF
max
3'ES
max 7
Σ
((s'(s,a)
max aJED
Q - 22(5' a)
8,0
S'ES
Σ
((( (2(3,a)
max
max 8.0:(B,a)ED
8,0
S'ES
Σ
P(s"|s, s, a))ss 22110
max 8,0
SE
=7 1211or
(13)
where the last equality is due to Eves (() =
L
To demonstrate that the sampling-basd -ased update rule in Eq. (2) converges to Q", utilize an auxiliary result from stochastic approximation [62, 63].
Theorem A.2. The random process } taking values in R" and defined as
(++1(x)= = (1 ar (z)) + ((())
(14)
converges to zero with probability under the following conditions:
(1)0 S $ 1, E, ax(x)) сo and Σ. (z) < xo;
(2) [E[ S >/],,|l.. with 7
(3) Var [ar(F(())]F]]] S C(L+ )1 C >
W is norm. In our proof it supremum norm.
Proof. See [62, 63].
Lemma A.3. Given any initial estimation Qa. the following update rule: Qc(5+41,a) - Qc(se, (15)
Qu41(se, az) Qe(s,, a:) + ae(xe; or) +
max
converges w.p.1 to the optimal action-value function Q-
0 H a 1,, Eae(s, and Σ (s) < <0,
for all (s, SxA
16

---

Proof. Applying Theorem A.2, we can demonstrate the convergence of the update rule in Eq. (15). Rewriting Eq. (15), we get
Q1+1 at) = (1 - (s,,,, az) ( ar) + ae( +7 max
(c(5++1,a)
(16)
Subtracting (*t,)a))) ax) from both sides yields:
Q1+1 a+) - Q' ae)
(1 (1-ac(St, a
Q (st, (i)) ai) +y max
Qc(5441, (st, a:)
(17)
Let's define
-(s
(18)
and
Fs(s =(t,a))r+t?
max d'=(s'(a'EDD
2, - (')
(19)
This results in the same random process as shown in Theorem A.2 Eq. (14). Therefore, proving lim;- Qi = Q' is equivalent to demonstrating that A a) converges to zero with probability 1. We only need verify that the assumptions Theorem A.2 are satisfied under the definitions of Eqs. (18) and (19).
The first assumption of Theorem A.2 aligns with the condition in Lemma A.3. This can be easily achieved by choosing (s,s, a) 1/t, for instance.
For the second assumption of Theorem A.2, we have
E a(F((s.))FFl) = ' P(s'ss, +
- - as)
max (E)
s'ES
(BQ,))s a) - ()((s))) a)
(20)
-BQQ)) a) (BQ')(sso)
Thus,
())] 11(BQ.) -BQ2") 1|
Sr11@ @01100
(21)
with 7 < 1.
For the third assumption of Theorem A.2, we obtain
Var(F( FFF - [(
(s) - ((BQ)) (BQ)))))((Q"(s.))))
Err + Y max
a'ss'aa') -s((ss)) -(BQQ)(s. (8Q)),s
Q (s) -Eir + max ('
Varlr max ED
(22)
To align with the RHS in the third assumption of Theorem A.2, we add and subtract Y maxa'(essa)eD Q' (8', ,a) term:
Varlr max (")
@" +7 +y max
a''s',
max ('(s'''')
(23)
d')
ari EE)
Given that r is bounded, it follows that r + ? max. (s' ED Q- (8', a') is also bounded. Moreover, the second part max,'ss'. Q((s',a') max (s' J'E ¹- (s', al) can be bounded by | lloe with some constant. Hence, obtain
Var(F((s) C(1+ A.
(24)
17

---

for some constant C > O under the supremum norm. Therefore, by Theorem A.2, A, converges to zero with probability implying that Q. converges to Q* with probability 1.
Finally, when we derive the greedy policy from Q' by selecting the action with the highest value at each state R* arg m (s(ss o.,, #* is optimal for the empirical MDP M.. If the optimal trajectory for M is included in M, then this trajectory is optimal for M, i.c & will select actions following that trajectory. Therefore, in this case, the greedy policy derived from Q* is also optimal for M.
Proposition 3.4. Assume M has deterministic transitions. If (Dx) are datasets collected from M with Dj C D2 C ... C Dn and corresponding empirical MDPs {Mi}, then Qi S Q3 S S U
Proof. Consider two datasets D, C Dj and their corresponding empirical MDPs M,, Let B. and Bj be the corresponding empirical Bellman operators. We have:
(s, = Σ P(s'|s, ar + max
()'s
a'i("'aa')DD
s'ES
(25)
(s, = Σ P(s' (s)lss))]r++ +y
()'s' a')].
max (
x'ES
Where the transition probabilities P(s'18, a) are the same for both B, and By. Then, we can write: (s. ()) B,0) a) (s,
Σ P(s|(s,a)(r+)
Σ P(s +7
()) (7(5(,a6)1
max
e'ES
s'ES max
Σ P(s'ls, max (ED
(7 df
FEES
Σ P(s'ls, d(( (Q)(6',)) ((((a))
Q7 (.)
dfAdaT)EDD (5((
FES
< Σ P(s'|s,a)7
max a((aa)EDD
7 Σ P(d'(s, (5,ā)ED
(Q:(5,)) (5)
max
e'ES
max (a.a)ED,
(Q) a) (3(,,)) =7 max (a,)ED)
() -Qjssa))Q(((,.)) (s)
(26)
By repeatedly applying the inequality, we get
(i,,))) ()) s max (s,a)D,
(s, Q(.
s y max (r max (MO)ED, (s,0)ED
= -(((,))))(() = max
a)) (7(s,a))
(s.a)ED
<
S 2n" max (M.))D
(27)
Taking the limit on both sides and considering that 0 < 7 < 1, we obtain (s) - (s,,,a) 50.
ie., (s, a) $ (s.
Then for Di C D2 .... C Dn, and their corresponding empirical MDPs {Mi}, we have Qi < Q3 < ... < Q;
18

---

B Experimental Details
B.1 Cliffwalk
Environment Details. Cliffwalk is a simple navigation task introduced by [26] and is depicted in Fig. 8. The agent's objective is to navigate from the bottom-left state to the goal state (G) located at the bottom right. The environment consists of 48 states, represented as wwo-dimensional coordinate axes and y. In our experiments, correspond to the grid's shape, while the denotes three channels representing specific game objects. The first channel shows the goal's position, the second channel shows the cliff's position, the last channel shows the agent's position. The action space comprises 4 directions: left, right, up, and down. The reward system is as follows: reaching the goal yields +1, falling into the cliff results -1, and all other actions result in O. We set the discount factor to 0.99 and the maximum episode steps to 100, as per [49].
present it a 4 x 12 3 binary array. The dimensions 4 12
Actions:
S
The Cliff
G
Figure Illustration of the CliffWalk environment. Fach grid represents state, and the arrow indicates the optimal path from the start state (S) to the goal state (G).
The advantage of using a simple example like this is that we can pre-compute the optimal value and policy for better understanding. Fig. displays the optimal value for each state-action pair. Each grid contains four numbers in different directions, corresponding to the action values for the four actions: left, right, up, and down. The values, rounded three decimal places, are highlighted in orange if they are optimal.
0.869
0878
0.086
0,895
0,904
0,914
0.923
0,512
0.941
0.951
0.61
0.97
0,869 0.578
0.69
0.88
0.878
0.895
0.886
0.904
0.898
0.914
0.904
0.523
0.90200225
09410.922
0.951
0.441 0.961
0.551 0.97
0.963 0.97
0.878
0.886
0.886
0.904
0.914
0.923
0.822
0.941
0.511
0.961
0.97
0.88
0.869
0878
0.886
0.895
0,804
0.814
0,23
0.922
0941
0.861
0.61
0.97
0,878 0.586
0.78
0.855
0.886
0.904
0.895
0.914
0.004
0.923
0.514
0.992..923
0.4109922
0.551
0941
0961
0.551 0.77
0961
0.8
0.97 0.8
0.886
0.885
0.004
0.914
0.923
0.882
0.541
0.951
0.61
0.97
0.98
0.99
0.878
0.86
0.885
0.904
0.014
0,923
0.82
0.941
0.51
0.961
0.7
0.98
0,888 0.505
0.886
0.004
0.855
0.914
0.904
0.923
0.914 -1
0.932
0.923
0.541
0.982
18510991
0.861
0.07 0.511
0.961 0.88
0.7 -1
0.00
0.98 0.99
0.878
-1
-1
-1
0,878 -10
0.886
The Cliff
G
0.878
Figure 9: The optimal action value for each state-action pair. Each grid represents a state, with numbers in each direction indicating the action value for that state. The values in orange show the optimal actions.
Implementation Details. We train two DRL agents based on the Bellman update in Eq. (1) and the in- iampalll Bellman update in Eq. (2). We use convolutional neural network that consists of a convolutional layer, followed by fully connected layer. The convolutional layer has 16 3 x convolutions with stride 1, the fully connected layer has 128 units. The optimizer for the network Adam [65] with a learning rate of le-4. We fill the replay memory with different transitions to simulate various scenarios. Detailed results are given in Appendix C.I.
19

---

000
DOOO
DOOO
A
A
(a) Asterix
(b) Breakout
(c) Freeway
(d) Seaquest
(e) SpaceInvaders
Figure 10: Visualization of Atari environments.
B.2 Arcade Learning Environment
Environment Details. The Arcade Learning Environment (ALE) [24] is a platform for evaluating the development of general, domain-independent AI technology. provides interface large number of Atari 2600 game environments with image input and discrete action space and with variety of diverse mechanics. We show the visualization of some games in Fig. 10. Please refer to [24, 66] for more details.
Implementation Details. We the same network for each algorithm in the original paper. We search the learning rates for baselines among ( 1e-3,3e-4,1e-4 and report the best performance. For method, fix the learning rate lc-4 and search regularization parameters (0.05,0.1.0.. 1,0.5). We run each experiment with 5 different random seeds. Each run consists of 10 million steps of interaction The performance is evaluated by running 30 episodes after every 100k environmental steps. We proportionally reduce other parameters based on the interaction steps. The e-greedy exploration is linearly decayed from to 0.01 in million steps. The target network is updated every 1000 steps. The replay memory size is set as 100,000. The minibatch size is 32. The replay ratio is 0.25 [67], that is the Q function is updated once per four environmental steps. The optimizer for the network is Adam. The discount factor 0.99, Table I shows the details of parammerrs that used for all methods.
Atari games and 2 million steps of interaction MuJoCo tasks.
Table 1: Hyper-parameters of DQN on Atari environments.
Hyperparameter
Value
Hyperparameter
Value
Batch size
32
Optimizer
Adam
Replay memory size
100,000
Initial exploration
Target network update frequency
1,000
Final exploration
0.01
Replay ratio
0.25
Exploration decay steps
IM
Discount factor
0.99
Total steps in environment
10M
B.3 MuJoCo
(a) Ant
(b) HalfCheetah
(c) Hopper
(d) Swimmer
(c) Walker2D
Figure 11: Visualization of MuJoCo enviromments.
20

---

Environment Details. MuJoCo [25] stands for Multi-Join dynamics with Contact. It is general purpose physics engine that aims facilitate research and development in robotics. There are eleven MuloCo environments in total, and we choose eight of them in our experiments: Ant, HalfCheetah, Hopper, Humanoid, InvertedDoubleeennduum
Reacher, Swimmer and Walker2d. All of these environments are stochastic in terms of their initial state, with Gaussian noise added to a fixed initial state in order to add stochasticity. The state spaces for MuJoCo environments in Gymnasium [35] consist of two parts that are flattened and concatenated together: position of body part or joint and its corresponding velocity. Often, some the first positional elements are omitted from the state space since the reward is calculated based on their values, leaving it up to the algorithm to infer those hidden values indirectly. The action space is a vector that bounded within -1 and 1 for each dimension. Reward functions vary for each tasks. Please refer to [25, 35] for more details.
Implementation Details. For continuous control tasks, we compare our method with SAC [18, 39], TD3 [17], TRPO [40] and PPO [41]. SAC and TD3 are actor-critic methods that learn a Q network and policy network. TRPO and PPO are policy-based methods that only learn a policy network. We use the same network and parameters for each algorithm as in the original paper. Actor network has tanh function before the final output, to control the action range at each dimension within [-1.]]. Our method is based on TD3, we maintain TD3's parameters the same original paper [17] and search our particular parameter a E (0.05,0.1,0.55) Other common parameters are shown in Table 2. We each experiment with different random seeds, and show the mean score and standard deviation with solid line and shaded area. Each run consists of 2 million steps of interaction on MuJoCo tasks. The performance is evaluated by running 10 episodes after every 10k environmental steps. The action is the output of mean value estimate without randomness.
For these baseline algorithms such as SAC?, TD3² and XQL we use their official code. We also refer some awesome public codebases such as RLzoo [68], Tianshou [69] and Dopamine [70]. We run all experiments on a server with Intel CPUs (Intel(R) Xeon(R) CPU E5-2650 v4 @ 2.20GHz) and NVIDIA GPUs (NVIDIA A5000). Each Atari experiment takes about one day, and each MuloCo experiment takes about half day.
Table 2:
of TD3 on MuJoCo environments.
Hyperparameter
Value
Hyperparameter
Value
Batch size
256
Target update rate (r)
0.005
Replay memory size
1000,000
Policy noise
0.2
Discount factor
0.99
Noise clip
0.5
Optimizer
Adam
Delayed policy update frequency
2
Learning rate
3 10-4
Total steps in environment
2M
Additional Experimental Results
C.1 Toy Example on CliffWalk
We provide in-depth discussion considering the replay memory containing different state-action pairs. We examine four cases:
(1) The replay memory only contains a failed trajectory and misses most of state-action pairs.
(2) The replay memory contains a sub-optimal trajectory and misses many state-action pairs. The replay memory contains optimal transitions but misses some sub-optimal state-action pairs.
(4) The replay memory contains optimal transitions and nearly all state-action pairs.
In each case, the replay memory is fixed. The first row in Fig. 12 shows the four cases. In this toy example with finite sate-action space, we can track which actions are taken and which are not at
phttps://gicte http:////gghhaacccaaaa/////////a com/haaroojj//ac htttpe///gicubb..om//fjjjjiaai 'nttps://githul httpp:///gtthbb..co////9/9/////0 cwm.Div99/X0LL
21

---

state. We sample batches of data and take the max over all actions to learn Q, and constrain the actions in the replay memory to learn Q.
The second row plot the error curves between Q, Q and Q", र A(Q1, Q2) denotes the average absolute enror on state-action pairs in the replay memory between @i and Q2:
AQQ Q2)
1 D
E (s,e)D
(Q)(s,a) - Q2(s,
(28)
We run five random seeds, the solid line shows the mean value and the shaded area shows standard error. clear to find that AQ,Q"" converges to O, while Q neither converges to Q* nor Q- In particular, when we have (s, a) = Q (s. a) a(s E D. Q converges to the global optimal while Q still failed due missing transitions. This highlights that the Bellman update is heavily affected by missing transitions, and the generalization of function approximation cannot correct it.
The last two rows present the final policies derived from Q and Q after learning. Red arrows represent actions that neither follow the optimal value Q" nor Q' The blue shading indicates the action values. We can observe that with function approximation, the policy based on the Bellman update cannot learn the (sub)optimal actions and overestimates action values. While the in-sample Bellman update converges to Q and learn the best possible polices. When there case, Q still targets on current samples and converges Q*
successful samples in the first
Swilekcton Pairs in Memory
StiinAction Parra in Memory
Statedcttoon Paira in Menory
Stace de
Pain in Hemony
TraCl
Edimaton Phirsin Manury
Extmation Emeran in Memory
Extmation Manury
Extratioon Enoo Pains Memory
20.0)
60.00
wo.chi ao d:
61 ar d>
1.0
30.00
-0.00
0.6
0.6
w5. eal d1 a0.0
0.4
04
0.2
0.2
0.0
Slape
Stnce
Tolay Derived t
Palo Defeed Tem
Deliee fun
ThaCll
The
TraCie
In the CliffWalk scenario, the rewards are as follows: +1 for reaching the goal. -1 for falling into the cliff, and 0 otherwise. The first row illustrates four cases with increasing transition coverage in the replay memory. The second row shows the errors during the learning process. The third and last rows present the final policies derived from Q and Q. Red arrows represent incorrect actions that neither follow Q" nor "" The blue shading indicates the action values.
Figure 12:
22

---

C.2 Overall Performance
We present the performance improvement eurves for all environments when our method is applied to DQN and TD3 in Figs. 13 and 14. The solid line represents the mean score, and the shaded area indicates the standard deviation. Q online is the IQL agent we online that follows the learning rule Eq. (2) learn Q. DQN and TD3 are agents that adhere to the learning rule Eq. (1) to learn Q- While Q online aims solve the empirical MDP, it lacks the exploration that expands the MDP. DQN and TD3 have exploration mechanism such as e-greedy and random noise, but they do not target the empirical MDP. Our method learn both Q and Q, encompassing both steps of the Empirical MDP Iteration: solving the empirical MDP and augmenting the empirical MDP. Our method demonstrates significant improvement on all kinds of tasks compared with the methods that only learn Q or Q. This suggests that the Empirical MDP Iteration an effective enhancement for current DRL methods, and both steps are crucial for performance.
Next, present the learning curves in comparison with other baselines in Figs. 15 and 16. The mean score and the standard error are represented by the solid line and shaded area, respectively. Our method either outperforms is equivalent to (within a 10% difference) the best baselines most tasks. Especially on MuJoCo tasks, our method outperforms other basclines by a large margin. These results validate our intuition and demonstrate that Empirical MDP Iteration is superior approach than focusing on the original MDP from the beginning. It avoids bootstrapping error and thereby enhances sample efficiency.
PaDio
FUT non
unive
D01
DGA
200
1500
Coegh
Hil 00%
855
250
Figure 13: The performance improvement Atari environments.
23

---

Son M
2700
900
196
12000
Figure 14: The performance improvement on MuJoCo tasks.
430
D01
12
(M
1100
11000
1000
2005
300
1150
LNTTA
11000
11233
UM CCM
2000
180
Figure 15: Overall performance on Atari environments. The learning curves show mean scores across 5 seeds and shaded area shows standard deviation.
24

---

120
230
30
640
1100
.100
Figure 16: Overall performance on MuJoCo environments. The learning curves show mean scores across 5 seeds and shaded area shows standard deviation.
XO T8O
Figure 17: Performance on 20 Atari games and 8 MuloCo tasks, with each method's score normalized between 0 and EMIT outperforms or matches (within 10% margin) the best baseline results in 19 of the 28 tasks.
C.3 Analysis of Estimation Error
To determine whether the estimation or bootstrapping error is a ubiquitous issue on more complex environment, we run DQN and TD3 on Atari environments and MuJoCo tasks. These are based on the Bellman update in Eq. (1), and we denote the policy as т. We concurrently learn another IQL agent based on the in-sample Bellman update in Eq. (2), denoting the policy म. The policy ı interacts with the environment and collect data into a replay memory, from which both π and a learn. As result, both policies are learned with the identical dataset.
Figs. 18 and 19 shows the evaluation performance of π and f. We find that स performs similarly or even better than most of the tasks. These results may seem counterintuitive, as active learning is commonly considered superior to passive learning [43]. This indicates that the in-sample Bellman update can learn good policy from given data without active interaction with environments. On the contrary, the active policy π does not fully utilize collected data and cannot find the best possible policy due bootstrapping error. This highlights that bootstrapping from out-of-sample actions impedes sample-efficient learning and there should be room to improve it.
Next, we demonstrate that regularizing Q with @ significantly reduces the estimation error in Q. Estimation bias has long been problem in value-based methods due to the combination of deep neural networks with the maximization operator in the Bellman optimality equation [20, 21J. Our method effectively eliminates overestimation or underestimation, achieving nearly accurate estimation throughout the learning process. This implies that there is almost no bootstrapping error, whether induced by the maximization operator or erroneous target estimation. At each evaluation. we obtain the true discounted Monte Carlo return Qree by running the current policy for 30 episodes and computing the actual discounted cumulative rewards at each state-action pair: Q (St, a+) = ''',n'r 7'T,. We then compute the averaged estimation difference between the learned Q and ground truth Qrae. (airQQ, Qree) = 1 set of evaluation trajectories, (T) denotes the total number of state-action pairs in T. We compute Vai for our method and compare it with DQN and TD3.
[s.aa]] E(s.))77 (Q(s, a) - Qnee (s, a)), where T is the
Figs. 20 and 21 show that our method reduces the estimation error for most environments and keeps the difference near zero, indicating that the estimation quite close to the true value and there is no serious overestimation or underestimation.
25

---

100
1.00
Gumblooe
313
10000
12000
2300
14
Kough
12:03
1.20
220
Figure 18: We run a DQN agent to interact with the environment, and concurrently learn action value networks Q (DQN) and Q (IQL) with the same data. The curves show the performance of argmax policies of Q (r) and Q (7).
850
120
1.59
300
Figure 19: We run a TD3 agent to interact with the environment, and concurrentyy learn an IQL agent with the same data. The curves show the performance of TD3 (π) and IQL. (#).
26

---

3-4
Figure 20: Estimation error on Atari environments. We compute the average difference between the estimated Q value and the ground truth value during learning.
INT
(M2 722
34
2007
Figure 21: Estimation error Mujoco environments. We compute the average difference between the estimated Q value and the ground truth value during learning.
27

---

C.4 Analysis of Policy Churn
Policy churm refers to the rapid change of the greedy policy in value-based reinforcement learning [34]. This phenomenon is primarily caused by deep learning with high-variance updates. Most of this policy change could be unnecessary, especially when learning converges. The per-state policy change between policies т and n' is defined as:
W(T, x1s) = ; Σ m(ass) n (a(ss))
(29)
2
where 0 (=, S 1. When and x' are greedy policies derived from action-value functions, W = if and n' choose different actions, otherwise (TT >'|s) = O. Thus it is simply a count of different actions after step update. In agents that use target network which is older copy of the online network, it is easy to measure W (TT, x/|s) by comparing their argmax actions at the points in training where the target network lags behind by just one update.
When the target network lags behind by one update during the learning, for example at time step i, we sample batch of data D and compute the average policy change W (T mT) [D] ΣxED (T Tels), where [D] is the size of the batch data. Then we compute the average
policy change over the whole learning process as W |T Exer Wt, where T is the set of time steps that the target network lags behind by one update during the learning.
Fig. 22 shows the policy change on Atari environments. We can conclude that our method reduces policy churn compared to DQN. Policy churn is not entirely undesirable it can also be potentially beneficial form of implicit exploration. However, the frequency of change that benefits learning is still unclear and deserves further study.
00
33
EMIT DOM
6.01
JA
10
DF 2004
En .00
now
$0.00
0.55
EMIT CCM
Enfiiiy C00
422
10
FoST COCK
330
3.0
60
2400
12
Figure 22: Policy churn curves on Atari environments. We compute the average policy change at each time step when the target network lags behind by one update.
28

---

C,5
Ablation Study
Our method comprises two parts, the regularization term determined by parameter a, and the exploration term designed based on ó(s, a). Figs. 23 and 24 illustrate the role of each part of our method. w/o reg term denotes that we set a O. w/o explore term means we do not use our exploration mechanism. w/o both refers to the backbone methods without our two improvements. full method employs both improvements. We observe that both parts enhance the learning. The performance decreases more without regularization, indicating that following the empirical MDP iteration, the current exploration mechanisms such as c-greedy and random noise can make notable improvements. Adding advanced exploration mechanism can further enhance the performance.
Fal Nettin repirciinn
1000
Biu
exportiio
M4.2
D353
+1200
12:00
190
4.00
Figure 23: Ablations on Atari environments. Both the regularization and the exploration mechanism benefit the learning.
2700
1200
Figure 24: Ablations on MuJoCo environments. Both the regularization and the exploration mecha- nism benefit the learning.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction accurately reflect the paper's contributions the field of online reinforcement learning.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the computational efficiency of the proposed method, the assump- tions made in the theoretical results, and the applicable scope of the method.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
30

---

Answer: [Yes]
Justification:
We provide all the assumptions and proofs in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide all the details needed to reproduce the main experimental results in the appendix, such as the hyperparameterss the training details, and the evaluation metrics.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
31

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.ce
guuides/CoeeSumisse
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips. wttpccccpppppccctccccccccccccccc /ttp///gggdd////duuuuiinnnnn /wt////oddsssiiiiooooooo ssiiiioossiiiyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We specify the parameters for baselines and our method, and the training details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report the standard deviation in the figures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
32

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ete:///nerrrre hctpppbcc///hhhcccssiieeeee.ee
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics and believe that our research conforms
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
33

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the original papers and provide the link to the code in the main text and the appendix.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
34

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "jMl1Hrq5eJ", "reviewer": "Reviewer_jQwU", "summary": "The authors transfer insights from IQL to online RL, demonstrating the performance of online RL can be enhanced by leveraging a Q-function that performs a max only over actions in the replay buffer when updating the Q-network. They use this network to:\n* encourage exploration by driving the agent towards state-action pairs where the value predictions between a traditional Q-network and the IQL style Q-network differ\n* they regularise the value predictions of a Q-network with a term equal to the difference between a traditional Q-network and an IQL style Q-network's value prediction\n\nOverall, I like the paper and think it should be published.", "questions": "Why integrate into TD3 instead of SAC when as far as I know SAC seems to outperform TD3?", "limitations": "The authors do discuss the limitations briefly in the conclusion, but I think having a larger limitation section where they are discussed more thoroughly would improve the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "* The authors demonstrate improved empirical performance on an impressive number of environments.\n\n* They also perform ablation studies to analyse why their approach improves on previous methods (by considering how for example it reduces policy churn or how it improves the accuracy of Q-network value predictions).\n\n* They provide theoretical results surrounding the convergence of EMIT and how it relates to Q-learning", "weaknesses": "* prior to reading this paper, I did not know how IQL worked. For example, it was initially confusing to me how an update like equation 2 could be done in continuous state spaces where you are unlikely to encounter the same state twice. I think a little bit more explanation of how this approach works (for example around equation 3) would help a reader like me that is not very familiar with the related work.\n* it seems there are some insights that initially I thought we generated originally from your work but now I understand (e.g. Eq(2)) builds of prior work (IQL). Maybe that would be obvious to some but I think it would be good to make explicit your contributions compared to IQL etc\n* Pretty hard for me to parse figure 4. I think something more suitable would show some summary statistics aggregated over all environments (with the bar charts in the appendix). Also why no error bars in figure 4?\n* Would be interesting to see how it compares to basic regularization techniques (e.g. weight decay) and slightly more sophisticated methods for exploration (e.g. those that use intrinsic rewards). For example on venture it appears that the exploration term is contributing a lot to the improvement (possibly because it is a difficult environment in terms of exploration). I am not suggesting that EMIT must beat these methods, I just think it would add some context for the reader.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Why integrate into TD3 instead of SAC when as far as I know SAC seems to outperform TD3?\n\nWe integrate EMIT with DQN and TD3 mainly because they are directly built upon optimizing value-based Bellman equations, which aligns with our theoretical analysis and is exactly we aim to improve with EMIT. SAC, on the other hand, is originated from maximum entropy reinforcement learning with an entropy term. It is possible to implement EMIT with SAC. To show that, we've experimented EMIT with SAC, discovering that EMIT similarly enhances SAC's performance (Fig.1(a) in the rebuttal pdf).\n\n- a little bit more explanation of how IQL works\n\nWe appreciate the suggestion and will incorporate a more detailed explanation of IQL in the revised manuscript.\n\n- it would be good to make explicit your contributions compared to IQL etc\n\nEMIT is a novel framework that iteratively solves a sequence of empirical MDPs, enhancing existing online RL algorithms. Other existing offline methods that solve empirical MDPs alternatively than IQL can also be adopted when instantiating EMIT. We will make this point more explicit in the revised manuscript.\n\n- summary statistics aggregated over all environments, and error bars in figure 4\n\nWe summarize the aggregated results over all environments in Fig.2 in the rebuttal pdf. We will add error bars in fig.4 in the revised manuscript.\n\n- how it compares to basic regularization techniques (e.g. weight decay) and slightly more sophisticated methods for exploration (e.g. those that use intrinsic rewards).\n\nWe appreciate the suggestion. In our current study, we concentrate on the theoretical analysis and empirical validation of the EMIT framework, employing a straightforward instantiation to showcase its efficacy. Indeed,  We aim to explore more sophisticated methods for exploration and regularization in our future research.\n\n- a larger limitation section\n\nWe value your suggestion and will elaborate more on the limitations of this work.", "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": "", "extra_scores": {}}, {"review_id": "CADQhxAwoU", "reviewer": "Reviewer_tCA6", "summary": "This paper introduces a novel framework called Empirical MDP Iteration (EMIT) to improve the stability and performance of reinforcement learning algorithms. Traditional reinforcement learning algorithms optimize a Markov Decision Process (MDP) using the Bellman equation, which can lead to unstable optimization when function approximation is used. And the EMIT framework addresses this by constructing a sequence of empirical MDPs from the replay memory and using an in-sample Bellman update to learn an estimated Q-function, denoted as $\\widehat{Q}$. As claimed in the paper, this method restricts updates to in-sample data, ensuring convergence to a unique optimal $\\widehat{Q}$ function and inducing monotonic policy improvement.\n\nThe paper demonstrates that EMIT can be integrated with existing reinforcement learning algorithms like DQN and TD3, acting as a regularizer to enhance their performance. The experimental results on Atari and MuJoCo benchmarks show that EMIT significantly reduces estimation errors and improves the performance of these algorithms. The authors provide theoretical analysis and extensive experiments to support their claims, highlighting the advantages of in-sample bootstrapping over traditional Bellman updates in reducing estimation errors and improving policy learning stability.", "questions": "1. How does EMIT fundamentally differentiate itself from existing methods like Implicit Q-Learning and In-Sample Actor-Critic?\n2. What are the limitations of the current exploration mechanism used in EMIT, and how does it compare to other advanced exploration strategies?\n3. Can EMIT be effectively applied to real-world reinforcement learning problems, and what are the potential challenges in such applications?\n\nI am willing to discuss and update my score until all the concerns are addressed.", "limitations": "The authors have discussed the limitations of their work, especially concerning the scalability and computational cost of maintaining and updating two Q-functions. However, the paper would benefit from a more detailed analysis of these limitations and their broader implications. Additionally, the potential societal impact of this research has not been thoroughly addressed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. **Comprehensive Experimental Evaluation:** The paper presents extensive experimental results on both discrete action space environments (Atari) and continuous control tasks (MuJoCo). The diverse set of benchmarks provides a solid empirical foundation to validate the effectiveness of EMIT across different types of reinforcement learning tasks.\n\n2. **Improved Stability and Performance:** The empirical results show that EMIT significantly enhances the stability and performance of existing reinforcement learning algorithms like DQN and TD3. By integrating EMIT as a regularizer, the paper demonstrates a clear reduction in estimation errors and notable policy improvements across various benchmarks.", "weaknesses": "**Limited Novelty in Core Ideas:** While the EMIT framework introduces in-sample bootstrapping for empirical MDPs, similar ideas have been explored in offline reinforcement learning and distributional reinforcement learning. The paper would benefit from a deeper differentiation from existing works, such as Implicit Q-Learning and In-Sample Actor-Critic. The authors should elaborate on how EMIT offers significant advancements over these methods beyond just integrating with online reinforcement learning algorithms.\n\nI recommend the authors clearly delineate the unique contributions of EMIT compared to existing methods like Implicit Q-Learning and In-Sample Actor-Critic. Providing a comprehensive discussion on the theoretical and practical advancements offered by EMIT would strengthen the paper’s claim of novelty.\n\n**Scalability Concerns:** The proposed framework requires maintaining and updating two Q-functions (Q and $\\widehat{Q}$) simultaneously, potentially doubling the computational and memory requirements. This scalability issue is not sufficiently addressed in the paper. The authors should discuss how EMIT can be efficiently scaled to more complex environments or larger state-action spaces without significantly increasing the computational burden.\n\n**Hyperparameter Sensitivity:** The paper lacks an in-depth analysis of the sensitivity of EMIT to its hyperparameters, particularly the regularization parameter $\\alpha$ and the exploration bonus $\\delta(s, a)$. Understanding the robustness of EMIT to different hyperparameter settings is crucial for its practical applicability. The authors should provide more insights or guidelines on how to select these hyperparameters in various scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Limited Novelty in Core Ideas. How does EMIT fundamentally differentiate itself from existing methods like Implicit Q-Learning and In-Sample Actor-Critic?\n\nThe main contributions shown in our work is that in online RL, iteratively solving a sequence of empirical MDPs is better than just solving the original MDP, especially when the data is incomplete. We develop a novel framework EMIT to enhance existing online RL algorithms by iteratively solving current empirical MDPs. We showcase the effectiveness of our framework by using it to combine established methods for in-sample learning (i.e., Implicit Q-Learning, In-Sample Actor-Critic) and well-known online RL algorithms (i.e., DQN, TD3).\n\n- limitations of the current exploration mechanism used in EMIT, how does it compare to other advanced exploration strategies?\n\nThe objective of exploration in EMIT is to grow the empirical MDP to better approximate the original MDP. Our current exploration mechanism employs the `principle of optimism in the face of uncertainty`, which has proven a useful heuristic in practice. However, its efficiency may wane when the environment is too hard to explore, or when estimated uncertainty is unreliable (e.g., in environments with a 'Noisy TV' problem [1]). In such instances, exploration methods like Go-Explore [2] or intrinsic motivation exploration [1,3,4] might be more suitable. We will discuss this in revised manuscript.\n\n[1] Burda, Yuri, Harrison Edwards, Amos Storkey, and Oleg Klimov. \"Exploration by random network distillation.\" arXiv preprint arXiv:1810.12894 (2018).\n\n[2] Ecoffet, Adrien, Joost Huizinga, Joel Lehman, Kenneth O. Stanley, and Jeff Clune. \"First return, then explore.\" Nature 590, no. 7847 (2021): 580-586.\n\n[3] Zhang, Tianjun, Huazhe Xu, Xiaolong Wang, Yi Wu, Kurt Keutzer, Joseph E. Gonzalez, and Yuandong Tian. \"Bebold: Exploration beyond the boundary of explored regions.\" arXiv preprint arXiv:2012.08621 (2020).\n\n[4] Jarrett, Daniel, Corentin Tallec, Florent Altché, Thomas Mesnard, Rémi Munos, and Michal Valko. \"Curiosity in Hindsight: Intrinsic Exploration in Stochastic Environments.\" arXiv preprint arXiv:2211.10515 (2022).\n\n- Can EMIT be effectively applied to real-world reinforcement learning problems, and what are the potential challenges in such applications?\n\nEMIT is designed to improve the performance of existing online RL algorithms. Thus, it should lead to improved performance on any `real-world` problems where existing online RL algorithms have shown to be effective. It is an interesting question on what kind of problems EMIT's advantage would disappear or unable to observe. We will try elaborate more on the limitations of EMIT in our revision. While EMIT could still encounter similar challenges as other RL algorithms, such as facing issues related to sample efficiency and safety, it is encouraging to note that EMIT not only boosts the sample efficiency of tested RL algorithms but also yields a more conservative estimate of the Q-function. This conservative estimation could potentially enhance the safety of the derived policy, positioning EMIT as a more preferable solution for real-world applications.\n\n- Scalability Concerns: The proposed framework requires maintaining and updating two Q-functions, potentially doubling the computational and memory requirements.\n\nWe recognize the added computation cost in the \"Limitations\" section of our manuscript. However, the good news is that EMIT does not asymptotically make existing online RL algorithms more expensive over time. We thus believe EMIT enjoys similar `scalability` property as the online RL algorithms it intends to enhance.\nFuture work to further improve EMIT's efficiency include designing an exploration strategy that is directly based on in-sample Bellman update, or improving runtime using two processes to update Q and $\\hat Q$ in parallel. Despite this limitation, as demonstrated in Figure 3 of our manuscript and summarized in the table below, EMIT still outperforms DQN and TD3 when using the same amount of computation, underscoring its efficacy in the current format.\n\n| | EMIT-DQN (5e6) | DQN (1e7) |\n| :-----| ----: | :----: |\n| Asteroids | 1338.9 $\\pm$ 27.8 | 948.6 $\\pm$ 61.9|\n| Atlantis | 1599569.9 $\\pm$ 231875.6| 910471.2 $\\pm$ 35727.5|\n| Breakout | 266.2 $\\pm$ 40.4| 103.3 $\\pm$ 8.0|\n| Gravitar | 949.7 $\\pm$ 14.9| 523.5 $\\pm$ 68.3|\n\n| | EMIT-TD3 (1e6) | TD3 (2e6) |\n| :-----| ----: | :----: |\n| Ant | 6059.5 $\\pm$ 427.4| 5216.2 $\\pm$ 720.1|\n| HalfCheetah | 13100.6 $\\pm$ 639.5| 11481.2 $\\pm$ 294.8|\n| Hopper | 3587.0 $\\pm$ 225.0| 2968.1 $\\pm$ 1145.1|\n| Humanoid | 5526.9 $\\pm$ 378.3| 5876.5 $\\pm$ 292.2|\n\n- Hyperparameter Sensitivity\n\nWe searched the best regularization parameter $\\alpha$ in the range of [0.05, 0.1, 0.5] shown in Fig.3 in the rebuttal pdf. We find that a small value such as 0.05 or 0.1 suffices for the effective operation of EMIT. Regarding the exploration bonus, it does not introduce any hyperparameter. As demonstrated in the manuscript Fig.6(b), incorporating the exploration bonus notably enhances performance.", "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": "", "extra_scores": {}}, {"review_id": "XtrZgqnpVe", "reviewer": "Reviewer_4uKn", "summary": "The paper introduces the Empirical MDP Iteration (EMIT) framework, which enhances online reinforcement learning by regularizing algorithms with a sequence of empirical MDPs derived from replay memory data. By focusing on in-sample bootstrapping, EMIT ensures stable and unique convergence of Q-functions, leading to monotonic policy improvement (shown for deterministic MDPs). EMIT can be integrated with existing RL algorithms, effectively acting as a regularizer. Experiments with DQN and TD3 on Atari and MuJoCo benchmarks demonstrate that EMIT significantly reduces estimation errors and improves performance.", "questions": "Can you plot $\\Delta (Q, \\hat Q) $ to see how far is Q from the empirical $\\hat Q$?\n\nIn the discussion on page 4, in particular, when you state that \"Q neither converges to Q* nor $\\hat Q^*$, does this depend on the initialization of Q? How did you initialize Q?", "limitations": "Added computational complexity from learning two Q-functions", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally easy to follow and clearly written.\n\nThe proposed approaches appear to be simple and relatively original.\n\nGood analysis and numerical results.", "weaknesses": "Reproducibility: The code was not provided in the supplemental material. \nRepresentation: The text in Figure 2(a) is very small and unreadable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Can you plot to see how far is Q from the empirical Q?\n\nWe plot the difference in Fig.4 in the rebuttal pdf. We find $\\Delta(Q,\\widehat Q)$ is similar to $\\Delta(Q,\\widehat Q^*)$ in the later stage of training since $\\widehat Q$ will converge to $\\widehat Q^*$.\n\n- when you state that \"Q neither converges to $Q^*$ nor $\\hat Q^*$, does this depend on the initialization of Q? How did you initialize Q?\n\nThere is no dependency. In the extreme case where Q is initialized precisely to $Q^*$, then Q will converge to $Q^*$. Otherwise, Q has no guaranteed convergence to $Q^*$ whatever its initialization is. In our experiments, we initialize the Q as a randomly initialized neural network.\n\n- code \n\nIn compliance with the rebuttal guidelines, which should not contain any links, we sent an anonymized link to the AC in a separate comment. We will open-source the code after the review process.\n\n- text in Figure 2(a) is very small and unreadable.\n\nThank you for pointing this out. We will increase the font size in the revised manuscript.", "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": "", "extra_scores": {}}, {"review_id": "rTWreB9kSQ", "reviewer": "Reviewer_eYau", "summary": "When using the Bellman update with incomplete data, the estimation error is hard to eliminate.\nTo solve this problem, the authors develop a novel framework EMIT, which can be used to enhance existing RL algorithms by iteratively solving a current empirical MDP for stable finite-time performance, and can progressively approach a solution to the original MDP.", "questions": "1. Can EMIT improve the performances of the recently proposed RL methods?\n2. For continuous control, e.g., MuJoCo, in most cases, the current state-action pair will not be in the memory buffer D.\nThus, $R = -\\infty$ for this state-action pair.\nHow to deal with this issue?", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "1. The experiment is performed on both MuJoCo and Atari.\n2.  Propositions 3.2-3.4 explain the estimation error in RL.", "weaknesses": "1. The running time of the different RL methods should be compared.\n2. The proposed method should be compared with recent RL methods, such as TD7 and CrossQ [1, 2].\n3. A head-to-head comparison between your memory buffer and the existing ones should be given [3].\n4. From Algorithm 1, it is hard to see the difference between the proposed method and the existing ones.\n\n\nIf the authors can present their contributions clearly and open-source the code, I will  increase my rating.\n\n[1]Fujimoto S, Chang W D, Smith E, et al. For sale: State-action representation learning for deep reinforcement learning[J]. Advances in Neural Information Processing Systems, 2024, 36.\n\n[2] Bhatt A, Palenicek D, Belousov B, et al. CrossQ: Batch Normalization in Deep Reinforcement Learning for Greater Sample Efficiency and Simplicity[C]//The Twelfth International Conference on Learning Representations.\n\n[3] Schaul T, Quan J, Antonoglou I, et al. Prioritized experience replay[J]. arXiv preprint arXiv:1511.05952, 2015.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- Can EMIT improve the performances of the recently proposed RL methods such as TD7 and CrossQ?\n\nWe instantiate EMIT with TD7, and results are shown in Fig.1(b) in the rebuttal pdf. We find that EMIT can enhance the performance of TD7 on Ant and get similar performance on HalfCheetah. It may because TD7 is already a very strong baseline on HalfCheetah. We will discuss TD7 and CrossQ to provide a more comprehensive comparison in the revised manuscript.\n\n\n- For continuous control, e.g., MuJoCo, in most cases, the current state-action pair will not be in the memory buffer D. Thus, $R=-\\infty$ for this state-action pair. How to deal with this issue?\n\nFor the in-sample Bellman update as in eq.(3), we sample (s,a,r,s',a') in the buffer for the update. This r is not $-\\infty$.\n\n\n- The running time of the different RL methods should be compared.\n\nWe compare the running time of EMIT with DQN and TD3 using Frame Per Second (FPS) in the table below. EMIT consumes nearly double the time of DQN and TD3.\n\n|| EMIT-DQN | Rainbow | DQN | IQN | C51 |\n|-| :-: | :-: |:-: |:-: |:-: |\n|FPS| 103.1 $\\pm$ 4.2 | 124.0 $\\pm$ 5.8 | 194.4 $\\pm$ 5.7 | 179.1 $\\pm$ 2.9 | 170.6 $\\pm$ 5.6 |\n\n| | EMIT-TD3 | SAC | TD3 | XQL | TRPO | PPO |\n| :-: | :-: | :-: |:-: |:-: |:-: |:-: |\n| FPS | 42.2 $\\pm$ 0.2 | 70.4 $\\pm$ 0.3 | 79.4 $\\pm$ 0.3| 68.2 $\\pm$ 0.5 | 108.9 $\\pm$ 3.1 | 166.6 $\\pm$ 3.5 |\n\nDespite this limitation, as demonstrated in Figure 3 of our manuscript and summarized in the table below, EMIT still outperforms DQN and TD3 when using the same amount of computation, underscoring its efficacy.\n\n| | EMIT-DQN (5e6) | DQN (1e7) |\n| :-----| ----: | :----: |\n| Asteroids | 1338.9 $\\pm$ 27.8 | 948.6 $\\pm$ 61.9|\n| Atlantis | 1599569.9 $\\pm$ 231875.6| 910471.2 $\\pm$ 35727.5|\n| Breakout | 266.2 $\\pm$ 40.4| 103.3 $\\pm$ 8.0|\n| Gravitar | 949.7 $\\pm$ 14.9| 523.5 $\\pm$ 68.3|\n\n| | EMIT-TD3 (1e6) | TD3 (2e6) |\n| :-----| ----: | :----: |\n| Ant | 6059.5 $\\pm$ 427.4| 5216.2 $\\pm$ 720.1|\n| HalfCheetah | 13100.6 $\\pm$ 639.5| 11481.2 $\\pm$ 294.8|\n| Hopper | 3587.0 $\\pm$ 225.0| 2968.1 $\\pm$ 1145.1|\n| Humanoid | 5526.9 $\\pm$ 378.3| 5876.5 $\\pm$ 292.2|\n\n- A head-to-head comparison between your memory buffer and the existing ones should be given [3].\n\nOur first-in-first-out (FIFO) memory buffer is identical to the ones utilized in DQN and TD3. We have not incorporated any advanced memory buffer.\n\n- From Algorithm 1, it is hard to see the difference between the proposed method and the existing ones.\n\nThank you for pointing this out. We will provide a more detailed description in the revised manuscript.\n\n- code\n\nIn compliance with the rebuttal guidelines, which should not contain any links, we sent an anonymized link to the AC in a separate comment. We will open-source the code after the review process.", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all the reviewers for their comments, suggestions for improvement, and interest in the paper. Besides the detailed responses to each reviewer's comments, we submit a rebuttal pdf to supplement our responses. This pdf includes four figures to address the reviewers' concerns. 
- Figure 1 shows the performance of EMIT with SAC and TD7, demonstrating that EMIT can also enhance the performance of other state-of-the-art RL algorithms. 
- Figure 2 summarizes the aggregated results over all environments, providing a clearer comparison between EMIT and the baselines. 
- Figure 3 shows the parameter sensitivity analysis of the regularization parameter $\alpha$, showing that a small value such as 0.05 or 0.1 suffices for the effective operation of EMIT. 
- Figure 4 plots the difference between the Q-function and the empirical Q-function, showing that $\Delta(Q,\widehat Q)$ is similar to $\Delta(Q,\widehat Q^*)$ in the later stage of training since $\widehat Q$ will converge to $\widehat Q^*$.

Meta-review: There is general agreement that the paper delivers a solid contribution to improving online RL performance. The reviewers have noted a number of presentation and clarification issues that the authors should address in the final paper.
Decision: Accept (poster)