State Sequences Prediction via Fourier Transform for Representation Learning
Authors: Mingxuan Ye
Yufei Kuang
Jie Wang
Rui Yang
Wengang Zhou
Houqiang Li
Feng Wu
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Reinforcement learning
Representation learning
State sequences prediction
Fourier transform
TL;DR: A representation learning method that predicts the Fourier transform of state sequences to improve sample efficiency of RL algorithms.

Abstract: While deep reinforcement learning (RL) has been demonstrated effective in solving complex control tasks, sample efficiency remains a key challenge due to the large amounts of data required for remarkable performance. Existing research explores the application of representation learning for data-efficient RL, e.g., learning predictive representations by predicting long-term future states. However, many existing methods do not fully exploit the structural information inherent in sequential state signals, which can potentially improve the quality of long-term decision-making but is difficult to discern in the time domain. To tackle this problem, we propose State Sequences Prediction via Fourier Transform (SPF), a novel method that exploits the frequency domain of state sequences to extract the underlying patterns in time series data for learning expressive representations efficiently. Specifically, we theoretically analyze the existence of structural information in state sequences, which is closely related to policy performance and signal regularity, and then propose to predict the Fourier transform of infinite-step future state sequences to extract such information. One of the appealing features of SPF is that it is simple to implement while not requiring storage of infinite-step future states as prediction targets. Experiments demonstrate that the proposed method outperforms several state-of-the-art algorithms in terms of both sample efficiency and performance.

State Sequences Prediction via Fourier Transform for Representation Learning
Mingxuan Ye!
Yufei Kuang!
Jie Wang! 1.2
Rui Yang!
Wengang Zhou
Houqiang Li
Feng Wu!
CAS Key Laboratory of Technology in GIPAS, University of Science and Technology of China lIsttitute of Artificial Intelligence, Hefei Comprehensive National Science Center {mingxuanye, yfkuang, yr0013)@mail. ustc. edu. (jiewangx, zhag, lihq, (ingu]@uustr eeutt..edd..com cn
Abstract
While deep reinforcement learning (RL) has been demonstrated effective solving complex control tasks, sample efficiency remains a key challenge due to the large amounts of data required for remarkable performance. Existing research explores the application of representation learning for data-efficient RL, e.g., learning predic- tive representations by predicting long-term future states. However, many existing methods do not fully exploit the structural information inherent in sequential state signals, which can potentially improve the quality of long-term decision maaking but is difficuut to discern in the time domain. To tackle this problem, propose State Sequences Prediction via Fourier Transform (SPF), a novel method that exploits the frequency domain of state sequences to extract the underlying patterns in time series data for learning expressive representations efficiently. Specifically, theoretically analyze the existence of structural information in state sequences, which is closely related to policy performance and signal regularity, and then propose predict the Fourier transform of infinite-step future state sequences extract such information. One of the appealing features of SPF is that is simple implement while not requiring storage of infinite-step future states prediction targets. Experiments demonstrate that the proposed method outperforms several state-of-the-e algorithms in terms of both sample efficiency and performance." ?
Introduction
Deep reinforcement learning (RL) has achieved remarkable success in complex sequential decision- making tasks, such computer games [1], robotic control [2], and combinatorial optimization [3]. However, these methods typically require large amounts of training data to learn good control, which limits the applicability of RL algorithms real-world problems. The crucial challenge is improve the sample efficiency of RL methods. To address this challenge, previous research has focused on representation learning extract adequate and valuable information from sensory data and train RL agents in the learned representation space, which has been shown to be significantly more data-efficient [4-8]. Many of these algorithms rely on auxiliary self-supervision tasks, such as predicting future reward signals [4] and reconstructing future observations [5], to incorporate prior knowledge about the environment into the representations.
"Corresponding Author
"The code of SPF available on GitHub httpp::/ggichub.com//AAA// /ttp
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Due to the sequential nature of RL tasks, multi-step future signals inherently contain more features that are valuable for long-term decision-making than im- mediate future signals. Recent work has demon- strated that leveraging future reward sequences as su- pervisory signals is effective in improving the gener- alization performance of visual RL algorithms [9, 10]. However, we argue that the state sequence provides a more informative supervisory signal compared to the sparse reward signal. As shown in the top portion of Figure 1, the sequence of future states essentially de- termines future actions and further influences the se- quence of future rewards. Therefore, state sequences maximally preserve the influence of the transition intrinsic to the environment and the effect of actions generated from the current policy.
Klnuel
A state sequence under M (T.
Ma = (TH)P)
Ma (ma)p)
1996
Figure 1: State Sequence Generation Pro- cess. The top row displays sample of state sequences generated from MDP M. The bot- tom two rows visualize two state sequences in the time and frequency domains respectively. Each column corresponds to state sequence generated from a different policy.
Despite these benefits of state sequences, it is chal- lenging to extract features from these sequential data through long-term prediction tasks. A substantial ob- stacle is the difficulty of learning accurate long-term prediction models for feature extraction. Previous methods propose making multi-stop step predictions using a one-step dynamic model by repeatedly feeding the prediction back into the learned model [1 1- 13]. However, these approaches require high degree of accuracy in the one-step model to avoid accumulating errors in multi-step predictions [13]. Another obstacle is the storage of multi-step prediction targets. For instance, some method learns specific dynamics model directly predict multi-step future states [14], which requires significant additional memory to store multi-step future
states as prediction targets.
To tackle these problems, we propose utilizing the structural information inherent in the sequential state signals to extract useful features, thus circumventing the difficulty of learning an accurate prediction model. In Section 4, we theoretically demonstrate two types of sequential dependency structures present in state sequences. The first structure involves the dependency between reward sequences and state sequences, where the state sequences implicitly reflect the performance of the current policy and exhibit significant differences under good and bad policies. The second structure pertains to the temporal dependencies among the state signals, namely the regularity patterns exhibited by the state sequences. By exploiting the structural information, representations can focus on the underlying critical features of long-term signals, thereby reducing the need for high prediction accuracy and improving training stability [13].
Building upon our theoretical analyses, we propose State Sequences Prediction via Fourier Transform (SPF), a novel method that exploits the frequency domain of state sequences to efficiently extract the underlying structural information of long-term signals. Utilizing the frequency domain offers several advantages. Firstly, it is widely accepted that the frequency domain shows the regularity properties of the time-series data [15-17]. Secondly, we demonstrate in Section 5.1 that the Fourier transform of state sequences retains the ability to indicate policy performance under certain assumptions. Moreover, Figure provides an intuitive understanding that the frequency domain enables more effective discrimination of two similar temporal signals that are difficult to differentiate in the time domain, thereby improving the efficiency of policy performance distinction and policy learning.
Specifically, our method performs an auxiliary sulf-supervision task that predicts the Fourier transform (FT) of infinite-step state sequences to improve the efficiency of representation learning. To facilitate the practical implementation of our method, we reformulate the Fourier transform of state sequences as recursive form, allowing the auxiliary loss to take the form of a TD error [18], which depends only on the single-step future state. Therefore, SPF is simple to implement and eliminates the requirements for storing infinite-step state sequences when computing the labels of FT. Experiments demonstrate that our method outperforms several state-of-the-arr algorithms in terms of both sample efficiency and performance on six MuJoCo tasks. Additionally, we visualize the fine distinctions between the multi-step future states recovered from our predicted FT and the true states, which indicates that our representation effectively captures the inherent structures of future state sequences.

---

2 Related Work
Learning Predictive Representations in RL. Many existing methods leverage auxiliary tasks that predict single-step future reward or state signals to improve the efficiency of representation learning [2. 5, 19]. However, multi-step future signals inherently contain more valuable features for long-term decision decision-making than sinle-step signals. Recent work has demonstrated the effectiveness of using future reward sequences as supervisory signals improve the generalization performance of visual RL algorithms [9, 10]. Several studies propose making multi-step predictions of state sequences using a one-step dynamic model by repeatedly feeding the prediction back into the learned model, which is applicable to both model-free [11] and model-based [12] RL. However, these approaches require a high degree of accuracy in the one-step model to prevent accumulating errors [13]. To tackle this problem, the existing method learned a prediction model to directly predict multi-step future states [14], which results in significant additional storage for the prediction labels. In our work, we propose to predict the FT of state sequences, which reduces the demand for high prediction accuracy and eliminates the need to store multi-step future states as prediction targets.
Incorporating the Fourier Features. There existing many traditional RL methods to express the Fourier features. Early works have investigated representations based on fixed basis such as Fourier basis to decompose the function into a sum of simpler periodic functions [20, 18]. Another research explored enriching the representational capacity using random Fourier features of the observations. Moreover, in the field of self-super pre-training, neuro2vec [16] conducts representation learning by predicting the Fourier transform of the masked part of the input signal, which is similar to our work but needs to store the entire signal as the label.
3 Preliminaries
3.1 MDP Notation
In RL tasks, the interaction between the environment and the agent is modeled as Markov decision process (MDP). We consider the standard MDP framework [21], in which the environment is given by the tuple M == (S, AA R, P. pt, 7,, where S is the set of states, A is the set of actions, R:S X A S - [- Rmaa] is the reward function, P x A x S - [0, 1] is the transition probability function, μ S + 00, is the initial state distribution, and 7 E [0, 1) is the discount factor. A policy π defines a probability distribution over actions conditioned on the state, i.e. ((ass). The environment starts at an initial state 8e μ.. At time > O, the agent follows policy and selects an action ag ~ T (-))s)). The environment then stochastically transitions to a state $t+1 ~ P(-|s az) and produces reward r, = R(st, de, $t+1). The goal of RL is to select an optimal policy '' that maximizes the cumulative sum of future rewards. Following previous work [22, 231, we define the performance of a policy ı its expected sum of future discounted rewards:
J( == (TM(T.M))
o R(s,, at, $(41)
(I)
where (So, ao $1, a.....) denotes trajectory generated from the interaction process and T ~ MM) indicates that the distribution of r depends on π and the environment model M. For simplicity, we write ((T) and 7 as shorthand since our environment is stationary. We also interest about the discounted future state distribution d",, which is defined by d' (s)) = (1-7) 7
M). It allows to express the expected discounted total reward compactly as
1 Exsa" [R(s, a, s')] 1-7
((T)
(2)
8'>P
The proof of (2) can be found in [24] or Section A.1 in the appendix.
Given that we aim to train an encoder that effectively captures the useful aspects of the environment, we also consider a latent MDP M = (3. R, P. p. 7.), where 3 C RR 2 for finite D and the action space A is shared by M and M. We aim to learn an embedding function & S + S, which connects the state spaces of these two MDPs. We similarly denote म" as the optimal policy in M. For ease of notation, we use (-1ss) == 5 (-16(s)) to represent first using á to map s E S to the latent state space S and subsequently using /े to generate the probability distribution over actions.
3

---

3.2 Discrete- Tieerete-Timeaaeee Fourier Transform
The discrete-time Fourier transform (DTFT) is a powerful way to decompose a time-domain signal into different frequency components. It converts real complex sequence ( into complex-valuee function F(w) -a=-po Fn -jwn, where w is frequency variable. Due to the discrete-time nature of the original signal, the DTFT is 2x-periodic with respect to its frequency variable, i.e., F(w + 2 F(w). Therefore, all of our interest lies in the range E [0, 2T] that contains all the necessary information of the infinite-horizon time series.
It is important to note that the signals considered in this paper, namely state sequences, vealevalued, which ensures the conjugate symmetry property of DTFT, i... F(2x w) = F (w). Therefore, in practice, it suffices predict the DTFT only on the range of [0, 77,, which can reduce the number of parameters and further save storage space.
Structural Information in State Sequences
In this section, we theoretically demonstrate the existence the structural information inherently in the state sequences. We argue that there are two types of sequential dependency structures present in state sequences, which are useful for indicating policy performance and capturing regularity features of the states, respectively.
4.1 Policy Performance Distinction via State Sequences
In the RL setting, it is widely recognized that pursuing the highest reward at each time step in greedy manner does guarantee the maximum long-term benefit. For that reason, RL algorithms optimize the objective of cumulative reward over an episode, rather than the immediate reward, to encourage the agent to make farsighted decisions. This is why previous work has leveraged information about future reward sequences to capture long-term features for stronger representation learning [9].
Compared to the sparse reward signals, we claim that sequential state signals contain richer infor- mation. MDP, the stochasticity of a trajectory derives from random actions selected by the agent and the environment's subsequent transitions to the next state and reward. These two sources of stochasticity are modeled as the policy T (aass) and the transition p(s', r|s, a). respectively. Both of them are conditioned on the current state. Over long interaction periods, the dependencies of action and reward sequences on state sequences become more evident. That is, the sequence of future states largely determines the sequence of actions that the agent selects and further determines the corresponding sequence of rewards, which implies the trend and performance of the current policy, respectively. Thus, state sequences only explicitly contain information about the environment's dynamics model, but also implicitly reveal information about policy performance.
We provide further theoretical justification for the above statement, which shows that the distribution distance between two state sequences obtained from different policies provides an upper bound on the performance difference between those policies, under certain assumptions about the reward function.
Theorem 1. Suppose that the reward function R(s, 8²)") R(s) is related to the state s, then the performance difference between two arbitrary policies πI and To is bounded by the LI norm of the difference between their state sequence distributions:
- S Rmaz 7-
81,82, (TI (1, P(so, 81, 82,... (T22 "2,..../T2,,M M))11
where P(so, 81, $2. ... M) means the joint distribution of the infinitehhorionn state sequence {Sp. $1, S2.... conditioned on the policy n and the environment model M.
The proof of this theorem is provided in Appendix A. The theorem demonstrates that the greater the difference in policy performance, the greater the difference in their corresponding state sequence distributions. When we adjust the ratio Amaa to take a relatively small value by scaling the reward, 1-y the theorem indicates that good and bad policies generate significantly different state sequence distributions. Furthermore, confirms that learning via state sequences can significantly influence the search for policies with good performance.

---

4.2 Asymptotic Periodicity of States in MDP
Many tasks in real scenarios exhibit periodic behavior as the underlying dynamics of the environment are inherently periodic, such as industrial robots, car driving in specific scenarios, and area sweeping tasks, Take the assembly robot as an example, the robot trained to assemble parts together to create a final product. When the robot reaches a stable policy, it executes periodic sequence of movements that allow it to efficiently assemble the parts together. In the case of MuJoCo tasks, the agent also exhibits periodic locomotion when reaching a stable policy. We provide a corresponding video in the supplementary material to show the periodic locomotion of several MuloCo tasks.
Inspired by these cases, we provide some theoretical analysis to demonstrate that, under some assumptions about the transition probability matrices, the state sequences in finite state space may exhibit asymptotically periodic behaviors when the agent reaches a stable policy.
Theorem 2. Suppose that the state spuce S is finite with transition probability matrix P E R|S and has a recurrent classes. Let R1; R2....: :. Ro be the probability submatrices corresponding to the recurrent classes and lef d1, d2,...,dy ,a, be the number of the eigenvalues of modulus that the submatrices R1, Rg....: periodic with period d = lem(d1, d2...., ,d)).
: R2 has. Then for any initial distribution po. P" is asymptotically
The proof of the theorem is provided in Appendix A.2. The above theorem demonstrates that there exist regular and highly-structtred features in the state sequences, which can be used to learn expressive representation. Note that an infinite state space, if the Markov chain contains a recurrent class, then after sufficient number of steps, the state will inevitably enter one of the recurrent classes. In this scenario, the asymptotic periodicity of the state sequences can be also analyzed using the aforementioned theorem. Furthermore, even if the state sequences do not exhibit strictly periodic pattern, regularities still exist within the sequential data that can be extracted as representations to facilitate policy learning.
5
Method
In the previous section, we demonstrate that state sequences contain rich structural information which implicitly indicates the policy performance and regular behavior of states. However, such information is not explicitly shown in state sequences in the time domain. In this section, we describe how to effectively leverage the inherent structural information in time-series data.
5.1 Learning via Frequency Domain of State Sequences
In this part, we will discuss the advantages of leveraging the frequency pattern of state sequences for capturing the inherent structural information above explicitly and efficiently.
Based on the following theorem, we find that the FT of the state sequences preserves the property in the time domain that the distribution difference between state sequences controls the performance difference between the corresponding two policies, but is subject to some stronger assumptions.
Theorem Suppose that S R D the reward function R(s, a, s')) R(s) an nth-degree polynomial function functionn with respect to E S, then for any two policies and T2, their performance difference can be bounded as follows:
VD
[R(0(())) kd
-[T)) S
max ISED
sup 2
(F() Fi (w:) - F(() (wx))
(4)
k=1
",, 525 ..... for any integer where F!! (w) denotes the DTFT of the time series S(#) = (so* $
k E [1 and ((k) means the kth power of the state sequence produced by the policy ा. The dimensionality of the same as s.
We provide the proof in Appendix A.I. Similar to the analysis of Theorem 1, the above theorem shows that state sequences in the frequency domain can indicate the policy performance and can be leveraged to enhance the search for optimal policies. Furthermore, the Fourier transform can decompose the state sequence signal into multiple physically meaningful components. This operator enables the analysis of time-domain signals in a higher dimensional space, making it casier to
5

---

distinguish between two segments of signals that appear similar in the time domain. In addition, periodic signals have distinctive characteristics in their Fourier transforms due their discrete spectra. We provide visualization of the DTFT of the state sequences in Appendix E, which reveals that the DTFT of the periodic state sequence is approximately discrete. This observation suggests that the periodic information of the signal can be explicitly extracted in the frequency domain, particularly for the periodic cases provided by Theorem For non-periodic sequences, some regularity information can still be obtained by the frequency range that the signals carry.
In addition to those advantages, the operation of the Fourier transforms also yields concise auxiliary objective similar to the TD-error loss [18], which we will discuss in detail in the following section.
5.2 Learning Objective of SPF
In this part, we propose our method, State Sequences Prediction via Fourier Transform (SPF), and describe how to utilize the frequency pattern of state sequences to learn an expressive representation. Specifically, our method performs an auxiliary self-supervision task by predicting the discrete-time Fourier transform (DTFT) of infinite-step state sequences to capture the structural information in the state sequences for representation learning, hence improving upon the sample efficiency of learning.
Now we model the auxiliary self-supervision task. Given the current observation 8 and the current action de, define the expectation of future state sequence & over infinite horizon
(7" {> E |Sttn+1|se. 0
0, 0.1,2.... 2, 3...
[ [8(8,, dz)]
n
00 Then the discrete-time Fourier transform of 5c is (w) n= the frequency variable. The discount factor y in (5) is used to ensure the convergence of the Fourier transform and also serves as the contraction factor in the following Theorem 4. Since the state sequences are discrete-time signals, the corresponding DTFT is 2n--eriodic with respect to w. Based on this property, common practice for operational feasibility is compute discrete approximation of the DTFT over one period, by sampling the DTFT at discrete points over [0, 2r]. In practice, we take L equally-spacee samples of the DTFT. Then the prediction target is matrix with size L D, where D is the dimension of the state space. We can derive that the DTFT functions at successive time steps are related to each other in a recursive form:
[ec]n e -J where w represents
(st. dz) = St + Ex.p ([($+11,041))
The detailed derivation and the specific form of 5, and I is provided in Appendix A.3.
Based on the recursive formula (6), between the estimated Fourier value (s,, at) and the better estimate S. 1' Esr.p [F(4 a++1)], just like the TD error. Similar to the TD-learning of value functions, the recursive relationship can be reformulated as contraction mapping T, as shown in the following theorem (see proof in Appendix A.3). Due to the properties of contraction mappings, we can iteratively apply the operator to compute the target DTFT function of long-term state sequences until convergence in tabular settings. When calculating the prediction loss, we only need to utilize the current state 8,, the current action at, and the next state 8 Therefore, one notable advantage of SPF is that there is no need to store multi-step future states as labels for predicting future state sequences.
obtain the prediction loss by computing the difference
S x A + CL+D and define the norm on F as Theorem 4. Let F denote the set of all functions F
|[]|==
sup max
[|[F(s.a)]lllb
sES OSk<L asA
where [F(s, a)], represents the kth row vector of F(s,a), a). We show that the mapping F + F defined as
TF a.) = St T F.p [F(8441 0e41]
is a contraction mapping, where S, and I are defined in Appendix A.3.
As the Fourier transform of the real state signals has the property of conjugate symmetry, we only need to predict the DTFT on half- interval [0, r). Therefore, we reduce the row size of the

---

Critic
Critic Loss
x
Predictor
Projection
F
Famlte
(KFFm))
Prediction Coyen
Target Encoder
Target Fac Rp-s)
Target st/Fa
Sarget 6sA
Target Predictor
Projection
*
#1:1
9,
Target Seei
Figure 2: The network architecture of SPF. The online encoder e outputs the representations used in the RL task and the predictor F predicts complex-values -valudd Fourier transform of the state sequences starting from the state-action pair (st, at). During training, (st. des St+1) are previously experienced states and actions sampled from replay buffer. The dashed line show how gradients flow back to model weights. We prevent the gradient of RI. losses from updating the online encoder and prevent the gradient of prediction loss from updating the target encoder.
prediction target to half for reducing redundant information and saving storage space. In practice, train a parameterized prediction model F to predict the DTFT of state sequences. Note that the value of the prediction target is the complex plane, the prediction network employs two separate output modules FR. and Fim as real and imaginary parts respectively. Then we define the auxiliary prediction loss function
Loped(0, F) d (5, [Ro ($t+1, (81+1)) FimFim ($441, (m441, (8(+1))] Fre FRo(3t. ai)
d ([T Fim (8 n (8)+1)) FieeFiFmmee (8t+1, ((+++)))] Fim ai)):
where s; - ((x)) means the representation of the state, I' and I'mm denote the real and imaginary parts of the constant I' and d denotes an arbitrary similarity measure. We choose d as cosine similarity practice. The algorithm pseudo-code is shown in Appendix B.
5.3 Network Architecture of SPF
Here we provide more details about the network architecture of our method. In addition to the encoder and the predictor, low-dimensional space to prevent overfitting when computing the prediction loss directly from high-dimensional predicted values. In practice, we use loss function called fregloss,, which preserves the low and high-frequency components the predicted DTFT without the dimensionality reduction process (See Appendix C for more details). Furthermore, when computing the target predicted value, we follow prior work [26, 11] to use the target encoder, predictor, and projection for more stable performance. We periodically overwrite the target network parameters with exponential moving average the online network parameters.
projection heads & [25] that project the predicted values onto
In the training process, we train the encoder o the predictor F, and the projection & to minimize the auxiliary prediction loss Cprea (Ø, F, and alternately update the actor-critic models of RL tasks using the trained encoder é. We illustrate the overall architecture of SPF and the gradient flows during training Figure 2.
6 Experiments
We quantitatively evaluate our method on a standard continuous control benchmark-the set of MuJoCo [27] environments implemented OpenAl Gym.
6.1
Comparative Evaluation on MuJoCo
To evaluate the effect of learned representations, we measure the performance of two traditional RI. methods SAC [28] and PPO [29] with raw states, OFENet representations [19], and SPF represen-

---

Table 1: Mean and standard results six MuJoCC tasks at 500K step and 1M step. All means and standard errors are calculated over 10 seeds. The highest mean scores are marked in blue. SPF outperforms other SOTA methods in 5 out of 6 settings with average 19.5% boost.
SAC-SFF
SAC-OFE
PPO-SPF
PPO-OFF
HalfCheetah
12739 + 139 (+7%)
11932 + 75
9004 + 150
2448 + 357 (+1%)
2419 + 296
1476 + 238
500K step
Hopper
3443
(+10%)
123
23/3 +
2923 (+36%)
157
2156 215
Walker2d
4868 + 53 (+299%)
3762 + 162
2023 + 269
1203 + 211 (+415%
339 1: 32
827 - 156
(+17%)
253
696
Swimmer
45 +
45 +
42 =
90 11 (4 13%)
78 = 12
06
Humanoid
4613 118 (+13%)
4071
172
2953 = 136
395 1
405
383
HallCheetah
15822 + 109 (+-10%)
14425 + 112
10745 = 159
3154 + 1358 (+3%)
3066 + 326
2259 +: 344
IM stap
Hopper
(+10%)
147
(+16%)
Walker2d
5158 + 69 (+7%)
4833 + 59
3367
+ 110
2229 + 299
1080 + 236
2202 + 188
Ant
7241 + 85 (+7%)
6738 150
4220
164 4
1053 = 79 (+15%%
913
867
Swimmer
45 +
0
99 (+ (+19%)
73 + 10
83
Humanoid
5633 + L12
6241 = 98
4618 + 118
441 =
448 + 17
439
Walker2d
1o4
HalfCheetah
Hopper
2.75
Evaluation returns
1.50
Evaluation retumns
Evaluation returss
3.00
2.3
0.15
2.50
2.25
0.0
0.5
2.5
0.2
5.5
Steps
106
Steps
Steps
1e5
384
Ant
Swimmer
1+1
Humanoid
1.0
1.4
Evaluation returs
Praluation retumss
Evaluation returns
1.2
2.4
0.2
0.0
0.5
1.0
3.5
2.0
2.5
3.0
0.0
5.5
1.0
1.5
2.5
2.5
3.0
0.5
3.5
Steps
Steps
Stops
SAC-SPF
SAC-OFE
SAC-raw
PPO-SPF
PPO-OFE
PPO
Figure 3: Results on six MuJoCo tasks. The solid curves denote the means and the shaded regions denote the minimum and maximum returns over 10 seeds. Each checkpoint is evaluated by 10 episodes evaluated environments. Curves are smoothed for visual clarity.
tations. We train our representations via the Fourier transform of aefinite-horizon state sequences, which means the representations learn to capture the information of infinite-ster step future states. Hence, we compare our representation with OFENet, which uses the auxiliary task of predicting single- step future states for representation learning. For fair comparison, we use encoder with the same network structure as that OFENet. See Appendix and for more details about network architectures and hyperparameters setting.
As described above, our comparable methods include: 1) SAC-SPE: SAC with SPF representations; 2) SAC-OFE: SAC with OFENet representations; 3) SAC-raw: SAC with raw states; 4) PPO-SPF: PPO with SPF representations: 5) PPO-OFE: PPO with OFENet representations: 6) PPO-raw: PPO with raw states. Figure 3 shows the learning curves of the above methods. As our results suggest, SPF shows superior performance compared the original algorithms. SAC-raw and PPO-raw, across all six MuJoCo tasks and also outperforms OFENet in terms of both sample efficiency and asymptotic performance on five out of six MuloCo tasks. According the results in Table 1, SPF achieves an average gain of +19.5% over other methods at 500K step and 1M step. These results indicate that our approach learns more quickly than other methods when the number of interactions is limited. One possible explanation for the comparatively weaker performance of our method the Humanoid-v2

---

HalfCheetah
HalfCheetah
Eveluation retums
15300
12307
00300
SFF
1.00
0.75
31x2
2302
0.50
Rovi
nutredless
RouiT
0.5
3.2
Staps
2.4
0.0
3.5
Steps
2.0
2.5
2.0
(a)
(b)
Figure 4: Results of additional trials. (a) Ablation study: training curves of five variant methods of SPF on SAC. Each method is evaluated over 5 seeds on HalfCheetah-v2. (b) Comparison of prediction targets: training curves of SAC with different auxiliary prediction tasks. Each method is evaluated over 5 seeds on HalfCheetah-ve -2.. (c) Visualization of recovered states from the predicted DTFT. The blue line represents the true state sequence, while the red line represents the recovered state sequence. The lighter red line corresponds to predictions made by historical states from more distant time step. The four subfigures represent four dimensions of the state space on Walker2d.
task is that its state contains the external forces to bodies, which show limited regularities due to their discontinuous and sparse.
6.2 Ablation Study
In this part, we will verify that just predicting the FT of state sequences may fall short of the expected performance and that using SPF is necessary to get better performance. To this end, we conducted an ablation study to identify the specific components that contribute to the performance improvements achieved by SPF. Figure 4(a) shows the ablation study over SAC with HalfCheetah-v2 environment.
notarg removes all target networks of the encoder, predictor, and projection layer from SPF. Based on the results, the variant of SPF exhibits significantly reduced performance when target estimations in the auxiliary loss are generated by the online encoder without a stopgradient. Therefore, using separate target encoder is vital, which can significantly improve the stability and convergence properties our algorithm.
nofregloss computes the cosine similarity of the projection layer's outputs directly without any special treatment to the low-frequency and high-freuuency components of our predicted DTFT. The reduced convergence rate of nefreqloss suggests that preserving the complete information of low and high-frequency components can encourage the representations to capture more structural information in the frequency domain.
noproj removes the projection layer from SPF and computes the cosine similarity of the predicted values as the objective. The performance did not sigmificantly deteriorate after removing the projection layer, which indicates that the prediction accuracy of state sequences in the frequency domain may not have strong impact on the quality of representation learning. Therefore, it can be inferred that SPF places greater emphasis on capturing the underlying structural information of the state sequences, and is capable of reconstructing the state sequences with low risk of overfitting.
mlp changes the lay block of the encoder from MLP-DenseNet MLP. The much lower scores of mlp indicate that both the raw state and the output of hidden layers contain important information that contributes the quality of the learned representations, This result underscores the importance of leveraging sufficient information for representation learning. mlp-cat uses modified block of MLP the layer of the encoder, which concat the output of MLP with the raw state. The performance of mip-cat does increase compared to mip, but still not as good as SPF in terms of both sample efficiency and performance.
6.3 Comparison of Different Prediction Targets
This section aims to test the effect of our prediction target-infinite-tter state sequences in the frequency domain-on the efficiency of representation learning. We test five types of prediction

---

targets: 1) Stal: single-step future state; 2) StaN: N-step state sequences, where we choose .N =
2. 3, 5; 3) SPF: infinite-step state sequences frequency domain; 4) Rew1: single-step future reward; 5) RewFT: infinite-step reward sequences in frequency domain.
As shown in Figure 4(b), SPF outperforms all other competitors in terms of sample efficieney, which indicates that infinite-step state sequences in the frequency domain contain more underlying valuable information that can facilitate efficient representation learning. Since Stal and SPF outperform Rew and RewFT respectively. it can be referred that learning via states is more effective for representation learning than learning via rewards. Notably, the lower performance of StaN compared to Stal could be attributed to the model's 's tendency to prioritize prediction accuracy over capturing the underlying structured information in the sequential data, which may impede its overall learning efficiency.
6.4 Visualization of Recovered State Sequences
This section aims to demonstrate that the representations learned by SPF effectively capture the structural information contained in infinite-step state sequences. To this end, compare the true state sequences with the states recovered from the predicted DIFT via the inverse DTFT (See Appendix for more implementation details). Figure 4(c) shows that the learned representations the true state sequences even using the historical states that are far from the current time step. In Appendix E, we also provide visualization of the predicted DTFT. which is less accurate than the results in Figure 4(c). Those results highlight the ability of SPF to effectively extract the underlying structural information in infinite-step state sequences without relying high prediction accuracy.
recover
We further provide a comparison table that measures the distance between the real DIFT and the predicted DTFT using cosine similarity. The results provided in Appendix F indicate that the prediction module F exhibits moderate predictive accuracy in approximating the real Fourier transform, with average cosine similarity value of -0.6.
7 Conclusion
In this paper, we theoretically analyzed the existence of structural information in state sequences, which is closely related to policy performance and signal regularity, and then introduced State Sequences Prediction via Fourier Transform (SPF), a representation learning method that predicts the FT of state sequences to extract the underlying structural information in state sequences for learning expressive representations efficiently. SPF outperforms several state-of-the- of both sample efficiency and performance. Our additional experiments and visualization show that SPF encourages representations to place greater emphasis on capturing the underlying pattern of time-series data, rather than pursuing high accuracy of prediction tasks.
algorithms in terms
Limitations One of the main limitations of our paper is that we have only evaluated our method on tasks where the state sequences exhibit strong asymptotic periodicity. Considering that the Fourier transform converts non non-periodic signals into a continuous frequency domain, is more difficult to extract meaningful frequency features of non- non-periodic signals compared to periodic signals that have discrete frequency domain. Moreover, the frequency features extracted by our approach inherently depend on the policy and task, which limits their reusability across multiple tasks. Further research needed to analyze the applicability of our approach to non-periodic tasks and the potential for generalization across multiple tasks.
Acknowledgments
The authors would like thank all the anonymous reviewers for their insightful comments. This work was supported by National Key R&D Program of China under contract 2022ZD01 19801, National Nature Science Foundations of China grants U19B2026, U19B2044, 61836011, 62021001, and 61836006.
References
[1] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Gluman-leve control through deep reinforcement learning. nature, 518(7540):529 533, 2015.
10

---

[2] Tim de Bruin, Jens Kober, Karl Tuyls, and Robert Babuska. Integrating state representation learning into deep reinforcement learning. IEEE Robotics Autom. Lett., 3(2):1994-140.. 2018.
[3] Thomas D. Barrett, William R. Clements, Jakob N. Foerster, and A. I. Lvovsky. Exploratory combinatorial optimization with reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3243-3250, 2020.
[4] Max Jaderberg, Volodymyr Mnih, Wojeiech Marian Czamecki, Tom Schaul, Joel Z. Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. In 5th International Conference on Learning Representations (ICLR), 2017.
[5] Jelle Munk. Jens Kober, and Robert Babuska. Learning state representation for deep actor-critic control. In 55th JEEE Conference on Decision and Control (CDC), pages 4667-4673, 2016.
[6] Amy Zhang, Rowan Thomas McAllister, Roberto Calandra, Yarin Gal, and Sergey Levine. Learning invariant representations for reinforcement learning without reconstruction. In 9th International Conference Learning Representations (ICLR), 2021.
[7] Zhihai Wang, Jie Wang, Qi Zhou, Bin Li, and Houqiang Li. Sample-efficient reinforcement learning via conservative model-based actor-critic. In Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI), pages 8612-8620, 2022.
[8] Zhihai Wang. Taoxing Pan, Qi Zhou, and Jie Wang. Efficient exploration in resource-restricted rein- forcement learning. In Brian Williams, Yiling Chen, and Jennifer Neville, editors, Thirty-Sevent AAAI Conference on Artificial Intelliencce (AAAI), pages 10279-10287, 2023.
[9] Rui Yang. Jie Wang. Zijie Geng, Mingxuan Ye, Shuiwang Ji, Bin Li, and Feng Wu. Learning task- relevant representations for generalization via characteristic functions of reward sequence distributions. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2242-2252, 2022.
[10] Jie Wang, Rui Yang. Zijie Geng, Zhihao Shi, Mingxuan Ye, Qi Zhou, Shuiwang Ji, Bin Li, Yongdong Zhang, and Feng Wu. Generalization visual reinforcement learning with the reward sequence distribution. 2023. doi: 20.48550/r2xi..2222.0000
[11] Max Schwarzer, Ankesh Anand, Rishab Goel, R. Devon Hjelm, Aaron Courville, and Philip Bachman. Data-efficient reinforcement learning with self- predicteee representations. In 9th International Conference on Learning Representations, ICLR, 2021.
[12] Danijar Hafner, Timothy P. Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In Proceedings of the 36th International Conference on Machine Learning([CML), volume 97, pages 2555 1555-2555,115 2019.
[13] Zhaohan Daniel Guo, Bernardo Ávila Pires, Bilal Piot, Cean-Bastien Grill, Florent Altché, Rémi Munos, and Mohammad Gheshlaghi Azar. Bootstrap latent- predit--re representations for multitask reinforcement lcarning. In Proceedings of the 37th Interaational Conference on Machine Learning(/CML), volume 119, pages 3875-3886, 2020.
[14] Nikhil Mishra, Pieter Abbeel, and Igor Mordatch. Prediction and control with temporal segment models. In Proceedings of the 34th International Conference on Machine Learning(/CMI.), volume 70, pages 2459-2468, 2017.
[15] Sungwook Moon and Ahmed Helmy. Understanding periodicity and regularity of nodal encounters in mobile networks: spectral analysis. In Proceedings of the Global Communications Conference. GLOBECOM, pages 1 1-5. JEEE, 2010.
[16] Di Wu, Siyuan Li, Jie Yang, and Mohamad Sawan. neuro2vec: Masked fourier spectrum prediction for neurophysiological representation learning. arXiv preprint w-Xiv:2204.124400 2022.
[17] Anthony Tompkins and Fabio Ramos. Fourier feature approximations for periodic kernels in time-series modelling. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, pages 4155- 4162. AAAI Press, 2018.
[18] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[19] Kei Ota, Tomoaki Oiki, Devesh K. Jha, Toshisada Mariyama, and Daniel Nikovski. Can increasing input dimensionality improve deep reinforcement learning? In Proceedings of the 37th International Conference Machine Learning, ICML, volume 119, pages 7424 2433, 2020.
11

---

[20] Sridhar Mahadevan. Proto-value functions: Developmental reinforcement learning. In Proceedings of the 22nd international conference Machine learning, pages 553-560, 2005.
[21] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley, 1994.
[22] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In Proceedings of the 34th International Conference Machine Learning, volume 70, pages 22-31, 2017.
[23] Ofir Nachum and Mengjiao Yang. Provable representation learning for imitation with contrastive fourier features. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Procexsing Systems 2021. pages 30100-30112, 2021.
[24] Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement leaming. In Machine Learning, Proceedings of Nineteenth International Conference, pages 267-274, 2002.
[25] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning visual representations. Proceedings of the 37th International Conference on Machine Learning, ICML, volume 119, pages 1597-1607, 2020.
[26] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Ávila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent A approach self- supervised learning. volume pages 21271-212844 2020.
[27] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: physics engine for model-based control. In International Conference on Intelligent Robots and Systems, IROS, pages 5026-5033. IEEE, 2012.
[28] Tuomas Haamoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. Proceedings of the 35th International Conference on Machine Learning, ICML, volume 80, pages 1856-1865, 2018.
[29] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, 2017.
[30] Geoffrey Grimmett David Stirzaker. Probability and random processes. Oxford university press, 2020.
[31] Fugene Seneta. Non-negative matrices and Markov chains. Springer Science & Business Media, 2006.
[32] Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. Proceedings of the 35th International Conference on Machine Learning, ICML, volume 80 of Proceedings of Machine Learning Research, pages 1582-1591, 2018
12

---

A Proof
A.1 Proof of Performance Difference Distinction via State Sequences
Following the previous work [22], our analysis will make use of the discounted future state distribution, d", which is defined as
dt (s) = (1-1) -1--) 7) Σ
, P(s, = M)
t=0
It allows us to express the expected discounted total reward compactly as
[ EE [R(st, ae se+ 1
P(s) M))
1=0
/ R 7 P((s M)
(I)
1
Rr (s) ds
1
Eaad" [R(s,a,5)) SPP
(2)
1
where we define (s) := st [ a, s')] should be clear from a ~ (-|ss) and ~ P(-Is, a) that and s depend s. Thus, the reward function R,, is only related to when the policy t is fixed.
Firstly, we prove that the distance between two state sequence distributions obtained from two distinct policies serves as an upper bound on the performance difference between those policies, provided that certain assumptions regarding the reward function hold.
Theorem 1. Suppose that the reward function R(s, 5') R(s) is related to the state s, then the performance difference between two arbitrary policies mi and T2 is bounded by the LI norm of the difference between their state sequence distributions:
Rmax
[[(m)) - J((z) <
1-7 ||P(so: 81,82 M) P(so, 81, 82,... 122 Mill
where P(so, 81, 82, .. | M) means the joint distribution of the infinite-horizon state sequence S = {soo $1, . } conditioned the policy x and the environment model M.
Proof. According to the equation (I), the difference in performance between two policies Ti, T2 can be bounded as follows.
[m(m)) [(T2) Rmax
Σ 7'
P(st
s/TI, P(st 5/T2, M)] ds
t=1
T
Rmax Σ
r'
8t-1, 8141,,..... ,T|
JS
PP 11-1, 8, 8141
87 TT, M) dep ... dd.- ids+1 ... deT ds
R 2
VT
1=
13

---

T
Rmax
?
ST .........
,2| P(so....,37T2) dso dsT
ST++
t=0
Rmax 2
n', AT
1=f+1
R
PSss........ Sy [1, M) P(so ......... ................... T2, ... dsr
1
ST+1
R 2
Σ ,
YT21.
1=++1
Let T + 00, then we obtain the bound proposed by (3).
We are further interested in bounding the performance difference between two policies by their state sequences in the frequency domain. Benefiting from the properties of the discrete-time Fourier transform (DTFT), we can constrain the performance difference using the Fourier transform over the interval [0, 2T), instead of using the distribution functions of the state sequences in unbounded space.
Theorem Suppose that
DR. the reward function R(s, a, 5') R(s) an nth-degree polynomial function with respect E S, then for any two policies and TT, their performance difference can be bounded as follows:
- J(T)) S VD
| (O)lD,
max ISiD
sup w;E[0,2r]
(w(((ws)) - (
(4)
k!
k=
where F.F)(() (w) denotes the DTFT of the time series S(x) = {so k s1 82 .... } for any integer E [1. n] and ((k) means the kth power of the state sequence produced by the policy n. The dimensionality wf is the same as
Proof. For sake of simplicity, we define (s(s)m:) = P(s = M/ for = 1,2. We denote 6 as
R(s (p((sm) pr (2()) ds.
(5)
(
Based the Taylor series expansion, rewrite the reward function as R(s) 2k=o then for any integer E [1, n)). we have
g
( (O)ll
|/
le
<
[5 (s(m(() - sppsss ds
k!
(R())
[O)]l
E s
[
F
[st]
(6)
k!
sropi( (-1mg) (T))
0=
13
Since the inverse DTFT of (1) (w) is the original time series (1k), we have
2x
E 8 s)mpe(-Im)
F*())
(ws)ee dwi, Vi = 1,,,..., D.
(7)
2TT
Then we have
2n
E
[s
E
[sA]]
<
((k) (wx)
((t) F(()((ss)) F7 (wss)
|esturt dww
5, (m)
2T
sup w. e0,
(()((w))) F (wi)
(8)
Substituting (8) into (6), then we obtain
R (0)
|el S VD.
p(h) (w);) F000 (w:))
max sup
k!
IS o (0,2m)
14

---

For the sake of DTFT, the upper bound of é, is independent of then we could derive the performance difference bound as follows.
- J(T22
y |ea
(2 (O))
VD
m (ws) - F (wi)
max Is
sup [;E(0.2a)]
k!
and immediately achieve the desired bound in (4).
A.2 Proof of the Asymptotic Periodicity of States in MDP
This section focuses on analyzing the asymptotic behavior of the state sequences generated from an MDP. We begin by discussing the limiting process of MDP with finite state space S. Let P be the transition probability matrix and let μ4 be the probability distribution the states at time t,. Then we have Mi+1 = Ps. for any 2 0. If the sequence {ur splits into d subsequences with d cyclic limits [1 1-=0 that follow the cycle:
Mox + pi +.......
11 +
then say that the states of the MDP exhibit asymptotic periodicity. Such eyclic asy asymptotic behavior implies that the limiting distribution of the states eventually repeats in specific period after certain number of steps.
We begin by providing some essential definitions in the field stochastic processes [30], which will be utilized in the following proof. Let P be transition probability matrix corresponding
states (n 2 1). Two states and j are said to intercommunicate if there exist paths from to j as well as from j to i. The matrix P is called irreducible if any two states intercommunicate.. A set of states is called irreducible if any two states in the set intercommunicate. Moreover, a state called recurrent if the probability of eventual return having started from is 1, If this probability is strictly less than 1, the state i is called transient.
Note that if the whole state space S is irreducible, then its transition matrix P is also irreducible. The following lemma demonstrates that the state space is irreducible, then its asymptotical periodicity determined by the eigenvalues with modulus of its transition matrix.
Lemma 1. Suppose that the space S is finite with transition probability matrix P E IS If P is an irreducible matrix with d eigenvalues of modulus 1, then for any initial distribution poo pa P"po po is asymptotically periodic with a period of when and asymptotically aperiodic when d.1.
theorem for irreducible non- non-negative matrices, all eigen- values of P of modulus are exactly the d complex roots of the equation A - 1 = 0. They can 253 Each of them is simple
Proof. According to the
be formulated A 1, E-,.... ÀP-1 gd-1, where & root of the characteristic polynomial of the matrix P. Since P is a transition probability matrix, the remaining eigenvalues Ad. A satisfy |^^| < Therefore, the Jordan matrix of has the form
A1
dk
1
J
Ad-1
where Js
Ja
A
Ja.
We refer to J3 as Jordan cells.
Let [S| D, can rewrite P in its Jordan canonical form P= XJX-1 where
X = To. H ,,.,.,, T--
15

---

Note that for k < d, 24 is the eigenvector corresponding to Aष. Since the column vectors of X are
D-1
linearly dependent, there exist č = [co,Cl, CD-II. not all zero, such that po = Σ CgTx = Xc. Thus, we have
k=
D-1
Pd = Σ
C + Σ
(9)
k=0
k=d
For any Jordan cell Jk. ag be the multiplicity of dg. then
X
1p-1
C Cn-ayt X xn-aut
1
C Cn-as +2 aa, x
Jk =
A
A ag X0x
Since ag is fixed for matrix P. we have lim vector (9), denoted by pa Hl. satisfies:
J = 0 for each k = d..... D 1. Then the limiting
n
p p0
lim XJ X x_=X-1Xx- n-
lim
lim mm))
n=020
where we denote p(1)
Σ
ck
2 y I" Letr= n (mod d), then we have
k=0
(()) p00)
Σ ce
vn21.
Therefore, the probability sequence (o"") will split into d converging subsequences and has d cyclic limiting probability distributions when n - co, denoted as
Σ
y Zs.
0, 0.1...... d 1.
Thus, po is asymptotically periodic with period d if d and asymptotically aperiodic d 1.
We now consider more general state space that may not necessarily be irreducible. According to
the Decomposition theorem of the Markov chain [30], the finite state space S can be partitioned
uniquely as set of transient states and one or several irreducible closed sets recurrent states. rewrite
According to [31], after performing appropriate permutation of rows and columns, the transition probability matrix in its canonical form:
R
0
0
0
R2
0
0
P
0
Rw
Ti
T2
Ta
Q
where Ri,..., Ra represent the probability submatrices corresponding the recurrent classes, Q represents the probability submatrix corresponding to the transient states, and T,....,Ty represent the probability submatrices corresponding to the transitions between transient and recurrent classes Ri, Ri respectively.
Theorem 3. Suppose that the state space S is finite with a transition probability matrix P E [SS and has a recurrent classes. Let R1, R2,.... .. Ro be the probability submatrices corresponding to the recurrent classes and let di, d2...., do be the number of the eigenvalues of modulus that the submatrices R1, R2,..., Rs has. Then for any initial distribution po. po is asymptotically periodic with period d = lem d1, d2..... da) when d > 1 and asymptotically aperiodic when d = 1.
16

---

Proof. Since P is block upper-triange triangular, it can be shown that the eigenvalues of P are equal to the union of the eigenvalues of the diagonal blocks Ri...., R2, Q. Note that the nth-power of P satisfies the following expression:
R
0
R2
0
0
pn
R
(n)
T!())
Q"
where ( is related to the (n - 1)-th or the lower power of Rt and Q. From Theorem 4.3 of [31], obtain that lim Q" which implies that all eigenvalues of Q have modulus less than 1.
On the other hand, note that the sum of every row in matrix R, is equal to 1, which means À = is an eigenvalue of R and all eigenvalues of R2 satisfy [^] 1. Thus, the spectral radius of equal to 1.
Note that the proof of Lemma implies that the asymptotic periodicity of Pd no depends the eigenvalues of that have modulus 1. Since R2 is non-negative irreducible with spectral radius 1, based the Perron- Berron-Frobenius theorem used in Lemma modulus as:
express the eigenvalues of R, in
A e² 2n
k == ,. -.......,d-- d
Based the above discussion, it is easy to check that Ü "A,.o...,,,,,,111 is the set of all eigenvalues of modulus of P. Rewrite P in its Jordan canonical form P XJX-1, where
T1,00
11,d--1
A2,0
da
Jdyto
J.
and X = [2,, TD-1] is an invertible matrix. Similar to the proof in Lemma 1, we get
da
p p40 = lim
Ca
2ak dr
m = lim (n)
no+
n-
k=0
Let lcm(d1, .2...., da) and r = n (mod d). then we have
(n) = (r)
Vn 2
Therefore, the probability sequence (P"Mo)n21 will split into d converging subsequences and has d cyclic limiting probability distributions when n + oc, denoted as
d
0,....,dd 1
k=0
Thus, P" Ag is asymptotically periodic with period d if and asymptotically aperiodic if This completes the proof.
17

---

A.3 Proof of the Convergence of Our Auxiliary Loss
In this section, we provide detailed derivation of the learning objective of SPF. As the DTFT of discrete-time state sequences is continuous function that is difficult to compute, we practically sample the DTFT at equally-spaced points.
+.00
F
Σ n==
[Eln e 1. == 1.
(10)
As a result, the prediction target takes the form of matrix with dimensions of L D, where D denotes the dimension of the state space. The auxiliary task is designed to encourage the representation to predict the Fourier transform of the state sequences using the current state-action pair as input. Specifically, we define the prediction target xx (St, az) follows:
L-1
+00
Fa Fa ar) = Fō(ss,
Σ
(3,, arl]n - 27k
(11)
k=0
For simplicity of notation, we substitute F(s,, ax) for (x,,( at) in the following. We can derive that the DTFT functions successive time steps related to each other in recursive form:
toc
[F(s,, az)lı
Σ
Exp, [sctn+1 8r s,a, a] n" e- -
+ - Ep [su+1] St 8,00
Σ nthh e 2 Ep [ ac-1
3o + 7 e - 2uhh
Emp ([ 4++ Mal Vk= 0, 0, L 1
We can further express the above equation as matrix-form recursive formula as follows:
F(st, az) = S, + r Ex, [F(s+11, ac+1)],
(12)
where
S, |[:
[eloo E RLXD
-
e
T=
Similar to the TD-learning of value functions, we can prove that the above recursive relationship (12) be reformulated contraction mapping T. Due the properties of contraction mappings, can iteratively apply the operator T to compute the target DTFT function until convergence in tabular settings.
Theorem 4. Let F denote the set of all functions F A - CL*D and define the F as
|| sup max
[F((s
sES OSkEL
where [F(s, a)] represents the kih row vector of F(s,a). We show that the mapping T F - F defined as
TF(st, un) S, T Fm [F(se11, ((41)
(13)
is contraction mapping, where S, and I' are defined as above.
18

---

Proof. For any F1, F2 E F, we have
||F TF2l = sup max
8 + 7c
(Pi(s',a'] s
SES OSkeL AEA
a'mx))118)
7E 12
EsInP(le()) a'mx(116')
(F(('
S T max sup Osk<L sE aCA
E a'~o)(11')
[Fi(s', (')s',')]{=
[Fa((''
5 max sup 0sk<L j'es
[[[ (5' P2(55''')),,1)
d'EA
- | F2lls.
Note that 7 E [0, 1), which implies that T a contraction mapping.
B
Pseudo-code of SPF
The training procedure of SPF is shown in the pseudo-code as follows:
Algorithm State Sequences Prediction via Fourier Transform (SPF)
Denote parameters of the online encoder (o., &s.a), predictor F, and projection y as Oaux
Denote parameters of the target encoder (Ø.,, &x.a). predictor F, and projection & 0anx Denote parameters of actor model æ and critic model Q for RI agents as 0RL Denote the smoothing coefficient and update interval for target network updates and K Initialize replay buffer and parameters f 3RL for each environment step & do
Gg ~ x( (8))
S1+1, T141 p(.)s),
D t DU (st, ag, $141.
sample minibatch of {(5,, at, $14 1 from D
mmx + 0mx aaux Va.. I (hea(Oouxx (Omux aaxx) resampling minibatch of {(Sr, de, 8141) from D
31 - (x.))
Fec.ac &s (s)))
update the RL agent parameters lRL with the representations 8t, 2 2
update parameters of target networks with 0aux +- 70mux + (1 7 7mnx every K steps
end for
C Network Details
The encoders d. and ds.a share the same architecture. Each layer of the encoders uses MLP- DenseNet [19], a slightly modified version of DenseNet. For each MuJoCo task, the incremental number of hidden units per layer is selected from (30, 40), while the number of layers is selected from {6, 8} (see Table 2). Both the predictor F and the projection & apply 2-layer MLP. We divide the last layer of the predictor into two heads the real part FR and the imaginary part Fim. respectively, since the prediction target of our auxiliary task complex-valued With respect to the projection module, we add an additional 2-layer MLP (referred to Projection2) after the original online projection to perform a dimension-invariann nonlinear transformation on the predicted DTFT that has been projected target projection. This additional step is carried out to prevent the projection from collapsing to a constant value in the where the online and target projections share the same architecture.
dimer-dimensionll space. We do not apply this nonlinear operation the
In Fourier analysis, the low-frequency components the DTFT contain information about the long-term trends of the signal, with higher signal energy, while the high-frequency components of the
19

---

Table 2: Detailed setting of the encoder for six MuJoCo tasks.
Environment
Number of Layers
Number of Units per Layer
Activation Function
HalfChectah-v2
8
30
Swish
Walker2d-v2
Swish
Hopper-v2
6
40
Swish
Ant-v2
Swish
Swimmer-v2
6
40
Swish
Humanoid-v2
Swish
DIFT reflect the amount of short-term variation present in the state sequences. Therefore, attempl to preserve the overall information the low and high-frequency components of the predicted DTFT by directly computing the cosine similarity distance without undergoing the dimensionality reduction process. For the remaining frequency components of the predicted DTFT, we first utilize projection layers to perform dimensionality reduction, followed by calculating the cosine similarity distance. The sum of these three distances is used as the final loss function, which we call freqloss.
D Hyperparameters
Table 3: Hyperparameters of auxiliary prediction tasks.
Hyperparameter
Setting
Optimizer
Adam
Discount
0.99
Learning rate
0.0003
Number of batch size
256
Predictor: Number of hidden layers
Predictor: Number of hidden units per layer
1024
Predictor: Activation function
ReLU
Projection: Number of hidden layers
Projection: Number of hidden units per layer
512
Projection: Activation function
ReLU
Projection2: Number of hidden layers
Projection2: Number of hidden units per layer
512
Projection2: Activation function
ReLU
Number of discrete points for sampling the DTFT L
128
The dimensionality of the output of projection Replay buffer size Pre-training steps
512
100,000
10000
Target smoothing coefficient
0.01
Target update interval K
1000
Hyperparameters of SPF-SAC
Each module: Normalization Layer
BatchNormalization
Random collection steps before pre-training
10,000
Hyperparameters of SPF-PPO
Each module: Normalization Layer
LayerNormalization
Random collection steps before pre-training
4,000
0 update interval K₂
HalfCheetah--2
Walker2d-v2
2
Hopper-v2
150
Ant-v2
150
Swimmer-Ve v2
200
Humanoid-v2 v2
1
20

---

We select L = 128 as the number of discrete points sampled over one period of DTFT. In practice, due to the symmetry conjugate of DTFT. the predictor only predicts 1/2 + points on the left half of our frequency map, as mentioned in Section 5.2. The projection module described in Section 5.3 projects the predicted value, a matrix with the dimension of I. * D. into 512-dimensional vector. To update target networks, we overwrite the target network parameters with an exponential moving average of the online network parameters, with a smoothing coefficient of = 0.01 for every = 1000 steps.
In order to eliminate dependency on the initial parameters of the policy, we use a random policy to collect transitions into the replay buffer [32] for the first 10K time steps for SAC, and 4K time steps for PPO. We also pretrain the representations with the aforementioned random collected samples to stabilize inputs to each RL algorithm, as described in [19].
The network architectures, optimizers, and hyperparameters of SAC and PPO are the same as those used in their original papers, except that we use mini-batches of size 256 instead of 100. As for PPO, we perform K₂ gradient updates of Oax for every K2 steps of data sampling. The update interval K₂ set differently for six MuJoCo tasks and can be found in Table 3.
E
Visualization
To demonstrate that the representations learned by SPF effectively capture the structural information contained in infinite-step state sequences, we compare the true state sequences with the states recovered from the predicted DTFT via the inverse DTFT.
Specifically, we first generate a state sequence from the trained policy and select a goal state 8, at certain time step. Next, we choose historical state st-k located k steps past the goal state and select an action a based on the trained policy xt (-[ss=k) as the inputs of our trained predictor. We then obtain the DTFT Fi-k == Fx (S:-A: 0e-k) of state sequences starting from the state S Next, we compute the kth element of the inverse DTFT of Fi-& and obtain a recovered state $,, which represents that we predict the future goal state using the historical state located k steps past the goal state. By selecting a sequence of states over a specific time interval as the goal states and repeating the aforementioned procedures, we will obtain a state sequence recovered by k-step prediction. In Figure 5(b), 6(b), 7(b), 8(b), 9(b) and 10(b), we visualize the true state sequence (the blue line) and the recovered state sequences (the red lines) via k-step predictions for k = 1, 2, 3, 4, 5. Note that the lighter red line corresponds to predictions made by historical states from more distant time step. We conduct the visualization experiment predictors trained by SPF-SAC or SPF-PPO. Due to the large dimensionality of the states in Ant-v2 and Humanoid-v2, which contain many zero values, we have chosen to visualize only six dimensions of their states, respectively. The fine distinctions between the true state sequences and the recovered state sequences from trained representations and predicted FT indicates that our representation effectively captures the inherent structures of future state sequences.
six MuJoCo tasks using the representations and
Furthermore, we provide a visualization that compares the true DTFT and the predicted DTFT in Figure 5(a), 6(a), 7(a), 8(a), 9() and 10(a). To accomplish this, we use our trained policies to interact with the environments and select the state sequences of the 200 last steps of an episode. The blue lines represent the true DTFT of these state sequences, while the orange line represents the predicted DIFT using the online encoder and predictor trained by learned policies. is evident that the true DTFT and the predicted DTFT exhibit significant differences. These results demonstrate the ability of SPF to effectively extract the underlying structural information in infinite-step state sequences without relying on high prediction accuracy.
F
Cosine Similarity Results
We present a comparison table between the real discrete-time Fourier transform (DTFT) and the predicted DTFT. To obtain these results, we use our trained policies to interact with six MuJoCo environments and record the states and the actions for the 201 last steps of an episode, denoted as {st 200 and {ae |200 respectively. The real DTFT of the state sequence ($1, $ $200] over a 200-step horizon is computed using the formulation of the discrete-time Fourier transform. For the predicted DTFT, we employ our trained encoder and prediction module, with the state and the action dg serving as inputs. The output of the prediction module represents the predicted DTFT of the state sequence ($1, 82 ..... $200 }. We compute the cosine similarity between A and B with the
21

---

formula-
A-B || where values closer to -1 indicate greater similarity while the values closer to 1 indicate greater dissimilarity. The cosine similarity between the real DTFT and the predicted DTFT listed in Table 4 below.
Table 4: Cosine similarity distance between the real DTFT and the predicted DTFT.
Environment
Cosine similarity distance
HalfCheetah
-0.655
Hopper
-0.600
Walker2d
-0.651
Ant
-0.351
Swimmer
-0.557
Humanoid
-0.651
G Code
Codes for the proposed method are available at httrgs///gtthub..ca//AAALLa
cww www./MMAwaab....................
http://IRAAa--ST/R------0- USTC/RL-SPF/
MERER STARAS
PaRCheset MANCl rodes
(a) True and predicted DTFT
(b) True and recovered state sequences
Figure 5: Predicted values via representations trained by SPF-SAC on HalfCheetah-vV) -2
22

---

COMER
Wata GUONES
Watar MENAE moade
(a) Truc and predicted DTFT
(b) True and recovered state sequences
Figure 6: Predicted values via representations trained by SPF-SAC on Walker2d-v2
PETANOD MA0000 IT modd
(a) True and predicted DTFT
(b) True and recovered state sequences
Figure 7: Predicted values via representations trained by SPF-SAC Humanoid-v2
23

---

Hoppack CEON
HALAONINN
(a) Truc and predicted DTFT
(b) True and recovered state sequences
Figure 8: Predicted values via representations trained by SPF-PPO on Hopper-v2
(a) True and predicted DTFT
(b) True and recovered state sequences
Figure 9: Predicted values via representations trained by SPF-PPO on Ant-v2
SWIDOICC SOONG modee
JON PAO
200
JON
Seleract
(a) True and predicted DTFT
(b) True and recovered state sequences
Figure 10: Predicted values via representations trained by SPF-PPO on Swimmer-v2
24


Reviews:
[{"review_id": "Z0FgRooDqj", "reviewer": "Reviewer_1q5C", "summary": "The paper suggests a representation learning method that leverages the existing periodic structures in the state sequences of a policy. Specifically, they propose using the features obtained by the Fourier transform of the state sequence. To practically extract such features, they employ a Bellman equation-like recursive form of the Fourier transform (FT), which enables efficient online learning. The authors demonstrate that their representation learning method helps improve the performances of SAC and PPO in Gym MuJoCo environments.", "questions": "- Can the authors elaborate on why Fourier features are useful for representations? For example, let's say a state sequence from a policy forms a perfect sinusoidal curve so that its Fourier transform collapses to a single point. In such a case, its Fourier representation (which is a constant) may not contain sufficient information for control (i.e., for producing optimal actions to maintain that sinusoidal curve).\n- Could SPF be harmful in tasks that do not have periodicity? Have the authors tested SPF on such environments/tasks?\n", "limitations": "The authors briefly mention the limitations of SPF in Section 7. However, it would be also important to include a discussion on the second question above in the limitation section as well.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The idea of using frequency features in sequential decision-making problems seems novel and sensible, given that real-world tasks often inherently have periodic (sub-)structures in their states (e.g., robotic locomotion).\n- The recursive objective in Equation (7), which enables learning Fourier features in practice without the need to deal with the entire state sequences, is intriguing and potentially inspirational for future research.\n- The paper includes an informative ablation study.", "weaknesses": "- The Fourier features inherently depend on the policy and task, making them less reusable for multiple tasks, especially compared to previous self-supervised representation learning methods.\n- The theorems in the paper do not necessarily explain why Fourier features could be potentially useful for *representations*. Theorem 3 states a (very crude) bound for the performance difference between two policies expressed in the frequency domain. However, it is unclear as to why the features extracted in this manner are useful or sufficient for modeling policies/value functions as well, which is the way SPF utilizes the learned features. I would have expected a theorem that says the sub-optimality of using the learned Fourier representation decreases as the state sequence shows stronger periodicity.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n**Figure S1 and Table S1 in this response refer to the pdf attached in the global response.**\n\n**Q1. Could SPF be harmful in tasks that do not have periodicity? Have the authors tested SPF on such tasks?**\n\n**A1.** \n+ **We claim that SPF shows favorable performance even in tasks lacking periodicity.** By analyzing the Fourier Transform (FT), we can identify the dominant frequencies and their corresponding magnitudes, revealing the periodic patterns or oscillatory behavior within the time-horizon state sequences. Furthermore, the Fourier Transform enables the identification of transient phenomena, such as irregular sudden changes, which may be reflected in the frequency domain as high-frequency components.\n\n+ We further test SPF on complex dexterous manipulation tasks, **the Adroit benchmarks** [1], which **do not have clear periodicity due to the randomized position of the manipulated target** (such as the door in the AdoritHandDoor task). In Table S1 and Figure S1(b) of **the attached pdf in 'global' response**, we report that for **Adroit tasks**, SPF achieves **a 1494% and 330% boost on average** compared to OFE at 1M and 2M interaction steps, respectively.\n\n  For your convenience, we quote the **Adroit-1M** section of Table S1 below.\n\n| Adroit-1M      | SAC-SPF  | SAC-OFE | PPO-SPF  | PPO-OFE |\n| - | - | - | - | - |\n| AdroitHandDoor | **4420** | 1162    | -56      | -58     |\n| AdroitHandPen  | **960**  | -547    | **1453** | -253    |\n\n**Q2. A theorem that says the sub-optimality of using the learned Fourier representation decreases as the state sequence shows stronger periodicity is expected.**\n\n**A2.** \n+ We provide **a sub-optimality performance bound for the latent policy using the learned Fourier representation** as follows:\n\n  *Suppose that $\\mathcal{S}\\subset\\mathbb{R}^D$ the reward function $R(s,a,s')=R(s)$ is a linear function with respect to $s\\in \\mathcal{S}$. Then the performance difference between the optimal policy* $\\pi^*$ *and the latent policy* $\\overline{\\pi}\\circ \\phi $ *may be bounded as:*\n  $$\n  |J(\\pi^*)-J(\\overline{\\pi}\\circ\\Phi)|\\leq \\frac{\\sqrt{D}\\cdot R_\\text{max}}{(1-\\gamma)^2}\\cdot E_{(s,a,s')\\sim\\mathcal{D}}\\left[\\overline{\\delta}_{\\overline{\\pi}\\circ\\phi }(s,a,s')\\right],\n  $$\n\n  *where $\\overline{\\delta}_\\pi(s,a,s'):=s'+e^{-j\\omega}\\gamma E\\_{a'\\sim{\\pi}}\\left[F\\_{\\pi}(s',a')\\right] - F\\_{\\pi}(s,a)$ is the minimized objective of SPF.*\n\n  **We provide detailed proof in the 'global' response.**\n\n+ Based on the above theorem, the performance gap between the optimal policy and our learned policy decreases when we minimize the auxiliary loss function $\\overline{\\delta}_\\pi(s,a,s')$, even in cases where the state sequence does not exhibit strong periodicity. The above theorem indicates that **leveraging Fourier spectrum information via the objective of SPF is useful for the agent to approach the optimal policy.**\n\n+ However, **it has benefits when the state sequence shows stronger periodicity.** In such scenarios, the FT of the state sequence approaches discreteness, which reduces errors introduced during algorithm implementation. This is because, in practice, we can only estimate the values of Fourier functions from discrete sampling points.\n\n\n\n**Q3. Why are Fourier features useful for representations?**\n\n**A3.** \n+ The inverse Fourier Transform allows us to convert the frequency domain back into the time domain. When given a single frequency $\\omega$, we can express the sinusoidal function as $\\sin(\\omega x)$ (if we do not consider the amplitude and phase factors). \n\n+ In the case of a perfect sinusoidal curve, as the representation learns a Fourier function on the interval of $[0,2\\pi]$,  it may discover that there exists a single frequency $\\omega$ on $[0,2\\pi]$, and **all values outside the point (that is, $[0,2\\pi]\\setminus \\\\{\\omega\\\\}$) are zero**. Then the representation captures the presence of the perfect sinusoidal function.\n\n \n\n**Q4. More discussion for limitations.**\n\n**A4.** Thank you for pointing out this. One of the main limitations of our paper is the absence of an analysis regarding the performance of our method on tasks that lack periodicity. In the revised version, we will thoroughly analyze the applicability of our approach to non-periodic tasks. Additionally, we will investigate its ability to identify irregular changes in time-series data. \n\n\n\n[1]. Rajeswaran A, et al. \"Learning complex dexterous manipulation with deep reinforcement learning and demonstrations.\" RSS, 2018."}, {"review_id": "lCYipICUCD", "reviewer": "Reviewer_ov12", "summary": "Unlike many prior model-based RL methods that predict one future state at a time, the authors present a Fourier-transform based approach that predicts future states over a fixed interval. They prove that a large difference in policy performance will cause a significant difference between the experienced states of a good and bad policy. This conclusion is important for utilizing frequency-space analysis of the states.\n\nTheir approach uses a self-supervised learning objective where they attempt to fit an online encoder given the current states, and a target encoder given the next states. Note that both the online and target encoder, given a single state, will predict frequencies for the rest of the trajectory. This is in contrast to prior methods that will just compute the next state. The TD-like error between predictions is then used to train the online encoder. I'm not sure I fully understand it, but it seems quite elegant in that their approach closely resembles the one-step TD error. As far as I can tell, they are not actually using the predicted state sequences for planning, as in model-based RL. Rather, they are learning the features necessary to predict future state sequences. These features are useful for a downstream policy.\n\nThey evaluate their method on the standard MuJoCo/Gym benchmarks which outperforms baselines. They compare their method using SAC/PPO to SAC/PPO using OFE or no prediction at all. They continue to ablate nearly all portions of their approach.", "questions": "- \"Therefore, state sequences maximally preserve the influence of the transition intrinsic to the environment and the effect of actions generated from the current policy\"\n    - I'd be careful saying this. In the case of a deterministic policy, yes. But if you add stochasticity (e.g. epsilon greedy or policy-gradient sampling) I'm not sure you can claim you can predict a future state sequence. You can perhaps predict the distribution of states.\n- \"it is widely accepted that the frequency domain shows the regularity properties of the time-series data\"\n    - There are citations for this but I find it a bit hard to believe. For cyclical processes this makes sense, but there is no guarantee, for example, that you will see a specific feature every k timesteps. Could you add an intuitive explanation of why this should work for latent state sequences?\n    - This is explained later in the paper, but perhaps it makes sense to say you show/prove this in the introduction\n- Eq. 5: Why do you discount the future state using gamma? I understand dicounting the reward/return, but not effectively \"decaying\" the future state. Could you briefly explain the reasoning here? Is it to weight nearby states more heavily?", "limitations": "- The authors do not list any limitations", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is very well written\n- Their approach is novel and elegant\n- Their experiments, specifically the ablation, is well-done\n- They show their approach outperforms baselines", "weaknesses": "- They only compared to one other feature-learning algorithm. It would be beneficial to have additional baselines.\n- Unless I'm misunderstanding, it seems like they've purposely limited the applications of their approach to fully observable, model-free RL\n    - They already predict future states, they might as do some online planning\n    - This could be applied to partially observable domains to learn Markov states\n- They do not list any limitations of their approach", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n**Figure S2 and Table S3 in this response refer to the pdf attached in the global response.**\n\n**Q1. Additional baselines.**\n\n**A1. We further compare our method (SPF) with an additional baseline D2RL [1]**, which explores an effective architectural of deeper networks and dense connections for representation learning. The evaluation data of D2RL on state-based RL tasks is sourced from the 'Deeper_Larger_Actor-Critic_RL' repository on GitHub. In Table S3 of the added pdf, we report that for **five MuJoCo tasks**, SPF achieves **a 39% and 18% boost on average** compared to the other baselines at 500k and 1M interaction steps, respectively.\n\nFor your convenience, we quote the **MuJoCo-1M** section of Table S3 below.\n\n| MuJoCo-1M   | SAC-SPF   | SAC-OFE  | SAC-D2RL | PPO-SPF  | PPO-OFE | PPO-D2RL |\n| - | - | - | - | - | - | - |\n| HalfCheetah | **15822** | 14425    | 12932    | **3154** | 3066    | 1592     |\n| Hopper      | **3517**  | 3197     | 3247     | **3152** | 2370    | 1698     |\n| Walker2d    | **5158**  | 4833     | 5075     | **2229** | 1080    | 1596     |\n| Ant         | **7241**  | 6738     | 5385     | **1053** | 913     | 236      |\n| Humanoid    | 5633      | **6241** | 5073     | 441      | **448** | 413      |\n\n**Q2. Apply their approach to partially observable domains to learn Markov states.**\n\n**A2. We extend the evaluation of SPF to partially observable domains** by introducing standard Gaussian noises to substitute several dimensions of the input states. Specifically, we mask 2 and 3 dimensions of states and evaluate the performance of our method in comparison to other baselines on **Walker2d task**, which is one of the MuJoCo tasks. Figure S2(b) of the added pdf in 'global' response demonstrates the superiority of our method over OFE and raw RL algorithms.\n\n\n\n**Q3. They might as do some online planning.**\n\n**A3.** It is possible to apply SPF to online planning by planning through the predicted state sequences. For instance, in the AdroitHandDoor task, where we aim to teach a robotic arm to open a door. The Fourier functions of the state sequences predicted by SPF can be recovered to obtain the original state sequences using the inverse Fourier Transform. This enables us to extract the physical parameters of the robotic arm and the coordinates of the door handle from the states. Subsequently, optimization or heuristic methods can be employed to generate a path for the robotic arm to reach the door handle.\n\n\n\n**Q4. Lack of limitations.**\n\n**A4.** Thank you for pointing out this. \n\n+ One of the main limitations of our paper is the absence of an analysis regarding the performance of our method on tasks that lack periodicity. In the revised version, we will thoroughly analyze the applicability of our approach to non-periodic tasks. Additionally, we will investigate its ability to identify irregular changes in time-series data. \n+ Another limitation of our study is that we did not extend our proposed method to visual-based RL settings, where frequency domain transformations of images have shown promise for noise filtering and feature extraction. \n\n\n\n**Q5. If you add stochasticity, I'm not sure you can claim you can predict a future state sequence.**\n\n**A5.** In theoretical analysis, we model the state sequences as the expectation of state sequences with respect to a stochastic policy (refer to Equation (5)). Hence, in theory, we account for the inherent randomness associated with the policy. In practical implementation, we optimize the objective function$\\overline{\\delta}_\\pi(s,a,s'):=s'+e^{-j\\omega}\\gamma E\\_{a'\\sim{\\pi}}\\left[F\\_{\\pi}(s',a')\\right] - F\\_{\\pi}(s,a)$. Note that the selection of the next action $a'$ is based on the current policy $\\pi$, which implies that the prediction of the Fourier Transform incorporates the stochasticity of the policy.\n\n\n\n**Q6. Why this should work for latent state sequences ?**\n\n**A6.** Thank you for bringing this to our attention. **The learned Fourier feature may contain frequency information about the future state sequences, but it does not imply that the feature itself possesses periodic properties.** For example, we assume that each state corresponds to one latent state, and it is possible for multiple states to correspond to the same latent state, which we refer to as an equivalence class consisting of these states.  Consequently, the periodicity of the latent states may be determined by the least common multiple of the states within the corresponding equivalence class. This situation potentially disrupts the inherent periodicity of the latent states.\n\n\n\n**Q7. About Equation (5).**\n\n\n**A7.** Since we consider the infinite state sequences, it is necessary to keep the Fourier series remains bounded or converges to a finite value. And the discounted rate for state sequences can ensure the recursive operator $\\mathcal{T}$ in Equation (7) a contraction mapping, which guarantees the convergence to the true FT function in tabular settings when using our auxiliary loss. This modeling approach has been used in prior works [2], which allows us to compactly express the difference in performance between two policies.\n\n\n\n[1] D2rl: Deep dense architectures in reinforcement learning. arXiv preprint, 2020.\n\n[2] Achiam J, et al. Constrained policy optimization, ICML 2017."}, {"review_id": "ivniB7dd99", "reviewer": "Reviewer_KaZ7", "summary": "Data-efficient RL exploits representation learning which learns representations by predicting long-term future states. However, inherent structural information in sequential state signals is ignored in existing methods. The authors propose SPF which exploits the frequency domain of state sequences. The proposed method performs an auxiliary self-supervision task to improve the efficiency of representation learning. This method outperforms several state-of-the-art algorithms in terms of both sample efficiency and performance.", "questions": "* What is inherent structural information we can get from Fourier-transform? \n\n* The main concern is that results do not outperform the baseline. Also, in 6.3, the results of all the baselines and SPF are comparable.\n\n====================================================================================================\n\n\nThe authors successfully handle my concerns. I raise my score to borderline accept. ", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 1, "presentation": 2, "contribution": 2, "strengths": "* Notations are clear and methods are clearly proposed.\n", "weaknesses": "* Results are not promising compared to SAC-OFE. In Humanoid, SAC-OFE outperforms SAC-SPF, and in HalfCheetah, Walker2d, Ant, Swimmer, SAC-OFE is comparable to SAC-SPF.\n* I could not find critical superior points to use Fourier transform. As the authors pointed out in the conclusion, experiments on visual-based RL settings are required to show the benefits of the Fourier transform.\n* The inherent structural information in a sequential state is not clearly discussed in the paper.\n\n\n**Minors**\n* Typo in Figure2, There is no predictor F in the figure.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score（\"3: Reject\"). If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n**Figures S1, S2, and Tables S1, S2 in this response refer to the pdf attached in the global response.**\n\n\n**Q1. Results are not promising compared to SAC-OFE.**\n\n**A1.**\n+ **Our method (SPF) learns more quickly than OFE and significantly outperforms OFE by a large margin when the number of interactions is limited.** It is particularly important when we train the agent under a constrained budget for interactions, which can be costly. In Table S1 and Figure S1(a) of **the attached pdf**, we report that for **MuJoCo tasks**, SPF achieves **a 39% and 18% boost on average** compared to OFE at 500k and 1M interaction steps, respectively.\n\n+ **We conduct experiments to test our method (SPF) on complex dexterous manipulation tasks, the Adroit benchmark [1].** The Adroit tasks are difficult to solve effectively due to their high dimensionality, which provides an opportunity to highlight the advantage of SPF in representation learning. In Table S1 and Figure S1(b) of the pdf, we report that for **Adroit tasks**, SPF achieves **a 1494% and 330% boost on average** compared to OFE at 1M and 2M interaction steps, respectively.\n\n  For your convenience, we quote the **Adroit-1M** section of Table S1 below.\n\n| Adroit-1M      | SAC-SPF  | SAC-OFE | PPO-SPF  | PPO-OFE |\n| - | - | - | - | - |\n| AdroitHandDoor | **4420** | 1162    | -56      | -58     |\n| AdroitHandPen  | **960**  | -547    | **1453** | -253    |\n\n**Q2. Results in Figure 6.3 are comparable.**\n\n**A2. Our method (SPF) learns more quickly than the other baselines and significantly outperforms other baselines when the number of interactions is limited.** Figure S2(a) in the added pdf displays the learning curves on HalfCheetah and Walker2d tasks for the initial 1M interaction steps, providing evidence of SPF's improved performance in terms of sample efficiency.\n\n**Q3. Experiments on visual-based RL to show the benefits of the FT**.\n\n**A3. We extend the evaluation of SPF to the visual-based RL setting** using DeepMind Control Suite (DMC), a popular benchmark for visual-based RL.  We build our representation learning method (SPF) on DrQ [2], an existing visual RL approach that improves SAC with image augmentation. We then compare the performance of DrQ+SPF against the original DrQ on DMC. We use a mini-batch size of $128$ and an action repeat of $4$ to accelerate the training speed. In Table S2 of the pdf, we report that for the **Finger-spin and Walker-walk tasks**, DrQ+SPF achieves **a 2% and 25% boost on average** compared to the original DrQ at 100k and 500k interaction steps, respectively.\n\nFor your convenience, we quote the **DMC-500k** section of Table S2 below.\n\n| DMC-500k | DrQ+SPF | DrQ  |\n| - | - | - |\n| Finger spin | **728** | 543 |\n| Walker walk | **860** | 743 |\n\n**Q4. The critical superior points of using FT.**\n\n**A4.**\n+ Intuitively, we train the encoder by predicting the Fourier Transform (FT) of state sequences to **extract the periodic patterns exhibited by state sequences in the long run, which are valuable for long-term decision-making RL tasks**. In Theorem 2, we show the widespread existence of asymptotically periodic behaviors in a Markov chain, where we can fully exploit the potential of FT to extract the regularity information.\n\n+ The formulation of Discrete-Time FT (DTFT) offers **an elegant prediction loss in the form of TD error** (See Equation (6) and equation on Line 261). The TD-style loss makes SPF **easy to implement and eliminates the need to store multi-step future states as labels for predicting future state sequences.**\n+ **The FT of state sequences preserves the state sequence's ability to reflect the performance of the current policy.** Theorems 1 and 3 provide theoretical evidence for the relationship between policy performance and state sequences in the time and frequency domains, respectively.\n\n**Q5. What is inherent structural information we can get from FT?**\n\n**A5.** In our paper, the two types of structural information mean **the policy performance information reflected by state sequences** and **the regularity information inherent in state sequences**. We provide detailed explanations as follows.\n\n+ The first information refers to the dependency between reward sequences and state sequences shown in Figure 1 of the main text, where the state sequences implicitly reflect the performance of the current policy (i.e. the discounted sum of a reward sequence) and exhibit significant differences under good and bad policies (Theorem 1). Theorem 3 showd that the FT of state sequences preserves a similar property related to policy performance, which means we can get information of policy performance from the FT of state sequences.\n+ The second information refers to the temporal dependencies in a state sequence, namely the regularity patterns exhibited by the state sequence (showed in Theorem 2 and visualized in Figures 5-9 of the Appendix). By analyzing the FT, we can identify the dominant frequencies of the time-horizon state sequences, which reveal the periodic patterns within the state sequences. In Figure 4(c) of the main text, we demonstrate that the representations learned by SPF effectively capture such regularity information in state sequences.\n\n**Q6. Typo in Figure 2.**\n\n**A6.** Thank you for pointing out this typo. In Figure 2 of the main text, the letter $\\mathcal{P}$ should be $\\mathcal{F}$.\n\n\n\n[1] Learning complex dexterous manipulation with deep reinforcement learning and demonstrations.  RSS, 2018.\n\n[2]  Image augmentation is all you need: Regularizing deep reinforcement learning from pixels. ICLR, 2021."}, {"review_id": "AgL5fT8mkd", "reviewer": "Reviewer_i4e2", "summary": "The authors in this paper investigated the structural information in state sequences for reinforcement learning, and proposed the prediction of Fourier transformation for the input sequences, which is further used an auxiliary task for learning policies. Some theoritical results are provided to show the existence of structual information. Experimental results on MuJoKo tasks demonstrated the promise of the proposed method.\n", "questions": "1. Some notations in Figure 2 are not defined (e.g., $P$) and cannot be located from the definition of the prediction loss (e.g., $\\mathcal{F}$) between L261 and L262.\n\n2. What does $\\Gamma_{Re}$ do in the prediction loss, given that $\\mathcal{F}_{Re}$ is already real? ", "limitations": "Yes, the authors mentioned that the current version may not handle the image inputs.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The idea of performing prediction on the Fourier spectrum is interesting. This approach may better extract information hidden in the time domain, which constitutes the main contribution of this paper.\n\n2. From the experimental results, the proposed auxiliary task indeed helped learn better policies for RL agents, w.r.t. both SAC and PPO.", "weaknesses": "1. There seems to be a gap between the motivation and the implementation. The introduction and some theoretical results, e.g., Theorem 3, imply that the prediciton is on the Fourier domain; however, the algorithm (SPF) simply used a parameterized prediction module. Consequently, it's unclear to me whether the proposed algorithm can extract the information in the Fourier spectrum.\n\n2. It's unclear to me whether the proposed method can capture the long-term information. From Figure 2, it only considers two adjacent states as inputs.\n\n3. The significance in Theorem 1 may not be sufficient, as the upper bound can be loose. Note that the use of l1 norm for the difference between two distributions will make the term in Equation (3) much greater than 1. Furthermore, it's unclear whether the states distributions for two policies can vary that much, given the use of Rmax / (1 - \\gamma).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive and insightful comments. We respond to each comment as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n**Q1. The gap between the motivation and the implementation.** \n\n**A1.** \n+ To narrow the gap between the motivation and the implementation, we provide **a sub-optimality performance bound for the latent policy using the learned Fourier representation** as follows:\n\n  *Suppose that $\\mathcal{S}\\subset\\mathbb{R}^D$ the reward function $R(s,a,s')=R(s)$ is a linear function with respect to $s\\in \\mathcal{S}$. Then the performance difference between the optimal policy* $\\pi^*$ *and the latent policy* $\\overline{\\pi}\\circ \\phi $ *may be bounded as:*\n  $$\n  |J(\\pi^*)-J(\\overline{\\pi}\\circ\\Phi)|\\leq \\frac{\\sqrt{D}\\cdot R_\\text{max}}{(1-\\gamma)^2}\\cdot E_{(s,a,s')\\sim\\mathcal{D}}\\left[\\overline{\\delta}_{\\overline{\\pi}\\circ\\phi }(s,a,s')\\right],\n  $$\n  \n  *where $\\overline{\\delta}_\\pi(s,a,s'):=s'+e^{-j\\omega}\\gamma E\\_{a'\\sim{\\pi}}\\left[F\\_{\\pi}(s',a')\\right] - F\\_{\\pi}(s,a)$ is the minimized objective of SPF.*\n  \n  **We provide detailed proof in the 'global' response.**\n\n+ Based on the above theorem, the performance difference between the optimal policy and our learned policy using Fourier representation decreases when we minimize the representation learning objective of SPF (Line 261 in our paper). This indicates that leveraging Fourier spectrum information for representation learning aids the agent in learning the optimal policy.\n\n+ In practice, we use the predictor module $\\mathcal{F}$ to estimate the Fourier Transform (FT) of the state sequence $F_{\\pi}$ with the latent state $\\phi(s)$ and action $a$ as input. Thus, we rewrite the objective as\n\n  $$\n  \\overline{\\delta}_\\pi(s,a,s'):=s'+e^{-j\\omega}\\gamma E\\_{a'\\sim{\\pi}}\\left[\\mathcal{F}(\\phi(s'),a')\\right] - \\mathcal{F}(\\phi(s),a).\n  $$\n\n+ Note that we use the objective $\\overline{\\delta}_\\pi(s,a,s')$ to **update the encoder $\\phi$ and the predictor $\\mathcal{F}$ simultaneously**. Thus, the information in the Fourier spectrum of state sequences is propagated to the encoder when minimizing the objective of SPF.\n\n\n\n**Q2. Explanation for Figure 2.**\n\n**A2.** \n+ Thank you for pointing out this typo. We apologize for any inconvenience or confusion this may have caused. In Figure 2 of the main text, the letter $\\mathcal{P}$ (including $\\mathcal{P}\\_\\text{Re}$ and $ \\mathcal{P}\\_{\\text{Im}}$) should be $\\mathcal{F}$ (also $\\mathcal{F}\\_{\\text{Re}}$ and $\\mathcal{F}\\_{\\text{Im}}$), which denotes the predictor.\n\n+ **The prediction loss in Figure 2 corresponds to the objective $\\overline{\\delta}$ mentioned in A1 of this response.** It is derived from the recursive form of the FT of state sequences (See Equation (6)), and it can be expressed as the difference between the estimated Fourier value of $F_{\\pi}(s,a)$ and the better estimate $s'+e^{-j\\omega}\\gamma E_{a'\\sim{\\pi}}\\left[F_{\\pi}(s',a')\\right]$, just like the TD error. **When calculating the prediction loss, we only need to utilize the current state, the current action, and the next state**. Thus, one of the advantages of SPF is without the need to store multi-step future states as labels for predicting future state sequences.\n\n+ Similar to how the classic RL algorithms use TD error to update the $Q(s,a)$ function for estimating the sum of future rewards, **our prediction loss enables the predictor to estimate the FT of long-term state sequences from the tuple $(s,a,s')$.** Theorem 4 in our paper shows that the recursive operator $\\mathcal{T}$ is a contraction mapping, which guarantees convergence to the true FT function in tabular settings.\n\n\n\n**Q3. The upper bound of Theorem 1.**\n\n**A3.** \n+ **Theorem 1 provides intuition about the relationship between the distribution of the state sequences and policy performance.** As the state sequences generated by the learned policy approach the state sequences generated by the optimal policy, the performance difference between the two policies tends to zero. However, in online RL, we have no access to the state sequences generated by the optimal policy. Thus, **in practice, we optimize $\\overline{\\delta}_\\pi$ (the TD-style loss) instead of the right term of Theorem 1.** In A1 of this response, we present a theorem that establishes an upper bound on the sub-optimality performance gap using our optimized objective.\n\n+ According to  Lemma 13.3 in [1], the L1 norm is equivalent to the total variation (TV) norm. The total variation norm is a widely used distance measure for probability distributions.\n\n+ From the proof of Theorem 1, we acknowledge that the constant $\\frac{R_\\text{max}}{1-\\gamma}$ is necessary to establish the bound. In practice, we can consider constraining the reward range to minimize the magnitude of this constant.\n\n\n\n**Q4. What does $\\Gamma_\\text{Re}$ do in the prediction loss?**\n\n**A4.** \nConsidering that the states are vectors and we only take discrete samples for the estimation of FT, we rewrite the prediction loss in the matrix form $\\overline{\\delta}_\\pi(s_t,a_t,s_t') = \\widetilde{\\boldsymbol{S}}\\_t + \\Gamma \\, E\\_{\\pi,p}\\left[F(s\\_{t+1},a\\_{t+1}) \\right] - F(s_t,a_t)$. The form of  $\\Gamma$ is on Line 565 of the Appendix.\n\nNote that the prediction loss $\\overline{\\delta}\\_\\pi$ is complex-valued as $F_\\pi$ and $\\Gamma$ are complex-valued matrices. Thus, we measure the magnitude of $\\overline{\\delta}\\_\\pi$ with its modulus, that is, the sum of the squares of its real and imaginary parts. So we have to express $\\Gamma=\\Gamma\\_{\\text{Re}}+i\\Gamma\\_{\\text{Re}}$ and  $F=F\\_{\\text{Re}}+i F\\_{\\text{Re}}$ to compute the modules of the prediction loss.\n\n\n\n[1] Driver B K. Math 280 (Probability Theory) Lecture Notes. Lecture notes, Department of Mathematics.\n"}]

Author rebuttal:
We thank all the reviewers for the insightful comments and constructive suggestions, which are very helpful for us to strengthen this submission.

We have submitted detailed responses to address the concerns raised by all the reviewers. Besides answering the technical questions,

1. We provide a sub-optimality performance bound for the latent policy using the learned Fourier representation, which narrows the gap between the motivation and the implementation and explains why the learned Fourier features could be potentially useful for representations; (for reviewers 1q5C and  i4e2)
2. We conduct experiments to test our method on complex dexterous manipulation tasks, the Adroit benchmark, which demonstrates the effectiveness of our representation method to deal with high-dimensional inputs and non-periodic tasks; (for reviewers 1q5C and KaZ7)
3.  We extend the evaluation of our method to the visual-based RL setting on DeepMind Control tasks, which demonstrates the benefits of the Fourier transform on image feature extraction; (for reviewer KaZ7)
4. We provide more detailed results with the performance of our method at limited interaction steps, which demonstrates the superiority of our method in terms of sample efficiency; (for reviewer KaZ7)
5. We compare our method with an additional baseline D2RL, which demonstrates the superiority of our method over other feature-learning algorithms; (for reviewer ov12)
6. We extend the evaluation of SPF to partially observable domains, which demonstrates the effectiveness of our method with a lack of information. (for reviewer ov12)

We would like to know if our responses have properly addressed your concerns. All of your feedback and/or additional comments are warmly welcomed.

**We provide the proof of the bounded sub-optimality theorem as follows.**

Based on the proof of Lemma 1 in [1], we can prove a similar lemma as follows.

*Let Fourier transform function $F_\pi:=\mathcal{F}\widetilde{s}_{0}(\omega|\pi)$. For any policy $\pi$ and any function $f:S\rightarrow \mathbb{R}$, the following formula holds:*

$$
E_{s\sim\mu}[f(s)] +  \frac{1}{1-\gamma}E_{\substack{s\sim c^\pi \\ a\sim\pi \\ s'\sim P}}\left[\delta(s,a,s')\right] = F_\pi,
$$

*where*  $c^\pi(s)=(1-\gamma)\sum_{t=0}^\infty e^{-j\omega t}\gamma^tP(s_t=s|\pi,\mathcal{M})$,  $F\_\pi(s):=\mathcal{F}\widetilde{s}\_{0}(\omega|\mathbf{s_0}=s,\pi)\in\mathbb{C}^D$ *and* $\delta(s,a,s'):=s'+e^{-j\omega}\gamma f(s') - f(s)$.

Apply any two policy $\pi_1$ and $\pi_2$ to the above and let $f(s)=F_{\pi_2}(s)$ in the two obtained equations, then we get

$$
E_{s\sim\mu}[F_{\pi_2}(s)] +  \frac{1}{1-\gamma}E_{\substack{s\sim c^{\pi_1} \\ a\sim{\pi_1} \\ s'\sim P}}\left[s'+e^{-j\omega}\gamma F_{\pi_2}(s') - F_{\pi_2}(s)\right] = F_{\pi_1},
$$

and

$$
E_{s\sim\mu}[F_{\pi_2}(s)] +  \frac{1}{1-\gamma}E_{\substack{s\sim c^{\pi_2} \\ a\sim{\pi_2} \\ s'\sim P}}\left[s'+e^{-j\omega}\gamma F_{\pi_2}(s') - F_{\pi_2}(s)\right] = F_{\pi_2}.
$$

Take the difference between the above two equations, then we have

$$
F_{\pi_1} - F_{\pi_2} = (1-\gamma)^{-1}\cdot \left( E_{\substack{s\sim c^{\pi_1} \\ a\sim{\pi_1} \\ s'\sim P}}\left[\delta_{\pi_2}(s,a,s')\right] - E_{\substack{s\sim c^{\pi_2} \\ a\sim{\pi_2} \\ s'\sim P}}\left[ \delta_{\pi_2}(s,a,s')\right]\right).
$$
Note that the second term within the parentheses is zero, which is easy to check from the summation formulation of the Fourier transform $F_\pi$. Thus, we have
$$
F_{\pi_1} - F_{\pi_2} = (1-\gamma)^{-1}\cdot E_{\substack{s\sim c^{\pi_1} \\ a\sim{\pi_1} \\ s'\sim P}}\left[\delta_{\pi_2}(s,a,s')\right].
$$

Replacing $\pi_1$ and $\pi_2$ in the above equation with the optimal policy $\pi_*$ and the latent policy with the learned representation $\overline{\pi}\circ\phi$, respectively. Then their performance difference can be bounded as follows.

$$
\begin{align}
\| F_{\pi_*} - F_{\overline{\pi}\circ\phi}\| 
    &\leq (1-\gamma)^{-1}\cdot E_{\substack{s\sim c^{\pi_*} \\ a\sim{\pi_*} \\ s'\sim P}}\left[\delta_{\overline{\pi}\circ\phi}(s,a,s')\right] \\
    &= (1-\gamma)^{-1}\cdot E_{\substack{s\sim c^{\pi_*} \\ a\sim{\pi_*} \\ s'\sim P}}\left[s'+e^{-j\omega}\gamma E_{a'\sim{\overline{\pi}\circ\phi}}\left[F_{\overline{\pi}\circ\phi}(s',a')\right] - E_{a\sim{\overline{\pi}\circ\phi}}\left[F_{\overline{\pi}\circ\phi}(s,a)\right]\right] \\
    &\leq (1-\gamma)^{-1}\cdot \max\limits_{s,a} E_{s'\sim p(\cdot|s,a)}\left[s'+e^{-j\omega}\gamma E_{a'\sim{\overline{\pi}\circ\phi}}\left[F_{\overline{\pi}\circ\phi}(s',a')\right] - F_{\overline{\pi}\circ\phi}(s,a)\right] \\
    &\approx (1-\gamma)^{-1}\cdot E_{(s,a,s')\sim\mathcal{D}}\left[s'+e^{-j\omega}\gamma E_{a'\sim{\overline{\pi}\circ\phi}}\left[F_{\overline{\pi}\circ\phi}(s',a')\right] - F_{\overline{\pi}\circ\phi}(s,a)\right].
   \end{align}
$$

Let $\overline{\delta}\_\pi(s,a,s'):=s'+e^{-j\omega}\gamma E\_{a'\sim{\pi}}\left[F\_{\pi}(s',a')\right] - F\_{\pi}(s,a)$ and substitute the above inequation into Theorem 3, then we achieve the desired bound.

[1] Achiam J, et al. Constrained policy optimization, ICML 2017.

Meta-review: One of the shortcoming of prior predictive coding auxiliary task works in RL is prediction in the time domain, where relevant structure may be difficult to extract (e.g., using sequential state representation prediction). This work presents a novel and interesting approach formulating an auxiliary task in the frequency domain. This bridges modern auxiliary tasks in RL with prior works that attempted to formulate value learning in the frequency domain, an interesting and relevant outcome. The theory is sound and the model is well validated with experiments. I therefore recommend this paper as a spotlight at NeurIPS.
Decision: Accept (spotlight)