Belief Projection-Based Reinforcement Learning for Environments with Delayed Feedback
Authors: Jangwon Kim
Hangyeol Kim
Jiwook Kang
Jongchan Baek
Soohee Han
Venue: NeurIPS 2023 poster (2023)
Keywords: time-delay system
reinforcement learning

Abstract: We present a novel actor-critic algorithm for an environment with delayed feedback, which addresses the state-space explosion problem of conventional approaches. Conventional approaches use an augmented state constructed from the last observed state and actions executed since visiting the last observed state. Using the augmented state space, the correct Markov decision process for delayed environments can be constructed; however, this causes the state space to explode as the number of delayed timesteps increases, leading to slow convergence. Our proposed algorithm, called Belief-Projection-Based Q-learning (BPQL), addresses the state-space explosion problem by evaluating the values of the critic for which the input state size is equal to the original state-space size rather than that of the augmented one. We compare BPQL to traditional approaches in continuous control tasks and demonstrate that it significantly outperforms other algorithms in terms of asymptotic performance and sample efficiency. We also show that BPQL solves long-delayed environments, which conventional approaches are unable to do.

Belief Projection-Based Reinforcement Learning for Environments with Delayed Feedback
Jangwon Kim
Hangyeol Kim
Jiwook Kang² jiwook. kang koreaaero.com
jangwonkim @ postech.ac.kr
hangyeol. kim @ koreaaero.com
Jongehan Back² joback @ttri.re.kr
Soohee Han soohec.han @ postech.ac.kr
Abstract
We present novel actor-critic algorithm for an environment with delayed feedback, which addresses the state-space explosion problem of conventional approaches. Conventional approaches use augmented state constructed from the last ob- served state and actions executed since visiting the last observed state Using the augmented state space, the correct Markov decision process for delayed environ- ments can be constructed; however, this causes the state space to explode as the number of delayed timesteps increases, leading to slow convergence. Our pro- posed algorithm, called Delief-Projection-Bae the state- state-space explosion problem by evaluating the values of the critic for which the input state size is equal to the original state-space size rather than that of the augmented one. We compare BPQL to traditional approaches in continuous control tasks and demonstrate that it significantly outperforms other algorithms in terms asymptotic performance and sample efficiency. We also show that BPQL solves long-delayed environments, which conventional approaches are unable to do.
Q-learning (BPQL), addresses
Introduction
Deep reinforcement learning (RL) methods have been successfully applied to diverse domains, such as decision-makee tasks and robotic control problems 2 The deep RI. framework has shown its potential by mastering the highly complex board game Go and defeating the professional Go player Lee [30] It has also demonstrated superhuman performance, even in games where perfect model not provided, such as Atari video games (24). Furthermore, modern deep RL algorithms have achieved significant performance improvements in continuous control domains, such as robotic locomotion 28 29 14]. Recently, many attempts have been made to apply RL-based control in not only simulations but also the real-world domain [13 [6 22 26). Remarkable examples include applying the RL method to a quadrupedal robot to learn walking gaits and plan the motion of robotic manipulation in the real world [7].
Despite recent progress in RL methods, adapting RL. algorithms to the real world remains challenging for many reasons. Delayed feedback from the environment is particular challenge. For example, latency may occur when the controller attempts to communicate with an agent if the agent located far from the controller or if a large quantity of data, such as high-resolution images, must be transmitted. Furthermore, hardware issues can cause sensing or actuator delays. This delayed feedback may hinder achieving the control objectives.
'Computational Control Engineering Lab., Pohang University Science Technology. Korea Aerospace Industries, Ltd. Electronics and Telecommunications. Research Institute.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Therefore, controlling signal delay is essential for applying RL algorithms to real-world domains. In this study, we propose novel approach called belief projection- based Q-learning (BPQL) to overcome a constant delayed environment in which feedback is delayed by fixed timesteps. BPQL. addresses the state-space explosion problem, which commonly oceurs in conventional approaches, and achieves better performance than conventional approaches in terms of asymptotic performance and sample efficiency.
Related Work
2.1 Standard Reinforcement Learning
Markov decision process (MDP) is defined as a 5-tuple AA, P. 7),,
where X is the state space,
A is the action space, R. X x A IR is the reward function. P X x A x X + [0, 1] is the transition kernel, and ς E (0, 1) is a discount factor. The policy <-|ss) maps the state-to-action distribution. In the standard RL framework, the agent chooses an action maximize the discounted cumulative rewards by interacting with an environment defined as an MDP.
Let the distribution of the initial state be Po. Then, the expected discounted cumulative reward from policy æ is given as:
<TT) = E
y R(ss a)),
where initial state 80 ~ Po. a ~ T( (+)s;), and 8t+1 ~ P(-ls;,a,)
From the standard definitions, the value and Q-value functions are obtained as:
(T((s) E
(((S++,)4+**)+
(2)
k=
Q" 04) = E
R(s++R
(3)
k=
where vk 2 0, 0 ((185+4) and 81+4+1 P(ylstt, 0c+k)-
Both value functions satisfy the Bellman equation (3:
v (st) = Barw)()le)) [R(s,, ar) + + (V(44)))]] (s+++))]
(4)
()), = R(st, ax) +
(5)
In the standard RL framework, we assume that the reward and next state only depend the immediately previous state and action based on the Markov assumption. However, in an environment where the observation is delayed, the next state does not depend on the immediately previous state but on an older state and action history. This delay property forces the environment to be a partially observable MDP, not an MDP.
In this study, we consider the observation-delayed environment but not the action-delayed environ- ment. However, observation and action delays intrinsically linked [ 34], which allows to control the action-delay problem in the same manner as the observation-delay problem.
2.2 Constant Observation- -Delayed Environment
In delayed feedback environment, the agent receives time-delayed feedback from the environment, which makes difficult to choose a timely and correct action at each timestep. conventional control theory, signal delay is often handled by augmenting the state combination of the last observed state and history of actions for the delayed timesteps (20 25).
This augmented state can also be used in RL frameworks. Considering a constant delayed feedback system, an environment with delayed feedback can formalized by a constant delayed MDP (CDMDP) (34) The CDMDP is defined as a 6-tuple (X R, P, d). where d is the number of timesteps between the execution of an action and receipt of feedback from that action (i.e., delayed timesteps).

---

Delayed feedback
(2) Se+1-di Tt-d
Delayed Environment
Agent
Figure 1: In a constant delayed environment, the agent receives delayed state st+1-d and reward d after executing action dg. These values are the actual feedback from previous action a;-d and state st-d, where is the number of delayed timesteps.
The CDMDP known to be reducible to an MDP (S, (7,.), where = X' A is an augmented state space, R S x A + R is the reward mapping, and P S x S [0, is the transition kernel 18 34). This makes it possible to treat the CDMDP as a regular MDP. From this perspective. some model-free approaches, referred to augmented state approackes, have been proposed [4] 34] 27 []. These use the augmented state, which is constructed by concatenating the last observed state and previous actions since visiting the observed state. However, the augmented state space grows exponentially as the number of delayed timesteps d increases. The curse of dimensionality makes the augmented state approach tractable for environments with only relatively
short delay.
Model-based approaches have also been proposed for handling delayed environments 34 In these approaches, the agent predicts the current state by simulating the environment model and selects action based on the predicted state. Increasing the accuracy of the transition model is key to this approach. However, in a complex, stochastic environment with long time delay, the rapid growth of model error increases the difficulty of training the agent.
To the best of our knowledge, the closest work to ours the study [ that proposes a model-based algorithm expectation maximization Q-learning (EMQL). This algorithm, however, can only be used discrete states and action spaces, whereas our proposed algorithm can be used in continuous state-action spaces without constraints. Additionally, although EMQL can suffer from dynamic model errors, our algorithm avoids this because is a completely model-free approach.
As aforementioned, delayed environments have been mainly handled with two methods: the complete information method (e.g., the augmented state method) and the state estimation methods (e.g., the model-basee method). As inherent drawbacks, the first one suffers from the curse of dimensionality and the second requires accurate model-based state estimation. Therefore, the research objective of this work is to resolve these two drawbacks together, i.e., find a model-free approach that is basically free of dimensionality curses. This is why the proposed algorithm was born.
3 Dynamics in Augmented State Space
In this section, we analyze the augmented state approach for the constant delayed environment. Figure Iillustrates the interaction between an agent and delayed environment. At each time i, the agent executes action a and receives the delayed state 8t+1-d and reward rt-d- where d is the number of delayed timesteps. These feedback values are the response from action a--d. This misalignment of state, action, and reward makes difficult find an optimal policy.
3.1 Notation
We have observed that the CDMDP can be treated as a regular MDP by replacing the state space in the CDMDP with the augmented state space. The augmented state is constructed by concatenating the last observed state and previous actions and is denoted by 3.
More formally, in environment delayed by d timesteps, the augmented state is constructed by concatenating the last observed state and previous actions:
(St-dy dg Oc-d+1," 14-1))-
(6)
3

---

The policy that receives the augmented state as input is called the augmented state state-based policy, denoted #(-13). (5) the agent's -aggddeee state distribution for augmented state-based policy т. Furthermore, we refer to the value of the augmented state as the augmented state-hased value, denoted as V* (s+). Similarly, the Q-value of the augmented state is called the augmented state-based Q-value, denoted as (a,, az).
3.2 Augmented State Approach
Our objective is train the agent in constant delayed environment. In the augmented state approach, new augmented state is constructed by augmenting the last observed state and previous actions to treat the CDMDP as regular MDP.
We can apply modified Bellman operator called the delay Bellman operator T to determine the augmented state-based value-function. The operator T is given as:
(3,(3;) + (ai
(x.)) [R[se,, az)] + - P(( [V [5(+1)]] vt >> d,
(7)
where denotes the number of delayed timesteps in the environment. The expected reward is used in the delay Bellman operator because we assume that all feedback is delayed in a constant delayed environment, including the reward, which implies that the exact reward R[ 0z) cannot be determined at time t.
The augmented based values be computed by repeatedly applying the delay Bellman operator. After computing the augmented state- state-based values, the policy is updated to increase these values for all augmented states in the policy-improvemmet stage.
Although the augmented state-based values can be computed using the delay Bellman operator, the state-space explosion issue follows; the augmented state space grows exponentially the number of delayed timesteps increases because the augmented state space in the reduced MDP a Cartesian product of the original state space and d action space (i.e., S X' x A This indicates that the larger the state space, the larger the set of samples required to compute the value of the entire set of states. This makes the augmented state approach impractical for long-delayed environment.
3.3 Alternative Method to Represent the Augmented State-Based Value
Because calculating the value of the augmented state space by applying the delay Bellman operator suffers from the state-space explosion issue, we propose an alternative method for representing the augmented value.
The distribution of the probability of visiting the true current state St (which has not yet been observed) depends the augmented state &, If two successive transition probabilities (s).(()) and ((), are similar, we can assume that the augmented states 8 and of have similar representative meanings. Based on this assumption, we define the belief projection of the augmented values as follows.
Definition 3.1. For a policy म., state space X' = {61, 82, ,8, and augmented state space S
{81, ... {8))
let B, V and D be:
(Ps [11
P(s2(51)
P(s: 51
(51)
P(s 82)
3282)32)
P(s 82)
B
V
D = diag (W,
(*(3,)
1())
P(52(3,)
P,))),))
where W = 10a (31), p² "e.,,".,"""
p² (3,)) is atgaenea state probability vector when the agent follows the policy म. Then, the projected values V projj are defined as:
prog. TT,
where the projection operator II, is BBB -BB
We refer to matrix B as the belief matrix. the matrix B operator can be replaced with the Moore-Penross pseudoinverse operator. We refer to the outcome
T DB is not invertible, then the inverse

---

from the projection operator Iw as the belief projection. The belief projection operator Iww projects vector in R' onto the column space of the belief matrix B with respect to the weighted Euclidean
norm || l|w-
Because the belief projection lies in the column space of the belief matrix, we can the vector V to decompose the projected values as follows:
(s1)
proj.
BV =B
(9)
(8:)
We refer to the elements of V/8 as the beta values. The vector V,3 can also be defined as:
arg min
BV
V1l2.w-
(10)
VER
From Equation ② the augmented state-based value can be decomposed into the sum of the expecta- tion of the beta values over the original states and the residual:
V (8e) (p().(a.) (sx)] + A (8+),
(11)
where t > d. Similarly, we can extend Equation ( to the belief projection for the augmented Q-values (projected Q-values); the beta Q-values for given action satisfy the following:
@" (5t, = EpcsIsa (0, a)] + Tesiduut a)
(12)
3.4 Linear Function Approximation
The augmented state approach is impractical for long-delayed environment because its state-space size grows exponentially as the number delayed timesteps increases. In long-delayed environment, this indicates that directly calculating the augmented state-based Q-values by applying the delay Bellman operator requires a significantly large set of samples.
To avoid this issue, instead of calculating the augmented state-based values V directly, we estimate the belief projection IIw V. Let 7 be matrix form of the delay Bellman operator 7 i..., T = R >PV, where R (a),,,, [ a)).... (8))(s)))..)at(((( [ a)]] is vector consisting of expected rewards and P is the transition matrix. In this setting, focusing on finding a solution V = arg minyeR: [BV II (BV)Ilw could be achieved very efficiently, especially
[R(s,
when [S] >>>>>>>>>>> |
Note that the values are approximated as linear combinations of the belief matrix and the beta-values. In other words, the belief projection can be seen as a linear function approximator where the feature vector for an augmented state & E S is [P(s) [x), ((2 (x))))).
(5,) 55)) and the corresponding parameters are the beta values [V] (s1), V (s2),-. V (s:)) In that sense, we can guarantee the
contraction of the combined operator Tl 7thh by using the well-known contraction property of linear function approximation 32 5
Proposition 3.2. Let the projection operator onto the column-space of the belief matrix B with respect to the weighted Fuclidean norm] || ||w be Tw, where W == [p= (81), (82), ...., p² (x) is steady-augmente state probability vector, and the Markov chain be irreducible i,e, p² (3x) > f
all ...,.. J.. Then the combined operator Iw? c-cottraction with respect l|w.
Proof. See appendix B
This contraction property of ll guarantees find a fixed unique solution (V (s1),... V (s:) by repeatedly applying the combined operator Tw This Vi be used as an estimator for the true beta values V,, providing a direction for policy update. For example, new policy Fnew can be obtained by greedily choosing an action, i.c., Fnew (3,) =
arg max,, E. (Ep(e.)s,) [R(s,, at)) (BP(E41155 EP(s. (araa is the policy before improved.
[V (st+1)])):
where the R.
5

---

Actor-Critic Algorithm for Constant Delayed Environment
In the previous section, we presented an iterative method that computes the value function in the smaller state space created by belief projection, rather than in the larger augmented state space. However, despite the favorable convergence property of value function approximation through belief projection, explicitly calculating the belief matrix can be challenging, especially in cases where the augmented space is large continuous. To address this challenge, we introduce practical sampling-bass reinforcement learning algorithm based on the theoretical insights from the previous section. In this algorithm, the agent learns the beta values without the explicit computation of the belief matrix.
First, we define the delay soft Bellman operator T which is the soft Bellman operator for the delayed environment setting:
To 2 (ft, 0t) + (p( (R(s,, + F (Fe+1, - a log t (ar+1 [++1)]
(13)
where a is the temperature parameter. We can compute the augmented state-based soft Q-values by repeatedly applying the delay soft Bellman operator.
In the policy improvement stage, the policy is updated towards the exponential of the evaluated augmented state-based soft Q-function. The improved policy new can be obtained as [1]
(+(-13)) exp TTa (3c,
new arg min DKL
(14)
2
where (sE) is a normalizing function. This updated policy neww guarantees Q (St. 0e) 2 QTay (3,, a,) for all (3,, a.) E S x A.
The beta Q-values approximately computed by minimizing the average of weighted squared residual error i.e, 6 Residual in Equation [2) as:
Jq. Es a 1e a:)] - x= az))
(15)
Let the augmented Q-value be a soft Q-value; then, substituting ("1(s,, a.) into with the target value in (13). Equation (15) can be expanded the following equation:
Jo. = E (Q) (z) - R(st, az)l - yEg, ( (8= 0c+1)
a log न (ac+1 [=++1)]
(16)
Subsequently, we replace the augmented state- based soft Q-value with the expectation of beta Q-values:
@* (B 1) Ep( [ (8241,
(17)
by fitting the augmented Q-value the belief projection. Then, the objective can be rewritten as:
JQ. = (3,
Ex (x) (QT ad) - R(s(, qz)
(18)
71B P. 190 (54)) log & (ar+1 (5++))]
Now, our objective has changed to finding the beta Q-values, where their expectation best represents the augmented state-based Q-values. We can also rewrite Equation [14) using the belief projection

---

instead of using the augmented Q- Q-vauues:
(1 exp( _ Co se) 1Q sou (sts -]))
T new
arg min DRL
(19)
R
(5c)
1 ( 1q (st, a+)] + log 2=00 (8+)
arg min
Σ areA
[log (unl(5))
(20)
α
arg min
log ((rl()))) # (1
a (e 19 at)] + R (e))) Dlog n0th
1
(st))
RICA
(21)
1 2 (s;: ar) + log 2tth (81))
arg min Ep(as(a.)
(aaaa (a:l5t)
(22)
ateA
exp( 1 (SL. n (5t)
arg min (5())(5))
DKL
(23)
where zan (8t) is normalizing function for the distribution Qaat Equation log 2 Ram (3t) and Ex(e:ls:) llog [**) are independent of Æ'.
21 holds because
Using Equation (23). we can update the policy by minimizing the expectation of the Kullback Leibler- diibler-iverrence of the policy and exponential of the beta Q-value. Notably, need not evaluate the augmented delayed timestep is large. By contrast, we evaluate the beta Q-values and improve the policy using these values.
soft Q-value, which causes the state-space explosion problem when the
The beta Q-value is expected to converge more stably and quicker than the augmented state-based Q-value because its input state space is considerably smaller than the augmented space, which also helps to obtain an improved policy with higher quality.
In the continuous state setting, the parameterized beta Q-function Q7 at) can be approximately computed by minimizing the squared-residual in Equation (18) denoted by JQa (0) with the aid of replay memory 'D (24]:
JQs (0) =I Sn J-Dly (2 (0 ar) (re + +E (Q01 G(+1)
(24)
a log i (a ((441))1
where T, R(st, az). Qui target network for Q7, 124] and मe is parameterized policy.
In the policy improvement stage, the policy can be trained by minimizing the objective (=))), which can be formalized from Equation (23 as:
(+ E Bainss la log (a(())))) (s),(()))))]
(25)
By iteratively minimizing Jq. (0) and (Ø), the actor and critic networks can be trained for delayed environment. This is the BPQL algorithm. Note that the first and second subscripts of Qo.s refer to the neural network weights and the beta Q-values, respectively. Actually, the beta Q-values depend on the neural network weights. Nevertheless, 0 and 8 are written together for clearer notation. Only is the variable set to be optimally taken through learning.
In the BPQL algorithm, expanded transition tuples that include augmented states are stored in the replay memory D. To construct the augmented state, use temporary buffer B in which the original states and action history are stored. The details of BPQL are summarized in Appendix A.
5 Experiments
We compared the performance of the BPQL algorithm with the following three baselines
Further details of the implementation of these algorithms given in Appendix D.
7

---

Walker 26-03
Nomea CelpaddAC Axcrrttl SOC
Figure 2: Performance curves of each algorithm for the Walker2d-v3 task. We repeated the test for this task five times with different random seeds. The mean the results is shown by the solid line, and the shaded area represents the standard deviation. As the delay increases, the proposed algorithm BPQL significantly outperforms other algorithms in terms of asymptotic performance and sample efficiency.
Table 1: Results of MuJoCo benchmark tasks for one million interactions. Each task was evaluated in the delayed environment setting for 3,6, and delayed timesteps d. All tests were repeated with five different random seeds. All results are shown with the standard deviation over the five trials denoted by =
Environment
HaliChestah-v3
Walker2d-v3
Hopper-v3
Swimmer-v3
InvertedPenddlum-22
Reacher-v2
Algoritlon
Normal SAC
-276.2
672 251.8
290.9
32 8ga7
16.9
28. 2.00
Delayed-SAC
1182.7
2521.7 72800.1
73.9-32.
916.5 916.5g112.
-3.95
Augmented SAC
1054.0
3453.3
2732. 63858.9
6a2.1
983 6:32.
g3.95
BPQL (ours)
8100.1
4538.5
2922.5
88.0
998.1
-3.8
Normal SAC
-288.7280.7
38.6
68.3
32.1
10.1g2.9
-38.2
Delayed-SAC
2060.9
1.0g40
1289 1289.2g107i.
58.2_146
929.1gmm.
-4.02g030
Augmented SAC
2012.6
3023. 14ss0.2
2100.0
43. 13a.
1000.0
-1.00
BPQL (ours)
6334.622453
4551.9 1571,
3336.0_
93.0 m1.
983. 983.4gam.
.3.81 10.51
Normal SAC
39.
26.448.8
69.0
26.323.
16.1g5.9
-37.3643.42
Delayed-SAC
1764.31993
2.6go.4
313.72w42.
77.6
505.8gama
-4.01g0.51
Augmented SAC
1297.2
1502.9
L497.8
38.3240
1000.0.an
-4.39g0.5
BPQL (ours)
5887.55
4104.3
2993,4_9667
93.5
985.6228.6
-3.86
Augmented approach: Augmented SAC
Model-based approach: Delayed-SAC
Normal SAC
In the augmented approach, we solve the control problem by adopting an augmented state space, which facilitates treating the CDMDP regular MDP. This is popular and widely used method for an agent learning in a delayed environment [34] [27]. The policy and critic in the augmented state approach are trained by minimizing the objectives (Q( and Jx()):
Jo( F (Q7 (3), a.) (r+ yaa ~ 12 (8441,
(26)
a log R 18- 1))
Ja (Ø) (. Ba (ar log n (a, (Fe, ac))-
(27)
We named this augmented-baree based approach Augmented SAC.
In the model-based approach, we use the delayed-Q algorithm 10 which uses a forward model to estimate the timely proper state. In this approach, the agent takes an action based on the pre- dicted current state from the dynamic model using the last observed state and action history, i.e.,
(st-d, ag-d, Oc-d+1,' a.))). The model repeats the one-step transition prediction d times to

---

sager
Figure 3: (a) Result of tests noisy version of InvertedPendullum-2.. The noises added to the actuator are drawn from a normal distribution with a mean of zero and standard deviations of 0.1 ((a)-left) and 0.15 ((a)-right), respectively. The range of action for the actuator is [- 3, 3]. (b) The performance curves of BPQL and Augmented SAC with different hidden sizes (256,, 256), (512, 512), (1024, 1024), (256, 256, 256)) of Q-network.
predict the current state. In the learning stage, we train the critic and policy using true transition tuples, i.e., (st, de, ft, 8t-1). The original study used double deep Q-networks (DDQN) (33 the base learning algorithm. However, because DDQN is only applicable to discrete action spaces, we have used SAC for base learning algorithm, so named this model-based approach Delayed-SAC.
Lastly, in the Normal SAC approach, the agent naively uses delayed feedback for training without any modification.
5.1 Performance Comparison
We tested the algorithms on several tasks using the MuJoCo benchmark 31 and evaluated their performances in environments with different numbers of delayed timesteps Figure 2 shows that the augmented and model-based approaches are inappropriate for environments in which the delayed timestep is large, whereas the proposed BPQL algorithm exhibits significantly better performance in a long-delayed environment. Table lists the overall experimental results, confirming that BPQL outperforms the conventional approaches by wide margin in environments ranging from short (d=3) to long delay (d=9).
5.2 Stochastic Environment
We evaluated BPQL and other baselines the noisy version of the InvertedPendulum- -v2 environment, where Gaussian noises were added to the actuator such that the acting becomes stochastic for the same input for the actuator. The added noises the actuator are sampled from normal distribution with zero mean and standard deviations of 0.1 and 0.15. In this stochastic environment, BQPL has also shown better performance than conventional algorithms, and the difference gap in performance increased as the level of stochasticity grew.
5.3 Performance comparison of augmented approach with various capacity of Q-nttwork
We conducted additional ablation study investigate whether the size of Q-network was small to learn and extract important features from the augmented state. We tested the performance of Augmented SAC with different hidden size of the Q-network, including (256,256), (512,512), (1024, 1024), and (256,256,250) The results of this additional experiment show that the size of the Q-network does not significantly affect the performance of the augmented SAC as shown in Figure 3-(b). This confirms that addressing the state space explosion problem is crucial factor in training the agent in a delayed environment.
Conclusion
In this study, we proposed novel model-free algorithm BPQL. for constant delayed environment. BPQL evaluates the beta Q Q-function based on the original state-space size rather than evaluating the
Seee Appendix C for the details of these environments.

---

augmented Q- Q-function, which helps the parameterized Q-function learn more stably and converge faster. In regards the MuJoCo benchmark for continuous control tasks, BPQL achieves significantly better performance than the augmented state approach, which is popular and widely used algorithm for delayed environments. Our results show that BPQL. provides promising avenue for handling delayed environments, such as real-world robot control environments where sensing and actuator delay exist, or a communication system with a narrow bandwidth.
As BPQL cannot be applied to a random delayed environment, it would be meaningful to extend our work to an environment with randomly delayed feedback. Ensemble learning of the beta Q-functions and augmented state-based policies that cover the entire delay range could be one possible approach. Furthermore, real-world applications using the proposed algorithm an exciting direction for future work.
Acknowledgement
This work was supported by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No.2019-0-01966, Artificial Intelligence Graduate School Program (POSTECH)
References
[1] Mridul Agarwal and Vaneet Aggarwal. Blind decision making: Reinforcement learning with delayed observations. Pattern Recognition Letters, 170:176-182, 2021. doi: 10.1016/j.patres 2021.06.022.
[2] Kai Arulkumaran, Mare Peter Deisenroth, Miles Brundage, and Anil Anthony Bharath. Deep reinforcement learning: A brief survey. IEEE Signal Processing Magazine, 34(6):26-38 -6, 2017. doi: 10.1 109/17701111...74422......
[3] Richard Bellman. A markovian decision process. Journal of mathematics and mechanics, pages 679-684, 1957.
[4] Dimitri P Bertsekas. Dynamic Programming and Optimal Control, 2nd Edn, Vols. I and 2.
Athena Scientific, Belmont, MA, 2001.
[5] Dimitri Bertsekas. Approximate policy iteration: A survey and some new methods. Journal of Control Theory and Applications, 9(3):310-333 11110033,1100 2011.
[6] Yann Bouteiller, Simon Ramstedt, Giovanni Beltrame, Christopher Pal, and Jonathan Binas. Re- inforcement learning with random delays. In Proceedings of the Ninth International Conference on Learning Representations, Online, 2021.
[7] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint 1606.06600.0// 2016.
[8] Baiming Chen, Mengdi Xu, Liang Li, and Ding Zhao. Delay-aware model- based reinforcement learning for continuous control. Neurocomputing, 450:119-128, 2021. doi: 10. 10.10166/..nucoo 2021.04.015.
[9] Petros Christodoulou. Soft actor-critic for discrete action settings. 19110:1910 2019.
arXiv preprint
[10] Esther Derman, Gal Dalal, and Shie Mannor. Acting in delayed environments with non- stationary Markov policies. arXiv preprint arXiv:2 1992, 2021.
[11] Vlad Firoiu, Tina Ju, and Josh Tenenbaum. At human speed: Deep reinforcement learning with action delay. arXiv preprint arXiv:181000726.. 2018.
[12] Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Proceedings of the 35th International Conference on Machine Learning, pages 1587-1596, Stockholm, Sweden, 2018. PMLR
10

---

[13] Shixiang Gu, Ethan Holly, Timothy Lillicrap, and Sergey Levine. Deep reinforcement learning for robotic manipulation with asynchronous off- ooflpp updates. In Proceedings of the 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 13399-3996 Singapore, Singapore, 2017. IEEE. doi: N..119//CRA.2001.79895555
[14] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abheel, and Sergey Levine. Soft actor-critic algorithms and applications. arXiv preprint arXiv: 2018.
[15] Todd Hester and Peter Stone. TEXPLORE: real-time sample-efficient reinfoocmmmnrninnooeeeeeem learning for robots. Machine learning, 90(3):385 429, 2013, doi: 10.100771119994412--22....
[16] Jemin Hwangbo, Inkyu Sa, Roland Siegwart, and Marco Hutter. Control of quadrotor with reinforcement learning. IEEE Robotics and Automation Letters, 2(4):2096-2103,, 2017. doi: 10.1109/LRA
[17] Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, and Sergey Levine. Scalable deep reinforcement learning for vision-based robotic manipulation. In Proceedings of the 2nd Conference on Robot Learning, pages 651-673, PMLR, 2018.
[18) Konstantinos V Katsikopoulos and Sascha E Engelbrecht. Markov decision processes with delays and asynchronous cost collection. IEEE Transactions on Automatic Control, 48(4): 568-5744 2003, doi: 10.1009/AAC.2003.899999
[19] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.6980, 2014.
[20] Woosuk Kwon and A Pearson. Feedback stabilization of linear systems with delayed control. IEEE Transactions on Automatic Control, 25(2):266-269, 1980. doi: 10.1 1990.......0 1 1102288.
[21] 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
2015.
[22] Jan Matas, Stephen James, and Andrew Davison. Sim-to-real reinforcement learning for deformable object manipulation. In Proceedings of the 2nd Conference on Robot Learning. pages 734-743, ürich, Switzerland, 2018. PMLR.
[23] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
[24] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, Stig Peter- son, 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-555 533, 2015. doi: 10. 10.1038/nature 1 14236.
[25] Jung Hun Park, Han Woong Yoo, Soohee Han, and Wook Hyun Kwon. Receding horizon controls for input-delayed systems. IEEE Transactions on Automatic Control, 1367):1746-1752, 2008. doi: 10. 10.1109//AC.2200822282000
[26] Xue Bin Peng, Pieter Abbeel, Sergey Levine, and Michiel de Panne. DeepMimic: Example- guided deep reinforcement learning of physics-based character skills. ACM Transactions On Graphics, 37(4):1 2018. doi: 10.1145/3175517.22113
[27] Simon Ramstedt and Christopher Pal. Real-time reinforcement learning. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages 3073-3082, Vancouver, Canada, 2019.

---

[28] John Schulman, Sergey Levine, Philipp Moritz, Michael Jordan, and Pieter Abbeel. Trust region policy optimization. In Proceedings of the 32nd Iternational Conference on Machine Learning. pages 1889-1897, Lille, France, 2015. JMLR.
[29] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1007.06377, 2017.
[30] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy 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-39)
2017. doi: 10. 1038/naturre22270.
[31] Emanuel Todorov, Tom Erez, and Yuval Tassa. MuloCo: A physics engine for model-based control. In 2012 JEEE/RSJ International Conference Intelligent Robots and Systems, pages 0026-5033, Allmoura-Algarwe Portugal, 2012. IEEE. doi: 10.1 20116.666.......86100
[32] John N Tsitsiklis and Benjamin Van Roy. Analysis of temporal-diffferenee learning with function approximation. Advances in Neural Information Processing Systems, 9:1075-1081, 1996.
[33] Hado Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double Q-learning. In Proceedings of the AAAI conference on Artificial intelligence, volume 30(1), pages 1094-2100, Phoenix, AZ, 2016.
[34] Thomas Walsh, Ali Nouri, Lihong Li, and Michael L Littman. Learning and planning in environments with delayed feedback. Autonomous Agents and Multi-Agent Systems, 18(1): 83-105, 2009. doi: 104500000008008--00000
12

---

A Architecture and Pseudo Code of BPQL
L St-d Re-e- Prei-
@ Reaandi Rond
Temporary Buffer
Replay Memory
Delayed Eav
Minimize Jg and J=
AgentPallicy
(
Figure 4: BPQL architecture: The agent selects action using augmented state, which is obtained from the temporary buffer, as an input of the policy. At every time t > 2d, transition tuple dt-d: de at-d; Tt-d 1 S-+1-d is stored in the replay memory, and the policy and beta critic are trained by minimizing J and JQp. respectively.
Algorithm 1 -Belicf-Projcctonn
Q-learning (BPQL)
1: initialize a policy 7& (a(5), beta critics (s, a), target beta critics Q (s, a), an empty replay memory D, a temporary buffer B, delayed timesteps d, learning rate for the beta critic Aga learning rate for the policy X and soft update ratio
2: for episode
to do 3: fort = 1 to H do
4: if then
5: executes action d, randomly 'No-Op' action
6: put a, to B
7:
else if d then
8:
choose action randomly or 'No-Op' action
9:
81 Env
10:
put 81 and aa to B
11:
else
12:
get st-d; at-d. Q1-1 from B
ar-di ...... a1-1) ar + (3t)
8t (s--d, (s
14:
8t+1-d; rt-d Env (at)
16:
put 8t41-d and to B
if 2d then
18:
get 8t-2d 2d-2 8t ..
., ar-d from B
19:
8t-d f- (8t-2ds 2d, at-2d; 0t-d-1)
20:
8t-4+1 (8t- 114 - (t-d)
store (8t-d; 8t-ds ai-d; Ti-ds 8141-d; 8:41-d) in
22:
end pop St-2d; Ot-2d from B
23:
24:
end if
25:
end for
26:
for each gradient step do
27:
w t w Aq, V VoJa, (w)
28:
o + -- A Ja
29:
- Tw + (1 -
30:
end for
31:
end for
13

---

B Proof of Proposition 3.2
Proposition 3.2 Let the projection operator on the column-space of the belief matrix B with respect
to the weighted Euclidean norm -ll be Iw. where W = (31), ...." (3) is steady- augmented state probability vector, and the Markov chain be irreducible i.e, p (5k) > 0 for all
E (1,2..... Then the combined operator Hw Th is n-contraction with respect to I|w.
Proof. Let V1 proj. and V proj. an arbitrary vector in R2, P0 (s')s) be transition probability 3 +
when the agent follow the policy and V.I.proj. 2/2.pros be the k-th element of the V proj. and V2 respectively.
proj.
1w
7
22
llw
(28)
proj.
proj.
[[[ (
T 2
(29)
prj.
proj.
[[[] (T v
proj.
T V?
proj.)
I1(I
IIw (T proj. - 7 22
peoj 1
(30)
!|? proj.
T v2
w
(31)
pruj.
|| + +VP
(R
+ PV
(32)
proj.
proj
= - p" (5x)
E pz (5t 5kk)
V.l.pproj.
V-2.proj.
(33)
S - p" (5k) ) Pa (5t|5t)
V/ V.I.proj. 1/2.pr0s))
(34)
7 Σ/ k= (5x) (5))5(()
11 1.2.proj.
V:2.paus))
(35)
"=/=11"'' (())) (5t)
v,2
(36)
(5k) PT = (5:) by the definition of p
= =7/1V] proj.
V2 proj.
(37)
where Equality (31) holds by the Pythagorean Theorem, and Inequality (34) follows from the Jensen's inequality.
14

---

C
Environment Details
(b)
(d)
(c)
Figure 5: MuloCo continuous control environments the experiment: (a) HalfCheetah-v3, (b)
Walker2d-v3, (c) Hopper-v3, (d) Swimmer-v3, (e) InvertedPendullun-z2, and (f) Reacher-v2.
Table 2: Details of the MuJoCo environment
Action dimension
State dimension
Timestep (s)
HalfCheetah-v3
17
0.05
Walker2d-v3
17
0,008
H3pper-v3 (s)
11
0.008
Swimmer-v3
2
6
0.04
InvertedPendulum--2
0.04
Reacher-v2
2
11
0.02
D Implementation Details
In this section, we provide the implementation details of the algorithms used in this study. All methods presented in the experiment used SAC as their base learning algorithm with the following characteristics:
Stochastic Gaussian policy approaches.
Automated entropy adjustment 14]
Clipped-double Q-learning, which was introduced in the TD3 algorithm prevent overesti- mating the Q-value [12].
Soft target update, which changes the target values slowly and improves the learning stability 21].
Adam optimizer, a variant of the stochastic gradient descent method 19
The details of the hyperparameters are presented in Table 3.
Table 3: Hyperparameters for BPQL and the baselines.
Hyperparameters
Values
Critic network
256, 256
Policy network
256, 256
Discount factor
0.99
Replay memory size
1 M
Minibatch size
256
Learning rate
0.0003
Target entropy
-dim A|
Target smoothing coefficient
0.995
Optimizer
Adam
15

---

E Plots of Performance Comparison
In this section, we present several plots of the performance curves of BPQL and other baselines in the environments with delayed timesteps of 3, 6 and 9.
Delayed 3imesteps=
200
Saimmmnnw
Iwattreheensbmm222
Reachers2
No mal SAC
Delayee SAC Auginer ted SAC jsuns
2003
20009
20.00
2000
Delayed timesteps-6
HaffCheddah-ss
WelBber 2iled
Traattshhnnskkm-22
Augmarted
SPOL (surs)
Delayed timesteps-
HallDedtaha@
Nermal SAC Deliyye SAc Augmented SAC EPOL (cur)
30980
$0980
J0000
100000
Figure 6: Performance curves for each algorithm in continuous tasks with three, six and nine delayed timesteps.
16

---

Additional Experiments
Extremely Long Delayed Environment
We conducted additional experiments determine how well BPQL could solve the control problem even in very long delayed environments. Fhows that BPQL, the policy is improved through interaction with the environment in very long delayed environment, but the conventional methods find it difficult improve their policy.
HalfCheetah-v3 (d=20)
InvertedPendulum-22 (d=25)
6000
Vermal
1000
restid
Avg Return
Return
800
2000
1000
200
0.0
0.2
0.4
0.6
0.8
1.0 0.0 1.0
1.5
2.0
3.0
step (1e6)
Step (1e6)
Figure 7: HalfChectah-v3 environment with 20 delayed timesteps (leff) and InvertedPendulum-VV environment with 25 delayed timesteps (right). Each timestep is 0.05 and 0.04 for HalfCheetah-v3 and InvertedPenduluu--2 environments, respectively. the InvertedPendulum-22 environment, to prevent early failure, the agent pretrained policy to determine the actions of the first 25 (=number of delayed timesteps) timesteps. We repeated the test for the tasks five times with different random seeds.
F.2
Action delay
We also evaluated BPQL and other baselines in action delayed environments. Figure illustrates the interaction between an agent and action delayed environment.
Agent
Environment
2 Ar-d
Delaydd octine
Action
Figure 8: In an action delayed environment, the environment takes the delayed action ar-d instead of current action de, where the number of delayed timesteps.
F.2.1 Augmented State in an Action Delayed Environment
In an action delayed environment, the augmented state time + d defined as:
S (St, at 0t-d+1, ... ,4t-1);
(38)
where the dl is the number of delayed timesteps for an action. The CDMDP for an action delayed environment is defined tuple (X,A,, R, P. 7, 7, da), where X' is the original state space, A is the action space, R x + R the reward function, P: X' A + [0, 1] is the transition kernel, 7 E (0, is discount factor, and d, is the number of delayed timesteps for action.
17

---

This CDMDP can be reduced to MDP (S, P. where S = x A is an augmented state space, R: A the reward mapping. and P x A [0, 1] the transition kernel as in the case of observation delayed environments [8] BPQL. for action delayed environments uses the augmented state defined Equation (38) instead of the one defined in Equation (6)
F.2.2 Results
Deliged Emwetaga13
30000
Figure 9: Performance curves for each algorithm in continuous tasks with action delayed timesteps. We repeated the test for the tasks five times with different random seeds.
Delayed Einesteption
Banatass MD
Figure 10: Performance curves for each algorithm in continuous tasks with 6 action delayed timesteps. We repeated the test for the tasks five times with different random seeds.
Dellyyed Einettaaaii
Figure 11: Performance curves for each algorithm in continuous tasks with 9 action delayed timesteps. We repeated the test for tasks five times with different random seeds.
18

---

F.3 Discrete Domain
We conducted additional experiments on the classical discrete control OpenAl gym 7 tasks: CartPole- v1 and LunarLander-v2. In the CartPole-vl environment, there are two available actions, while in the Lu environment, four actions are available. We compared the performance of BPQL with the Delayed-Q algorithm [10] and Delayed-SAC in various action delay settings. To adapt BPQL. and Delayed-SA to the discrete setting, we implemented a discrete version of SAC [9] for both of them, instead of the original continuous version. We trained the agent for 1 million timesteps in all enviromments (except for Delayed-SAC and BPQL the CartPole-vl task, which was trained for 0.5 million timesteps), and obtained results using 10 random seeds.
The results showed that all algorithms performed similarly in the CartPole-vl environment, which is considered relatively easier. However, in the LunarLander-v2 environment, as the delay increased, both Delayed-Q Q and Delayed-SAC showed a notable deterioration in performance. They even failed to control the agent in many episodes under the 10 timesteps delay setting. In contrast, the proposed BPQL. algorithm consistently maintained high performance across all tested delay settings (3,5, and 10).
Table 4: Results OpenAI Gym's discrete tasks. All results are shown with the standard deviation the ten trials denoted by +. The scores of Delayed-Q in CartPole-vl are sourced from the original paper [10] and marked with *
Environment
Delayed-Q [10
Delayed-SAt -AAC (discrete ver.)
BPQL (discrete ver.)
CartPole-vl (d=15)
444
411:75
464160
CartPole-vl (d=25)
324
396:167
3671994
LunarLander-v22 (d=3)
247:123
285
275 10
LunarLander--2 (d=5)
1731993
28244
256+53
LunarLander-v2 (d=10)
-84167
172
245
19


Reviews:
[{"review_id": "LJeUnuQK9s", "reviewer": "Reviewer_MGmU", "summary": "The paper proposes a new belief projection-based method for approximating delayed states in reinforcement learning. The method is derived from basic principles with properties of the projection demonstrated. The method is then transformed into a practical, model-free approach, that is extensively evaluated and bench-marked, with promising results.", "questions": "- See small writing suggestions above\n- The belief projection method comes a bit out of the blue, can you better motivate why this is a good idea?\n- The setting is connected to POMDPs where there is quite a bit of literature but which is only mentioned in passing. Can you discuss the relation a bit better?\n- Please detail the limitations better, you mention random delayed environments which are an obvious limitation.\n  * Do you think the method would still perform reasonably if there is some small randomness in the delay (even if that's not backed by the theory)?\n  * What are the implications of the linear approximation?\n  * More generally, this seems to be a lossy compression, bringing everything back down to the original state-space size. In which cases will having the full augmented state (and infinite data etc.) still result in better performance?\n  * Can you do something in between, i.e., project to a slightly larger state-space?", "limitations": "- societal impact is not really applicable\n- an explicit discussion on limitations is a bit short (see above)", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is easy to follow, the derivations are cleanly done and well explained.\n- The idea is interesting and sound\n- I really liked the logical progress of deriving the method with the assumption of having access to all the probabilities etc. and then step by step turning it into a practical method\n- The experiments show a good number of baselines, and sufficiently many standard benchmarks. The ablation with the delay steps, network capacity, and stochasticity are well done. The number of repetitions is adequate.\n- The method shows clear experimental benefits", "weaknesses": "- I found Sect 2.1 and 2.2 a tiny bit confusing in terms of notation initially. Especially in Sect 2.1 it was initially not clear why X is used and initially it wasn't clear to me that the reward is also delayed (Sect 2.2). Just some minor writing tweaks\n- Sect. 2.2: in conventional control having a system-model-based observer (e.g. Kalman filter) is also quite common - not just the augmented state - similar to the methods described a bit further down\n- In Sect. 1 it almost sounds like the method also considers (or should consider) varying delays for e.g. hardware issues. I'd suggest making more clear from the start that you consider constant delays.\n- I would have appreciated some little outline/forward pointer. On the first read I was a bit puzzled by the apparent assumption e.g. in Eq (7) of having access to the full model while initially a model-free method was promised. Briefly explaining the structure of the paper in the beginning would avoid that confusion.\n- missing limitations (see below)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "j6PksXCjqa", "reviewer": "Reviewer_3qfv", "summary": "This paper addresses the issue of delayed feedback in reinforcement learning,\nwhere the observations and rewards received by the agent are those generated by\nthe environment multiple (`d`) time steps ago, most commonly caused by latency\nin hardware. This problem is typically solved by augmenting the policy and    \nvalue functions with the `d` previous actions, recovering the Markov property                                                  \nof the problem. This paper argues that this augmented 'state space' is                                                         \nprohibitively large and proposes Belief-Projection-Based Q-learning (BPQL) as a                                                \nfix to the issue.                                                                                                              \n                                                                                                                               \nBPQL modifies SAC such that the value function (critic) that is being learned\nonly takes the observation (and not the `d` actions) as input (though the                                                      \npolicy (actor) still depends on the augmented space). The result is an       \napproximation of the original problem, where the critic learns the expected\nvalue of the policy based on just the last observation, as opposed to the    \nobservation and last `d` actions.                                                                                              \n                                                                                                                               \nThis approach is motivated by a substantial theoretical section that derives  \nand discusses the (approximated) loss function. The method is compared against                                                 \naugmented SAC, a model-based approach, and regular SAC on MuJoCo for different\ndelays.            ", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper proposes a high-performance solution to the complex problem of    \ndelayed feedback. It does so in a fairly simple (in the positive sense) way                                                                                                                                                                                   \nthat should be easily implementable and testable.                                                                              \n                                                                                                                               \nAnother advantage is the theoretical support of what otherwise would be a\nfairly ad-hoc solution. This is particularly useful because, in my opinion, the\nintuition of BPQL is fairly nice: the critic can ignore the additional action\nhistory input because this depends only on the policy it is evaluating: the\naction sequence of the policy is relatively 'stable', or determined, so not\nparticularly variable or something that needs to be given to the critic in    \norder to evaluate the expected return. \n\n======== post rebuttal ==========\n\nThe authors brought up reasonable arguments, context, and experiments to defend their work. I would personally still learn towards rejection due to the fact that, in its current form, I believe that the combination of the presentation, algorithmic contribution, and empirical evaluation are in my opinion relatively weak. However, I do not feel strong enough about this to champion for a rejection when others disagree.", "weaknesses": "Despite these strengths, there are a few concerns that makes me lean towards\nrejection.\n\nWhile the experiments show otherwise, I am slightly surprised that the action\nspace is big enough to cause issues in terms of policy evaluation and would\nneed more data to be truly convinced. Clearly augmented SAC is suffering but,\nunless there is something particular about these problems (of which I have no\ndetailed knowledge), generally the observation/state space is so much larger\nthan the action space that the additional input of `d` actions should not be\nthat significant.\n\nRegarding clarity, the presentation of the paper was in my opinion confusing:\nFirst, the method section contained a substantial amount of information that\nwould fit better in the background (e.g. 3.1, 3.2, and the start of 4). Second,\nthere was a very limited amount of information on the idea behind the paper or\nits overview until you start digging into the details. For example, until the\nlast paragraph before the experiment section I had no idea where this was\ngoing. Additionally, the theoretical section seems to attempt to justify the\napproximations made by BPQL, but that was not clear at all until diving into\nthe section afterwards.\n\nMost importantly, i still struggle to understand the theoretical support. I\nbelieve it eventually it provides a theoretical explanation for BPQL's loss\nfunction, but I only truly understand the loss function from a intuitive\nperspective and had to gloss over section 3 altogether. The main reason I lean\ntowards rejection is because it was not presented in a way that the theoretical\nsection was a contribution to me. This mostly because it is fairly 'easy' to\npropose to 'just drop' some input to reduce the space and have it work well for\nsome problems. So the theory is important here but, in my perspective,\ndifficult to understand.\n\nLastly, some ablations that would be very informative are missing. For example,\nit is clearly important that the policy accepts the augmented space (because\nthat seems to be the key difference between BPQL and 'normal SAC'), but the\nobvious alternative is to do some variant where the policy takes in only the\nlast observation but the critic gets the augmented input. I think more in depth\nexperiments would further motivate the approach. In particular, I would want to\nsee why it is so important that the policy does accept the last `d` actions as\ninput: is this a property of the problems, or is there some theory or intuition\nthat explains this discrepancy?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "3XA2GsFk4g", "reviewer": "Reviewer_HRKg", "summary": "This paper aims to tackle the delayed feedback RL problem. In such a problem setting, usually there is some fixed/constant delay in the environment, so that the observed rewards are delayed by $d$ timesteps. Traditionally, augmented state spaces have been used to solve such an issue, however, for large delays this leads to an exponentially large dimension for learning the value function. Thus, the proposed approach (BPQL) leverages the deconstruction of the augmented value function via the belief matrix into a lower dimensional beta q value function, and shows that this approximates the augmented q function (derived from the soft bellman update). This outperforms baselines on a variety of control tasks.  ", "questions": "See weaknesses section", "limitations": "This has been sufficiently addressed", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- I think there is good technical novelty and soundness in this paper\n- The problem space is very interesting and relevant to real world applications\n- BPQL drastically outperforms basleines \n- This approach is general (as it applies to continuous settings) ", "weaknesses": "I think it would be interesting to explore this idea on different types of environment delay (for example delays coming from different sources like actuators, sensors, etc. It would also be good to see more analysis and ablations on different levels of delays (value of $d$). \n\nFinally, it would be great if this apporach applied to more realistic robotics settings (even simulated versions). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear HRKg,\n\nWe sincerely appreciate your positive review and your interest in the problem space our paper aims to address. Based on your suggestions, we have conducted additional tests and provide the details as follows:\n\n**Different types of delay & Ablation**\n>“I think it would be interesting to explore this idea on different types of environment delay (for example delays coming from different sources like actuators, sensors, etc. It would also be good to see more analysis and ablations on different levels of delays (value of d).”\n\nIn the field of robotics, delays occur in various scenarios such as remote robot control, communication in low bandwidth, and complex control algorithm with on-board devices (sensors, actuators) with low computational capacity. Environments with these delays can be categorized into the following three types:\n* Observation delay environment\n* Action delay environment\n* Combined (Observation + Action) delay environment\n\nIn the main text, BPQL mainly conducted experiments in environments where observation delay only exists. However, BPQL is a general algorithm that can be applied not only to observation delay scenario but also to action delay scenario and even the combined delay scenario. To validate the generality of BPQL, we conducted an additional experiment evaluating performance under various delay combinations, and the results are listed in the table below.\n||HalfCheetah-v3|Walker2d-v3|Hopper-v3|\n|-|-|-|-|\n|Obs. delay=5 / Act. delay=0|6371.4+-181.9|4363.3+-332.0|3144.1+-528.17|\n|Obs. delay=0 / Act. delay=5|6459.1+-204.8|4008.2+-663.8|2736.8+-931.6|\n|Obs. delay=3 / Act. delay=2|6332.4+-210.4|4399.7+-455.5|2802.8+-670.8|\n|||||\n\nFrom the results, we confirmed that BPQL shows promise not only in single delay environments but also in combined delay environments. This generality of BPQL allows for broader application in addressing the significant latency issue in the field of robot learning.\n\n**Additional experiments on a realistic robotics setting**\n>\"it would be great if this approach applied to more realistic robotics settings (even simulated versions).\"\n\nTo further demonstrate the practicality of BPQL, we conducted an additional experiment in a more industry-oriented simulation task called Pusher-v4 from OpenAI Gymnasium. Pusher-v4 is a collaborative arm robot with multiple joints, resembling a human arm. The objective of the task is to move a target object to a specific goal position using the robot's end effector. In this experiment, we added sensing delays of 200 ms and 500 ms in the environment, and the results are presented in the table below.\n\n||delay=200 ms|delay=500 ms| \n|-|-|-|\n|Baseline (SAC w/o delay)|-21.0+-0.6|-21.0+-0.6|   \n|SAC|-88.5+-10.9|-166.0+-3.9|\n|BPQL|-22.7+-0.7|-24.8+-1.5| \n||||\n\nThe results show that, even with the presence of delay, BPQL demonstrates comparable performance to the delay-free environment (baseline SAC), reaffirming its potential."}, {"review_id": "Tv7GOyYdmi", "reviewer": "Reviewer_iPGm", "summary": "The authors propose a projection approach for more compactly representing the value function of a delayed system in reinforcement learning. A complete algorithm based on SAC with neural network approximations is presented and benchmarked on four Mujoco environments where it outperforms competing approaches.", "questions": "1) The text is a bit vague on what added assumptions / complexity there is of the beta q-function representation. Initially it seemed like the state transitions/beta matrix would have to be estimated separately in (10) where a linear projection was used.  Later a \"practical approximation\" is introduced where it seems the beta Q-function can be updated iteratively via sampling as normal in Q-learning? Does this preserve optimality or is it an approximation (further approximation on top of regular NN SAC). If not optimal, can you clarify what added assumptions there actually are?\n\n2) Why is it performing better even on the noisy environment without delay? This is not obvious from the claimed contributions.\n", "limitations": "To be clarified, the method seems very general.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper addresses an important problem when applying RL on real-world systems: latency. This is a common issue in robotics in particular. As such, a good solution would be of considerable value to the robot learning community.\n\n- The paper is well-written and mostly easy to read\n\n- The approach demonstrates impressive improvements on delayed systems in Mujoco benchmarks\n\n", "weaknesses": "- The experiments are only on four rather simple Mujoco control benchmarks. It would have been nice to have something more realistic, but I think the results were clear enough to establish the promise of the approach.\n\n- A few important details could be more clear (see questions below)\n\nSide note: Code is included but not publicly released. As the RL community has struggled with reproducibility due to small discrepancies in implementations, this would have been nice.\n\nMinor:\n- Not sure what you mean by \"agnostic random delayed environment\" in the conclusions? If you just mean randomly delayed environments, that sentence can be simplified a lot.\n\n------------ \nAfter rebuttal:\n\nThe authors addressed all of my concerns and therefore I raise my score to a 7. This paper could be very useful to better solve delayed control problems, which I can attest to being common in robotics. That said I agree with Reviewer 3qfv that the method sections were needlessly difficult to read. However, the authors promised to add some intuitions earlier in the final manuscript, which I think will be good enough. I thank the authors for their work and encourage them to open source their code so there is less room for misunderstandings by future work on this important problem.\n \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer iPGm,\n\nThank you very much for your positive review and for acknowledging our contributions. We have carefully read your comments, and we would like to provide additional details as follows:\n\n**Additional experiments on a realistic control task**\n>“The experiments are only on four rather simple Mujoco control benchmarks. It would have been nice to have something more realistic, but I think the results were clear enough to establish the promise of the approach”\n\nIn addition to our experimental results, we performed an industry-oriented simulation task _Pusher-v4_ ;a collaborative robot to further validate the practicality of our algorithm. \"Pusher-v4\" is an environment from OpenAI Gymnasium, which features a multi-jointed robot arm resembling a human arm. The goal is to move a target object to a specified goal position using the robot's end effector.\n\nWe conducted experiments in the Pusher-v4 environment where 200 ms and 500 ms sensing delay exist. The results are shown in the table below.\n\n||delay=200 ms|delay=500 ms| \n|-|-|-|\n|Baseline (SAC w/o delay)|-21.0+-0.6|-21.0+-0.6|   \n|SAC|-88.5+-10.9|-166.0+-3.9|\n|BPQL|-22.7+-0.7|-24.8+-1.5|  \n||||\n\nThe results confirm the promise of BPQL, showing comparable performance to the delay-free environment (baseline SAC) despite the presence of delay.\n\n**Algorithm details**\n>“The text is a bit vague on what added assumptions ... Initially it seemed like the state transitions/beta matrix would have to be estimated separately in (10) where a linear projection was used.”\n\nYes, In the practical version, we do not estimate the belief matrix and transition probability separately to compute the beta-Q value. Instead, we incrementally estimate the beta-Q-values based on the samples obtained through interactions with the environment. This sampling-based learning is a key characteristic of reinforcement learning, and in this setting, Q-values are proven to converge (Tsitsiklis and Van Roy, 1996).\n\n>“Later a \"practical approximation\" is introduced where it seems the beta Q-function can be updated iteratively via sampling as normal in Q-learning? “\n\nYes. The beta Q-function learns similarly to a normal Q-function, using \"timely properly-aligned\" transition tuples $(s_t, a_t, r_t, s_{t+1}). $ However, this is **not same situation**. Because the action $a_t$ is obtained from the policy with the augmented input ($s_{t-d}, a_{t-d}, ... , a_{t-1}$) but not $s_t$ (which is not observed yet due to the delay). Consequently, unlike the normal Q-function that learns true Q-values, the beta Q-values approximates (linearly) the true Q-value, and BPQL has a unique characteristic: the (beta) Q-function is evaluated using a reduced (original) size of state, while its policy uses an augmented state size to choose an action (Eq. 24, 25).\n\n**Assumption behind the algorithm**\n>“Does this preserve optimality or is it an approximation ... If not optimal, can you clarify what added assumptions there actually are?”\n\nUnfortunately, neither the iterative method (Section 3) nor the practical version (Section 4) can guarantee optimality, even though the beta value converges. This is because the beta value is an approximation of the true value that ignores the residual (Eq. 11, 12). If an environment is extremely chaotic, the norm of this residual cannot be ignored smoothly, leading to a gap between the optimal policy and the learned policy. \n\nIn this paper, we **assume** that the linearly approximated value in most real-world continuous tasks can **sufficiently represent** the true value. Indeed, in various MuJoCo benchmark experiments, BPQL showed better performance than the baselines and even outperformed Augmented SAC, which theoretically learns the true \"error-free\" value.\n\n**Optimality Analysis**\n\nAdditionally, using a property of linear approximator, an interesting error-bound can be derived as follows:\n\n*Proposition.*\n\nLet  $\\hat{V}^{*}_{proj.}$ be the unique fixed point calculated by repeatedly applying the combined operator \n\n$\\Pi_{\\textbf{W}}\\bar{\\textit{T}}^{\\bar{\\pi}}$, and $V_{true}$ be the true value of the policy. Then,\n\n$||V^{true}-\\hat{V}^{\\ast}_{proj.}||^2_W \\leq \\frac{1}{\\sqrt{1-\\gamma^{2}}}||V^{true}-\\Pi_W V^{true} ||^2_W$.\n\n*Proof.*\n\n$||V^{true}-\\hat{V}^{\\ast}_{proj.}||^2_W$\n\n$=||V^{true}-\\Pi_W V^{true}||^2_W$ $+||\\Pi_W V^{true} -\\hat{V}^{\\ast}_{proj} ||^2_W$\n\n$=||V^{true}-\\Pi_W V^{true}||^2_W+||\\Pi_W V^{true}-\\Pi_{W}\\bar{T}^{\\bar{\\pi}}\\hat{V}^{*}_{proj.}||^2_W$ \n\n($\\because \\hat{V}^{\\ast}_{proj.}$ is the fixed point of the combined operator.)\n\n$\\leq ||V^{true}-\\Pi_W V^{true}||^2_W + \\gamma^2||V^{true}-\\hat{V}^{*}_{proj.}||^2_W$  \n\n(by $\\gamma$-contraction property of the combined operator.)\n\n$\\blacksquare$\n\nThis implies that the projection $\\hat{V}^{\\ast}_{proj,}$ is, at least, not far from the true value $V^{true}$. \n\n**Noisy Environment**\n>“Why is it performing better even on the noisy environment without delay”?\n\nIn the noisy inverted pendulum environment, the delayed timesteps are six, not zero. We speculate that the reason for your misconception might be due to the small font size in the figure. If that's the case, we sincerely apologize for the confusion, and the font size will be adjusted for better readability in our camera-ready version of the paper.\n\n**Open-sourcing the code**\n>“Code is included but not publicly released. As the RL community has struggled with reproducibility ... this would have been nice.”\n\nOf course! We are thrilled and delighted to share our code to RL and robot learning community. Once our paper is published, the source code will be made accessible to everyone.\n\n**Minor**\n>“Not sure what you mean by \"agnostic random delayed environment\" in the conclusions? If you just mean randomly delayed environments, that sentence can be simplified a lot.”\n\nThank you for pointing this out. We agree that removing 'agnostic' from the sentence simplifies it significantly. we'll make the modification in the our final version of the paper."}, {"review_id": "Ocp8ANzFqI", "reviewer": "Reviewer_ozYa", "summary": "This work proposes a solution to the delayed feedback problem, in this case a fixed timestep delay. There are approaches to solving this problem in the literature, often associated with cumulative error or un-traceability given longer delays. One common approach — using augmented states by concatenating observed states & actions taken since visiting the delayed state — which grows exponentially the augmented state space as the delay increases. The authors’ algorithm (Belief Projection Based Q-Learning, BPQL) is formally shown to equally represent augmented state-based (Q-)Values. Further, the introduced belief-projection of those values is shown to be decomposable over the original states + residuals, therefore working on the original state-dimensionality rather than the exponential one of augmented state learning. The values are shown to be linearly approximable, an insight, which the authors then use to reformulate the discrete version into a continuous control version of a Belief-based Actor-Critic Algorithm, which outperforms naive/ augmented (-model) approaches of the soft-actor-critic in an delayed version of the MuJoCo benchmark.", "questions": "Aside from concerns mentioned above, the following questions arise: \n- Why is the belief-projection chosen here and how would you motivate this decision?\n- Why was the SAC algorithm chosen as the baseline, how was it parameterized and how would common baselines like A2C or PPO compare in this setting?\n- What is the runtime overhead of computing the belief-projection compared to the (technically simpler) augmented state techniques?\n- Would it be possible to show e.g. memory-complexity of the baselines and of BPQL as a metric in the specific case of MuJoCo domains here? L.225ff mentions that the algorithm also stores augmented states (original states and action history) in an extra temporary buffer, could you please contextualize this to augmented state learning? (As mentioned above, this would also be information to include in the compute-resource / runtime statement.)", "limitations": "Assumptions and limitations are stated in the context of the formalization. No potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The approach is formulated on a quite technical level and appears to be a novel application of belief-based ML to the delayed feedback problem. There is related work in different directions cited for solving delayed environments (augmented approaches, model-based predictions, expectation minimization Q-Learning), although I am not very familiar with the augmented techniques, with are directly compared against here. The reasoning towards the belief based Q-Learning Actor-Critic seems to differentiate enough from Agarwal&Aggarwal2021, which they cite as closest related work.\n- The mathematical reasoning seems reasonable as far as I can follow. The underlying constant delayed MDP and the assumptions are stated clearly. Furthermore, MuJoCo represents an appropriately difficult evaluation domain and the evaluation is sound, although there is no compute resource or training-time mentioned (as far as I can tell).", "weaknesses": "- The paper seems to be missing a discussion on the related concept of belief-state architectures, which may be considered related to the model-based approaches mentioned here but with more relevance to this chosen approach.\n- One point of concern I have with the claimed novelty compared to Agarwal&Aggarwal2021 in the difference of developing a continuous control algorithm, rather than a discrete model. I find it confusing that much of the definition of the BPQL / Actor-Critic model revolves around Q- Values and Q-Learning (the Q-Function, as it is called here) which are an inherently discrete concept The authors mention a generalization to continuous control problems, but the transfer l.228-224 reads more like an afterthought to position the algorithm in a niche without direct comparison benchmarks. If most of the work covers the Q-Learning approach it would be informative to proof performance in this approach compared to e.g. Agarwal&Aggarwal2021 or the DDQN Model-based approach of van Hasselt. et. al. 2016 before evading into the novelty of continuous problems.\n- Furthermore, the paper is lacking a motivation on why belief-based projection is an appropriate technique and was chosen here (aside from not dealing with exponentially growing state-spaces, which is repeated ... often enough). The reader is presented with a very final formulation of the belief matrix and belief projection operator initially, with the following pages re-contextualizing the known MDP / Bellman Equation into this framework. Without a background in control theory or kernel operators (and given the lack of references) I assume this part to be proposed by the authors or established theory, but without any descriptive intuition behind this formalization, much Chapter 3 reads like a proof that would be usually found in the Appendix. For a clearly readable publication I find this submission is written without the reasoning to convey its key-ideas behind the formalities to a broader audience.\n- Given that the evaluation is based on the AC method, I would have preferred to have the AC technicalities in the paper itself rather than the Appendix. Some of the implementation details I found helpful to reason about the evaluation results were found in the Appendix and only the code itself. However, given the technical nature of the paper I would understand why they were cut.\n- \nI feel conflicted about claiming significant performance gains against the mostly self-constructed SAC baselines with ‘only’ 1M training steps on a complex domain like MuJoCo. The evaluation does seem cleanly run and favorable for the BPQL approach (at least in terms of sample efficiency), however, I would argue that only 1M steps is a debatable length for some of these problems to be solvable by the intentionally slow SAC algorithm (regardless of hidden-dim size, not even accounting for delay complexity). Out of the three baselines, the naive SAC is akin to the random baseline and the adjusted model-DDQN baseline was not originally designed for a SAC and is therefore hard to judge in terms of comparability. As mentioned above, it seems as if this work is introducing a Q-Value approach and evaluating on continuous control problems that are a short transfer away, but is not comparing to established discrete solutions to this problem. If better benchmarks for this specific environment niche (continuous control delayed feedback) are not available, it would be nice to see the theoretical maximum reward per domain or other relational metrics that would indicate how the BPQL is performing in general, not just compared to the benchmarks. Apart from the baseline evaluation, the belief-projection application seems like an improvement in terms of computability and therefore, sample efficient training for delayed environments.\n- While the BPQL approach may be employed to any fixed step delay environment, with the initial setting of ‘uncertain latency’ that is motivated in the introduction, the authors are correct in listing this fixed-step assumption as a notable limitation. Especially in the continuous domain case (which is the differing focus of this work), having one (small) continuous, fixed delay signal is quite the niche. Nevertheless, given the defined setting the proposed algorithm shows promise in it’s intended purpose.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer ozYa,\n\nWe want to sincerely thank you for the valuable effort you put into providing constructive feedback. We have carefully considered each of your comments, and provide additional details as follows:\n\n**Novelty**\n\nIn addition to its applicability in continuous domains, BPQL has several distinct aspects compared to Agarwal&Aggarwal 's method (EMQL). In BPQL, the Q-function is evaluated using a reduced state size, while its policy uses an augmented state size to choose actions. Thus, the state sizes for the policy and Q-function are different, a **unique** feature not found in pure Q-Learning approaches like EMQL. Additionally, EMQL relies on a count-based model, making it challenging to apply in cases with large state and action dimensions, even in discrete environments. However, BPQL overcomes this issue by **not relying on an explicit model**, making it a truly \"model-free\" approach, in contrast to EMQL's \"model-based\" approach.\n\n**Discrete environments**\n>\"it would be informative to proof performance in this approach compared to e.g. Agarwal&Aggarwal2021 or the Model-based approach ... before evading into the novelty of continuous problems.\"\n\nIn the field of _robot learning_, latency is well-known for degrading performance. To address this issue, we developed BPQL, specifically designed for continuous robotic domains. Nevertheless, we agree that comparing our algorithm's performance with other algorithms in discrete domains would effectively demonstrate the generality of our approach. Therefore, we conducted an additional experiment with EMQL on discrete environments in OpenAI Gym. For this experiment, we implemented BPQL using the discrete version of SAC . The results are as follows:\n\n|CartPole-v0|d=2 / Epi=200|d=2 / Epi=1000|d=4 / Epi=200|d=4 / Epi=1000|\n|-|-|-|-|-|\n|EMQL|<= 80|<=150 |<=70|<=125|\n|BPQL|169 ±13|200±0|109±8|200±0|\n\nWe also conducted another experiment to compare the performance with Delayed-Q (Derman et al.,2021) on discrete environments.\n\n|Cartpole-v1|Delayed-Q|BPQL|\n|-|-|-|\n|d=15|414±14|**464±60**|\n|d=25|324±7|**367±94**|\n|**Acrobot-v1**|**Delayed-Q**|**BPQL**|\n|d=15|**-211±53**|-246.8±206|\n|d=25|-351±57|**-335.3±202**|\n\n(_± denotes std._)\n\nBPQL's strong performance demonstrates its potential not only in continuous but also in discrete settings.\n\n**Longer Interaction**\n>“However, I would argue that only 1M steps is a debatable length ... ”\n\nTo address this, we extended the evaluation to 2M and 3M steps. Model-based SAC didn't improve beyond 1M steps, but Augmented SAC showed notable improvement with more interactions due to its theoretical error-free TD learning. However, BPQL still outperformed it.\n\n|d=9|HalfCheetah-v3||Hopper-v3||Walker2d-v3||\n|-|-|-|-|-|-|-|\n|steps|2M|3M|2M|3M|2M|3M|\n|Augmented SAC|1362±40|1463±51|2476±783|2821±627|2970±897|3223±841\n|BPQL|5980±321|6214±108|2983±834|3120±561|4368±701|5130±472|\n\n\n**Relational metric**\n>“It would be nice to see the theoretical maximum reward per domain or other relational metrics ...”\n\nWe agree that adding a relational metric in the comparison table would improve the clarity of our experiment and provide a better understanding of the impact of delays on the algorithms. Hence, we examined the performance of SAC in a \"delay-free\" environment as a comparison metric. The performance of delay-free SAC is as follows:\n\n|(1M steps)|HalfCheetah-v3|Walker2d-v3|Hopper-v3|Swimmer-v3|InvertedPendulum-v2| Reacher-v2|\n|-|-|-|-|-|-|-|\n|SAC|11202±423|4733±728|3145±429|91.2±12|1000±0.0|-3.8±0.6|\n\n**Questions**\n>**Q 1.** Why is the belief-projection chosen ... motivate this decision?\n\nWe chose belief projection (BP) to find the best latent space representing the augmented state. In ML literature, dimensionality reduction methods like PCA and VAE have shown significant benefits for training. To leverage these advantages in RL, we incorporated a projection-based state reduction method into our algorithm. Additionally, as we discussed in Line 134-137, we assumed that similar successive transition probabilities imply similar meanings for the augmented states. Thus, we selected BP as the state reduction method.\n>**Q 2.** Why was the SAC algorithm ... compare in this setting?\n\n SAC is one of the SOTA algorithms used in continuous tasks, usually outperforming PPO in the MuJoCo control tasks (Haarnoja et al. 2018). Therefore, we integrated SAC into BPQL. And the policy is parameterized to represent the squashed Gaussian distribution.\n>**Q 3.** What is the runtime overhead ... ?\n\nThe dominant part of both algorithms in the runtime is the learning process (GPU load + neural network training).  We evaluated the Monte Carlo estimation for the learning process:\n \n||Augmented SAC|BPQL| \n|-|-|-|\n|Learning time (1 iter.)|8.98 ms|9.32 ms|   \n|||\n\nwith the following resources:\n* CPU: i7 9700K\n* GPU: GTX 1080 TI\n* RAM: 48GB\n\nThe experiments were conducted in the HalfCheetah-v3 with a delay of 9. BPQL uses a Q-function network with fewer parameters than Augmented SAC, yet it incurs 3% runtime overhead. This is likely due to the increased loading of transition tuples to the GPU from BPQL's temporary buffer.\n>**Q4**. Would it be possible to show e.g. memory-complexity ... \n\nLet M be the maximum size of the replay memory, A be the dimension of the action space, d be the delayed timesteps, and S be the dimension of the state space. Then the memory-complexity for Normal SAC is $O(M(A+2S+2))$, and for Augmented SAC, it is $O(M(A+2(\\underbrace{S+dA}_{\\text{augmented state}})+2)+Ad)=O(M(A(1+2d)+2(1+S)))$. The terms $Ad$ represent the space required for storing action history to create augmented states. BPQL adds two original-sized states to the tuple used in the replay memory of Augmented SAC, resulting in a complexity of $O(M⦁(A+2S+2(S+dA)+2)+2(S+Ad+1))=O(M(A(1+2d)+2(1+2S)))$.  The term $2(S+Ad+1)$ represents the space required for constructing the temporary buffers. Both are omitted in the Big O notation as M >> Ad and M >> 2(S+Ad+1)."}]

Author rebuttal:

Meta-review: The paper proposes a new method for solving decision making problems with delayed feedback. The approach is based on reducing the augmented state dimension by belief projection. The practical method derived from the theoretical results is extensively evaluated.

The reviewers found the proposed method and experiments interesting and promising. A few questions regarding the contribution, impact of action space, too simple experimental environments, details of the method, limitations, and reasoning of design choices were raised.

The rebuttal addressed all major concerns of the reviewers.

3 of the 4 reviewers have a clear vote for accepting the paper, the last reviewer is leaning slightly towards rejecting the paper with concerns about the paper as a "package". While the paper certainly has its limitations (also pointed out by the authors), I believe it makes an interesting contribution and step forward that is worthwhile presenting to the community.
Decision: Accept (poster)