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_cc_2024_Conference
Published: 2024-05-15 08:37:41

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.

Main paper: 
 introduction: 
 Reinforcement learning (RL) has achieved remarkable success across various domains, such as games [1, 2, 3, 4, 5] , robotics [6, 7, 8] and industrial applications [9, 10] , by modelling them as 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:Q(s, a) ← r(s, a) + γ max a ′ Q(s ′ , 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 or approximated by a parameterized policy [16, 17, 18, 19] . In practice, data coverage in the replay memory is limited to a potentially small subset of the whole state-action space, especially for complex environments. Indeed, the Bellman update in Eq. ( 1) suffers from estimation errors due to the combination of applying the max operator to out-of-sample actions and bootstrapping from a function approximator.In the examples in Fig. 1a , the well-known double Q-learning method [20] (a) Comparison of double Q technique with empirical Q. We train Double DQN [21] and TD3 [17] with the double Q technique. Concurrently, we learn Q based on Eq. ( 2). The graphs show the difference between the Q value and discounted Monte Carlo return. Greater/less than 0 means overestimation/underestimation. The double Q technique overestimates on Breakout but underestimates on HalfCheetah. Q yields much more accurate estimation on both tasks. 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 is 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 is 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 in-sample actions without querying the values of 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 a replay memory D collected from the environment.Q(s, a) ← r + γ maxEQUATIONThere is no out-of-sample bootstrapping in Eq. ( 2), and the solution in a 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 a 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. 1b . How to 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 Q. EMIT can be applied to any RL algorithms that can learn both Q and Q [23] . We implement and evaluate two variants based on 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 is guaranteed with growing data coverage if M is deterministic. These imply that Q can be a 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 MuJoCo [25] tasks. We show strong performance enhancements for both methods. Further analysis demonstrates that EMIT largely overcomes problems of estimation error. 
background: 
 Markov Decision Process (MDP). Reinforcement learning (RL) [26, 27] is a paradigm of agent learning via interaction. It can be modeled as a Markov Decision Process (MDP), a 5-tuple M = (S, A, R, P, γ). S denotes the state space, A denotes the action space, P (s ′ |s, a) : S ×A×S → [0, 1] is the environment dynamics, R(s, a) : S × A → R is the reward function which is bounded, γ ∈ (0, 1) is the discount factor. The goal of an RL agent is to learn an optimal policy π that maximizes the expected discounted cumulative reward E π [ ∞ t=0 γ t r t ]. Value-Based Methods. Q-learning is a classic algorithm based on the Bellman optimality equation Q * (s, a) = E [r + γ max a ′ Q * (s ′ , 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 a parameterized policy, which is suitable for continuous action spaces. The policy is updated by gradient ascent of a Q network, ∇ θ1 |B| s∈B Q ϕ (s, a θ ), a θ ∼ π θ (•|s), 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 RL [29] methods use Eq. ( 2) to approximate an 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:EQUATIONwhere L τ 2 (u) = |τ -1(u < 0)|u 2 is a weighted mean squared error loss, and Qθ is the target network.This asymmetric loss function defines the entire spectrum of methods between SARSA (τ = 0.5) and Q-learning (τ → 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 is straightforward to implement based on these offline methods.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 assumptions made in the theoretical results, and the applicable scope of the method.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
empirical mdp iteration: 
 A replay memory D is maintained to 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) ∈ D if ∃ (s, a, r, s ′ ) ∈ D and s ∈ D if ∃ (s, a, r, s ′ ) ∈ D or ∃ (s, a, r, s) ∈ D. A visit count N (s, 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. is the empirical transition dynamics based on visit counts in D, and γ ∈ (0, 1) is the discount factor.The empirical MDP M contains all information we can obtain from D. If a (state, action) pair is not in the data, its reward is set to -∞ 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-sample transitions, thereby influencing the convergence process. This indicates that the Bellman update is heavily influenced by the values of unseen state-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 a 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 infinietely 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 a toy example on CliffWalk [26] in Fig. 2 to illustrate the difference between the two update rules. CliffWalk is a simple navigation task. The goal is to reach the state G at the bottom right starting from the bottom left. The reward of reaching G is 1. Dropping into the cliff gives reward -1, and all other rewards are 0. We present two cases: (1) D contains a sub-optimal trajectory and misses many state-action pairs (Fig. 2a top left), and (2) D contains an 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. ∆(Q 1 , Q 2 ) denotes the averaged absolute error on state-action pairs in D betweenQ 1 and Q 2 . ∆( Q, Q * ) converges to 0, indicates that Q converges to Q * . However, Q neither converges to Q * nor Q * .In 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 on 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 a best possible policy.We solve each empirical MDP M i , defined by the current memory D i , and add data to 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 i } are datasets collected from M with D 1 ⊂ D 2 ⊂ • • • ⊂ D n and corresponding empirical MDPs { M i }, then Q * 1 ≤ Q * 2 ≤ • • • ≤ Q * n .This result is intuitive. With more transitions in the replay memory, we take the maximum over a wider range of actions, leading to a 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 a learning path to improve a policy. The guarantee of the convergence to a unique optimal value on existing transitions is a key property, which makes the in-sample Bellman update a 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 to learn even from optimal trajectories.Two major questions in EMIT are how to 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 utlize 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 a regularizer:EQUATIONHere, Q target = r(s, a)+γ max a ′ Q(s ′ , a ′ ), and α is a parameter controlling the level of regularization. Second, we add an exploration bonus to the algorithm'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 Q(s, a) should be closer at known than at unseen state-action pairs. Therefore, we 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:EQUATIONFor algorithms in discrete action spaces such as DQN, we can add an exploration bonus δ(s, a) to the greedy part of an ϵ-greedy policy: with probability ϵ it chooses an random action as usual, otherwise it selects an action that is greedy w.r.t Q(s, a) + δ(s, a):EQUATIONEq. ( 6) adds a targeted exploration mechanism to ϵ-greedy.For algorithms in continuous action spaces such as TD3, where the policy is assumed to be a unimodal Gaussian distribution, we use δ as a state-action dependent standard deviation and sample actions according to: a ← π(s) + ϵ, ϵ ∼ clip(N (0, δ(s, a)), -c, c), (7) The added noise is clipped to keep the target close to the original action [17] .Algorithm 1 shows pseudo-code for incorporating EMIT into a Q learning algorithm Alg. Blue text highlights the components added or modified by EMIT. EMIT maintains Q and incorporates it into the algorithm's action selection Alg.act() and Q update Alg.update(). Any method based on Eq. ( 2) can be used to learn Q. In our experiments, we apply implicit Q-learning (IQL) [30] . We learn Q using DQN [16] and TD3 [17] for discrete and continuous environments respectively. Clearly, Algorithm 1 should be more appropriate be viewed as a new framework, rather than a fixed algorithm. Alg.Select an action at = Alg.act(st, Q θ ) as Eq. ( 6) or (7) { Q guided exploration} 6:Alg.Execute at in Env and get rt, st+1 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: We will release the code upon acceptance.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experiments: 
 In this section, we present experimental results to 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 a 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 Q 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.Environments. We evaluate EMIT on Atari [24] and MuJoCo [25] tasks based on OpenAI Gym interface [35] . Atari provides a diverse set of video games, making it an ideal platform for evaluating the general competency of AI agents. The input for these games is image-based, and the dynamics are nearly deterministic. MuJoCo offers a 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 high-dimensional 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 is 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-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 α ∈ {0.05, 0.1, 0.5}. All other common parameters are set as detailed in Appendix B Tables 1 and 2 . Further details can be found in Appendices B.2 and B.3.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 We extend our comparison of EMIT with other strong baselines. For a clearer presentation, we display normalized scores. For each task, we define R max and R min as the maximum and minimum cumulative reward across all methods, respectively. The score for each method is then normalized using the formula (R -R min )/(R max -R min ).The overall performance on various tasks is presented in Fig. 4 . EMIT achieves the best average performance across these tasks. Specifically, EMIT either outperforms or is on par with (within a 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 a more effective approach than focusing on 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 out-of-sample actions.In contrast, EMIT seeks to 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.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 is 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 a policy π. Concurrently, we learn a policy π using another IQL agent with 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 is somewhat counterintuitive, as active learning is generally considered superior [43] . 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 out-of-sample transitions hampers sample-efficient 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 True , by executing the current policy for 30 episodes and calculating the actual discounted cumulative rewards, Q True (s t , a t ) = T t=t γ t r t . We then compute the average estimation difference between the learned Q and the ground truth Q True ,EQUATIONHere, T represents the set of evaluation trajectories, and |T | denotes the total number of state-action pairs in T . We calculate V diff for our method and compare it with DQN and TD3 on Breakout and HalfCheetah1 . 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 to 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 a 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 a potentially beneficial form of implicit exploration. The optimal frequency of change that could enhance learning remains unclear and deserves further investigation.Our algorithm design comprises two key components: the regularization term, determined by the parameter α, 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., α = 0. w/o explore term indicates the use of existing exploration methods, such as ϵ-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 a 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.  
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-learning [48] learns multiple Q functions to strike a balance between overestimation and underestimation. 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 solving Eq. ( 2). However, CEER is effective only when the constructed graph is 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 out-of-sample actions. Rainbow [38] integrates six enhancements to the DQN algorithm for improved empirical performance: double Q-learning [21] , prioritized replay [50] , dueling networks [51] , 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, 31] . Implicit Q-Learning (IQL) [30] estimates the value of the best available action at a 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). 
discussion and limitations: 
 We study the application of the Bellman equation as a learning objective in scenarios with incomplete data. Bootstrapping from in-sample transitions with Eq. ( 2) theoretically leads to a unique solution and significantly reduces the estimation error in practice, even with function approximation. We introduce a 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 a 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 is 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 is directly based on in-sample Bellman update to avoid out-of-sample bootstrapping and also taking the exploration mechanism into consideration.In this section, we analyze the property of the two update rules in Eqs. ( 1) and ( 2) for finite state-action space S × A discussed in Section 3.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.We illustrate the property using an example in Fig. 7 . The original MDP comprises two states {s 1 , s 2 } and two actions {a 1 , a 2 }. The memory D includes transitions {(s 1 , a 1 ), (s 1 , a 2 ), (s 2 , a 1 )}, but lacks (s 2 , a 2 ). Assuming a reward r(s, a) = 0 for all transitions for simplicity. In this case, the optimal action value for all state-action pairs in M and M is 0, i.e.,Q * (s, a) = Q * (s, a) = 0, a ∈ {a 1 , a 2 }, s ∈ {s 1 , s 2 }.However, the reward for the missing transition can take any value, leading to an infinite number of (2) uniquely converges to the optimal value Q * for the empirical MDP M in the limit of infinietely 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.MDPs M i ̸ = M,We first present the established results for the Bellman update in Eq. ( 1), and then provide a three-step proof for Proposition 3.3.The Bellman (optimality) operator B for Eq. ( 1) is defined as:EQUATIONPrevious works have demonstrated that the operator B is a γ-contraction with respect to the supremum norm:EQUATIONwhere the supremum norm ∥v∥ ∞ = max 1≤i≤d |v i |, and d is the dimension of vector v. According to Banach's fixed-point theorem [60] , Q converges to optimal action value Q * if we consecutively apply operator B to Q, lim n→∞ (B) n Q = Q * . Furthermore, the update rule in Eq. (1), i.e. Q-learning, is a sampling version that applies the γ-contraction operator B to Q. It can be viewed as a random process and will converge to Q * , lim t→∞ Q t = Q * , under certain mild conditions [61, 62, 63, 64] .In a similar vein, we define the empirical Bellman (optimality) operator B for Eq. ( 2):EQUATIONWe prove Proposition 3.3 in three steps. Firstly, we demonstrate that B is a γ-contraction operator under supremum norm, and thus converges to the optimal action value Q* , lim n→∞ (B) n Q = Q * .Next, we show that the sampling-based update rule in Eq. ( 2) converges toQ * , lim t→∞ Q t = Q * .Finally, we illustrate the greedy policy derived from Q * is optimal for M if the optimal trajectory for M is included in M. Lemma A.1. The operator B defined in Eq. ( 11) is a γ-contraction operator under supremum norm,EQUATIONProof. We rewriteEQUATIONwhere the last equality is due to s ′ ∈S P (s ′ |s, a) = 1.To demonstrate that the sampling-based update rule in Eq. ( 2) converges to Q * , we utilize an auxiliary result from stochastic approximation [62, 63] .Theorem A.2. The random process {∆ t } taking values in R n and defined asEQUATION) converges to zero with probability 1 under the following conditions:(1) 0 ≤ α t ≤ 1, t α t (x) = ∞ and t α 2 t (x) < ∞; (2) ∥E[F t (x)|F t ]∥ W ≤ γ∥∆ t ∥ W , with γ < 1; (3) V ar[F t (x)|F t ] ≤ C(1 + ∥∆ t ∥ 2 W ), for C > 0.W is a norm. In our proof it is supremum norm.Proof. See [62, 63] .Lemma A.3. Given any initial estimation Q 0 , the following update rule:EQUATIONconverges w.p.1 to the optimal action-value functionQ * if 0 ≤ α t (s, a) ≤ 1, t α t (s, a) = ∞ and t α 2 t (s, a) < ∞,for all (s, a) ∈ S × A.Proof. Applying Theorem A.2, we can demonstrate the convergence of the update rule in Eq. ( 15). Rewriting Eq. ( 15), we getEQUATIONSubtracting Q * (s t , a t ) from both sides yields:EQUATIONLet's defineEQUATION)This results in the same random process as shown in Theorem A.2 Eq. ( 14). Therefore, proving lim t→∞ Q t = Q * is equivalent to demonstrating that ∆ t (s, a) converges to zero with probability 1.We only need to verify that the assumptions in 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 α t (s, a) = 1/t, for instance.For the second assumption of Theorem A.2, we haveEQUATIONThus,EQUATIONwith γ < 1.For the third assumption of Theorem A.2, we obtainEQUATIONTo align with the RHS in the third assumption of Theorem A.2, we add and subtract a γ max a ′ :(s ′ ,a ′ )∈D Q * (s ′ , a ′ ) term:EQUATIONGiven that r is bounded, it follows that r + γ max a ′ :(s ′ ,a ′ )∈D Q * (s ′ , a ′ ) is also bounded. Moreover, the second part max a ′ :(s ′ ,a ′ )∈D Q t (s ′ , a ′ ) -max a ′ :(s ′ ,a ′ )∈D Q * (s ′ , a ′ ) can be bounded by ∥∆ t ∥ ∞ with some constant. Hence, we obtainEQUATIONfor some constant C > 0 under the supremum norm. Therefore, by Theorem A.2, ∆ t converges to zero with probability 1, implying that Q t 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 π * = arg max a Q * (s, a), π * 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.e. π * 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 {D i } are datasets collected from M with D 1 ⊂ D 2 ⊂ • • • ⊂ D n and corresponding empirical MDPs { M i }, then Q * 1 ≤ Q * 2 ≤ • • • ≤ Q * n .Proof. Consider two datasets D i ⊂ D j and their corresponding empirical MDPs M i , M j . Let B i and B j be the corresponding empirical Bellman operators. We have:EQUATIONWhere the transition probabilities P (s ′ |s, a) are the same for both B i and B j . Then, we can write:EQUATIONBy repeatedly applying the inequality, we getEQUATIONTaking the limit on both sides and considering that 0 < γ < 1, we obtainQ * i (s, a) -Q * j (s, a) ≤ 0, i.e., Q * i (s, a) ≤ Q * j (s, a).Then forD 1 ⊂ D 2 ⊂ • • • ⊂ D n and their corresponding empirical MDPs { M i }, we have Q * 1 ≤ Q * 2 ≤ • • • ≤ Q * n .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 two-dimensional coordinate axes x and y. In our experiments, we present it as a 4 × 12 × 3 binary array. The dimensions 4 x 12 correspond to the grid's shape, while the 3 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 in -1, and all other actions result in 0. We set the discount factor to 0.99 and the maximum episode steps to 100, as per [49] . The advantage of using a simple example like this is that we can pre-compute the optimal value and policy for a better understanding. Implementation Details. We train two DRL agents based on the Bellman update in Eq. ( 1) and the in-sample Bellman update in Eq. ( 2). We use a convolutional neural network that consists of a convolutional layer, followed by a fully connected layer. The convolutional layer has 16 3 × 3 convolutions with stride 1, the fully connected layer has 128 units. The optimizer for the network is Adam [65] with a learning rate of 1e-4. We fill the replay memory with different transitions to simulate various scenarios. Detailed results are given in Appendix C.1. Environment Details. The Arcade Learning Environment (ALE) [24] is a platform for evaluating the development of general, domain-independent AI technology. It provides an interface to a large number of Atari 2600 game environments with image input and discrete action space and with a 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 use the same network for each algorithm as in the original paper.We search the learning rates for baselines among {1e-3,3e-4,1e-4} and report the best performance.For our method, we fix the learning rate to 1e-4 and search our regularization parameters α ∈ {0.05,0.1,0.5}. We run each experiment with 5 different random seeds. Each run consists of 10 million steps of interaction on Atari games and 2 million steps of interaction on MuJoCo tasks. The performance is evaluated by running 30 episodes after every 100k environmental steps. We proportionally reduce other parameters based on the interaction steps. The ϵ-greedy exploration is linearly decayed from 1 to 0.01 in 1 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 is 0.99. Table 1 shows the details of hyper-parameters that used for all methods. Environment Details. MuJoCo [25] stands for Multi-Joint dynamics with Contact. It is a general purpose physics engine that aims to facilitate research and development in robotics. There are eleven Mujoco environments in total, and we choose eight of them in our experiments: Ant, HalfCheetah, Hopper, Humanoid, InvertedDoublePendulum, Reacher, Swimmer and Walker2d. All of these environments are stochastic in terms of their initial state, with a 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: a position of a body part or joint and its corresponding velocity. Often, some of 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 a 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 a tanh function before the final output, to control the action range at each dimension within [-1,1]. Our method is based on TD3, we maintain TD3's parameters the same as original paper [17] and search our particular parameter α ∈ {0.05,0.1,0.5}. Other common parameters are shown in Table 2 . We run each experiment with 5 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 SAC2 , TD3 3 and XQL 4 , 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 MuJoCo experiment takes about half a day. We provide an 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.(3) 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 state-action space, we can track which actions are taken and which are not at a 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 * , Q * . ∆(Q 1 , Q 2 ) denotes the average absolute error on state-action pairs in the replay memory between Q 1 and Q 2 :EQUATION)We run five random seeds, the solid line shows the mean value and the shaded area shows standard error. It is clear to find that ∆( Q, Q * ) converges to 0, while Q neither converges to Q * nor Q * . In particular, when we have Q * (s, a) = Q * (s,(Q, Q * ) (Q, Q * ) (Q, Q * ) (Q, Q * ) (Q, Q) 6WHSV H (VWLPDWLRQ(UURURQ3DLUVLQ0HPRU\ (Q, Q * ) (Q, Q * ) (Q, Q * ) (Q, Q * ) (Q, Q) 6WHSV H (VWLPDWLRQ(UURURQ3DLUVLQ0HPRU\ (Q, Q * ) (Q, Q * ) (Q, Q * ) (Q, Q * ) (Q, Q) 6WHSV H (VWLPDWLRQ(UURURQ3DLUVLQ0HPRU\ (Q, Q * ) (Q, Q * ) (Q, Q * ) (Q, Q * ) (Q, Q) 7KH&OLII *We present the performance improvement curves 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 run online that follows the learning rule Eq. ( 2) to learn Q. DQN and TD3 are agents that adhere to the learning rule Eq. ( 1) to learn Q. While Q online aims to solve the empirical MDP, it lacks the exploration that expands the MDP. DQN and TD3 have exploration mechanism such as ϵ-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 is an effective enhancement for current DRL methods, and both steps are crucial for performance.Next, we present the learning curves in comparison with other baselines in Figs. 15 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 as π. The policy π interacts with the environment and collect data into a replay memory, from which both π and π learn. As a result, both policies are learned with the identical dataset.Figs. 18 and 19 shows the evaluation performance of π and π. We find that π performs similarly or even better than π on 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 a 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 to 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 Q significantly reduces the estimation error in Q. Estimation bias has long been a problem in value-based methods due to the combination of deep neural networks with the maximization operator in the Bellman optimality equation [20, 21] .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 Q True by running the current policy for 30 episodes and computing the actual discounted cumulative rewards at each state-action pair:Q True (s t , a t ) = T t=t γ t r t .We then compute the averaged estimation difference between the learned Q and ground truthQ True , V diff (Q, Q True ) = 1 |(s,a)| (s,a)∈T (Q(s, a) -Q True (s, a)), where T is the set of evaluation trajectories, |T | denotes the total number of state-action pairs in T . We compute V diff for our method and compare it with DQN and TD3.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 is quite close to the true value and there is no serious overestimation or underestimation. Figure 21 : Estimation error on Mujoco environments. We compute the average difference between the estimated Q value and the ground truth value during learning.Policy churn 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 π ′ is defined as:EQUATIONwhere 0 ≤ W (π, π ′ |s) ≤ 1. When π and π ′ are greedy policies derived from action-value functions, W (π, π ′ |s) = 1 if π and π ′ choose different actions, otherwise W (π, π ′ |s) = 0. Thus it is simply a count of different actions after one step update. In agents that use a target network which is an older copy of the online network, it is easy to measure W (π, π ′ |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 t, we sample a batch of data D and compute the average policy change W t (π t-1 , π t ) =1 |D| s∈D W (π t-1 , π t |s),where |D| is the size of the batch data. Then we compute the average policy change over the whole learning process as W = 1 |T | t∈T W t , 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 as it can also be a potentially beneficial form of implicit exploration. However, the frequency of change that benefits learning is still unclear and deserves further study.( Our method comprises two parts, the regularization term determined by parameter α, and the exploration term designed based on δ(s, a). Figs. 23 Justification: The abstract and introduction accurately reflect the paper's contributions to 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 in 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 as long as it is clear that these goals are not attained by the paper.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to 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, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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 are accompanied by error bars, confidence 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).• 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. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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, or scraped datasets)?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 a 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 a 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
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/model 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. 
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 as 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 crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
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 nor 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 NeurIPS 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.Unlike Fig.1athat measures the error of Q, here we measure the estimation error of Q after regularization.https://github.com/haarnoja/sachttps://github.com/sfujim/TD3https://github.com/Div99/XQL 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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:
* 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
* 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

Overall, I like the paper and think it should be published.
strength_weakness: strength_weakness: * 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.
* 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
* 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?
* 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.
questions: questions: Why integrate into TD3 instead of SAC when as far as I know SAC seems to outperform TD3?
limitations: 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.
paper_summary: paper_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.

The 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.
strength_weakness: strength_weakness: **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.

I 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.

**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.

**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.
questions: questions: 1. How does EMIT fundamentally differentiate itself from existing methods like Implicit Q-Learning and In-Sample Actor-Critic?
2. What are the limitations of the current exploration mechanism used in EMIT, and how does it compare to other advanced exploration strategies?
3. Can EMIT be effectively applied to real-world reinforcement learning problems, and what are the potential challenges in such applications?

I am willing to discuss and update my score until all the concerns are addressed.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: Reproducibility: The code was not provided in the supplemental material. 
Representation: The text in Figure 2(a) is very small and unreadable.
questions: questions: Can you plot $\Delta (Q, \hat Q) $ to see how far is Q from the empirical $\hat Q$?

In 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: limitations: Added computational complexity from learning two Q-functions
paper_summary: paper_summary: When using the Bellman update with incomplete data, the estimation error is hard to eliminate.
To 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.
strength_weakness: strength_weakness: 1. The running time of the different RL methods should be compared.
2. The proposed method should be compared with recent RL methods, such as TD7 and CrossQ [1, 2].
3. A head-to-head comparison between your memory buffer and the existing ones should be given [3].
4. From Algorithm 1, it is hard to see the difference between the proposed method and the existing ones.


If the authors can present their contributions clearly and open-source the code, I will  increase my rating.

[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.

[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.

[3] Schaul T, Quan J, Antonoglou I, et al. Prioritized experience replay[J]. arXiv preprint arXiv:1511.05952, 2015.
questions: questions: 1. Can EMIT improve the performances of the recently proposed RL methods?
2. 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?
limitations: limitations: N/A

Comments: title: Follow-Up on Rebuttal and Feedback
comment: Thank you for your response.
Thank you for taking the time to review our responses and for increasing your score. We greatly appreciate your feedback and support.
I thank the authors for their detailed responses. I've increased my score.
Dear Reviewer,

As you mentioned 'I am willing to discuss and update my score until all the concerns are addressed', we kindly ask if our responses have addressed your concerns. We appreciate your feedback and are happy to provide further clarification if needed.

Many thanks,
The Authors
Thanks for your rebuttal and I will maintain my score!