CAE: Repurposing the Critic as an Explorer in Deep Reinforcement Learning
Authors: Yexin Li
Venue: Accepted by TMLR ()

Abstract: Exploration remains a fundamental challenge in reinforcement learning, as many existing methods either lack theoretical guarantees or fall short in practical effectiveness. In this paper, we propose CAE, i.e., the Critic as an Explorer, a lightweight approach that repurposes the value networks in standard deep RL algorithms to drive exploration, without introducing additional parameters. CAE leverages multi-armed bandit techniques combined with a tailored scaling strategy, enabling efficient exploration with provable sub-linear regret bounds and strong empirical stability. Remarkably, it is simple to implement, requiring only about 10 lines of code. For complex tasks where learning reliable value networks is difficult, we introduce CAE+, an extension of CAE that incorporates an auxiliary network. CAE+ increases the parameter count by less than 1% while preserving implementation simplicity, adding roughly 10 additional lines of code. Extensive experiments on MuJoCo, MiniHack, and Habitat validate the effectiveness of CAE and CAE+, highlighting their ability to unify theoretical rigor with practical efficiency.

Published in Transactions on Machine Learning Research (02/2026)
CAE: Repurposing the Critic as an Explorer in Deep Rein- forcement Learning
Yexin Li
lieezin @bigai.
State Key Loboratory of General Artificial Intelligence, BIGAT
Reviewed on OpenReview: https: // opwprvveeeer.......omoe net/ htt//ormm? id= 54MOD02aC2
Abstract
Exploration remains fundamental challenge in reinforcement learning, as many existing methods either lack theoretical guarantees or fall short in practical effectiveness, In this paper, we propose CAE, i.c., the Critic as an Explorcr, a lightweight approach that ro- purposes the value networks standard deep RL algorithuns to drive exploration, without introducing additional parameters. CAE leverages multi-armed bandit techniques combined with tailored scaling strategy, enabling efficient exploration with provable sub-linear regret bounds and strong empirical stability. Remarkably, it is simple to implement, requiring only about 10 lines of code. For complex tasks where learning reliable value networks is difficult, we introduce CAE+, an extension of CAE that incorporates an auxiliary network. CAE+ increases the parameter count by less than 1% while preserving implementation simplicity, adding roughly 10 additional lines of code. Extensive experiments on MuJoCo, MiniHack, and Habitat validate the effectiveness of CAE and CAE+, highlighting their ability to unify theoretical rigor with practical efficiency.
1 Introduction
Exploration in reinforcement learning (RL) remains a fundamental challenge, particularly in sparse-reward environments. Although algorithms such DQN (Mnih ct al. 2015 PPO (Schulman al., 2017). SAC (Haarnoja el al. 2018). DDPG (Liliccrap et al. 2016), TD3 (Fujimoto et al. 2018), IMPALA (Es- peholt et al.] 2018), and DSAC Duan et al. 2021 2023) have achieved impressive performance on tasks like Atari games MMiih et al. 2013 2015), StarCrafi (Vinyals et al.) 2019), Go (Silver et al. 2017), etc., they often depend on rudimentary exploration strategies. Common approaches, such as e-greedy or injecting noise into actions, are often sample-ineffcieet and struggle environments with delayed or sparse rewards.
For decades, exploration strategics with provable optimality guarantees have been well established in tab- ular RLL settings (Kearns & Singh 2002). More recently, methods with provable regret bounds have been progressively extended to RI, with function approximation, including linear functions (Osband et al. 2016 2019 Jin et al. 2018 2020 Kamyar& & Animashree 2018:) Agarwal et al. 2020). kernel-based models Yang eet al. 2020 and neural networks (Yang et al.) 20220) While linear and kernel-based approaches make strong assumptions about the RL functions, the provable method based on neural networks suffers from prohibitive computational costs, specifically O(n²), where n is the number of parameters the network. Subsequently, some studies (Ash al.) 2022; [shfaq et. al.) 2024a) propose algorithms with theoretical op- timality guarantees under the linearity assumption and extend them directly to deep RL without further proof. Other works (Tshfaq et al.) 2021 2024bb derive provable regret bounds for their deep RL methods, but these approaches are either practically burdensome or rely on unknown sampling errors.
More practical exploration approaches typically rely on heuristic mechanisms, giving rise to a variety of empirically successful methods, including Pscudocount (Bellemare al. 2016), ICM (Pathak al. 2017), RND (Burda et al. 2019b), RIDE (Raileanu & Rocktäsche] (020). NovelD (Zhang al.] 2021a). AGAC (Feet-Berliac et al.
2021 and E3B (Henaff et al. 2022 2023 These methods introduce intrinsic

---

Published in Transactions on Machine Learning Research (02/2026)
Value network learning
E3B or CAB
Auxiliary component of CAE+
trajectories
trajectories
trujectories
embedding net
value
embedding layers
U
embedding layers
bonus f
value net
value net
auxiliary net
output layer
output layer
bonus B
bonus B
Lp
LD
Lf
LB
(a) E3B
(b) CAE
(c) CAE+
Figure 1: Comparison of baselines, such as E3B, with CAE and CAE+. L, denotes the Bellman loss used to update the value function, while L refers to the loss of the auxiliary network. Unlike E3B, which requires separate network to compute exploration bonuses, CAE exploits the embedding layers of the value network for this purpose. CAE+ further enhances CAE by incorporating a compact, lightweight auxiliary network, f= improving performance in sparse-reward environments with only a minor increase in parameters.
bonuses to encourage agents to visit novel states. For instance, RND computes the exploration bonus using the prediction error of a randomly initialized target network. Despite their empirical effectiveness, such approaches often distort the extrinsic reward signal and generally lack formal thcoretical guarantocs. In contrast, potential-base based reward shaping methods, such as Liberty (Yiming et al. (023) and EME (Yiming) et al. 2024), provide stronger theoretical justification but are often challenging to implement in practice. Moreover, all of the above methods require training auxiliary networks beyond the standard policy and value networks used in deep RL, resulting in substantially increased computational overhead.
In this work, we aim to combine the strengths of both theoretically grounded and empirically effective exploration methods. Provably efficient approaches are fundamentally rooted in the theory of Multi-Armed Bandits (MAB) (Li et al., 2010: Chu et al., 2011 Agrawal & Goyal 2013 Wen et al., 2015 Zhang et al. 2021b Zhou et al., 2020). Building on this foundation, we hypothesize that advanced techniques from neural MAB can be effectively adapted for exploration in deep RL. Recent studies (Zahavy & Mannor,
2019 Riquelme et al. 2018 Xu et al.] (022) suggest that decoupling deep representation learning from exploration strategies holds promise for achieving efficient exploration in neural MAB settings.
Motivated by these insights, we propose CAE. Unlike cxisting mothods that train additional embedding networks to generate exploration bonuses, CAE leverages the embedding layers of the value networks in the RL algorithms and employs MAB techniques to produce exploration bonuses. To ensure the practical stability of CAE, we adopt an appropriate scaling strategy (Welford 1962 Elsayed et al. (024)) process the bonuses. Consequently, CAE introduces additional parameters beyond those in the original algorithms, showcasing that. RT. algorithms inherently possess strong exploration capabilities if their learned networks are effectively leveraged. Moreover, CAE is simple to implement, requiring only about 10 lines of code. A comparison between CAE and existing methods is in Figure [
For tasks with complex dynamics and very sparse rewards, learning value networks challenging, impeding exploration based on them. Accordingly, we propose an extended version CAE+, as illustrated in Figure D CAE+ integrates a compact, lightweight auxiliary network to facilitate the learning process. The structure of the auxiliary network is carefully designed to prevent severe coupling between the environment dynamics and the returns, thereby further enhancing the performance of CAE+. Remarkably, this addition increases the parameter count by less than 1% and requires only about 10 extra lines of code, thus preserving the simplicity and lightweight nature.
Our exporiments cover diverse set of benchmarks, Le., MuJoCo, MiniHack, and Habitat, representing dense- reward, sparse-reward, and reward- free environments. CAE improves the performance of stato-of- the-arrtt RL baselines, including PPO (Schulman et al. 2017 SAC (Haarnoja et al. 2018), TD3 (Fujimoto et al.) 2018
2

---

Published in Transactions on Machine Learning Research (02/2026)
Table 1: Method comparison. Linear function indicates whether the theoretical guarantees apply to RL algorithms with linear function approximation. Network-based function specifics whether the guarantees extend to RL algorithms using network- function approximation. Toy task denotes whether the method can be effectively applied to simple deep RL tasks. Practical complex task indicates whether the method remains practically feasible when deployed in realistie, large-scale deep RL environments.
Provable
Empirical with Deep RL
Method
Linear function
Network-based function
Toy task
Practical complex task
LSVI-UCB Jin al.
2020
NN-UCB Yang et al.
2020
OPT-RLSVI Andrea sl.
2020
X
LSVI-PHIE [lshfaq
212
BDQN Kamyar & Animashree
2018
ACB Ash et al. 2022
X
LMCDQN [Ishlaq
2024a
CAE
CAR+
and DSAC (Duan et al. 2021 outperforming E3B Henaff al (2022 2023), the state-of-the-art exploration method for MiniHack and Habitat, across all evaluated tasks. These results highlight the superior reliability and effectiveness of CAE and CAE+ in diverse RT. scenarios.
2023
Additionally, CAF+ demonstrates robust performance, consistently
In summary, we make three key contributions. First, we propose lightweight CAE and CAE+, which enable the use of linear MAB techniques for exploration in deep RL. By adopting scaling strategy and carefully designing the small auxiliary network for CAE+, we ensure both practical stability and functionality in environments with dense and sparse rewards. Second, our thcoretical analysis demonstrates that any deep RL algorithm with CAE CAE+ achieves sub-linear regret bound over episodes. Finally, experiments on MuJoCo, MiniHack, and Habitat validate the effectiveness of CAE and CAE+, showcasing their superior performance. Our code is available at https: //github.com com /iyeen/ Critic-as-an -aapp--o--
2 Related Work
Multi-armed bandits. MAB algorithms address the ssploration-xpplotaaiie dilemma by making se- quential decisions under uncertainty. LinUCB (Ti et al.] 2010) assumes a linear relationship between arm contexts and rewards, enabling efficient exploration via uncertainty quantification in the estimated parameter
space and ensuring a sub-linear regret bound (Chu et al. 2011 To relax the linearity assumption, Ker- nelUCB (Valko et al. 2013 Chowdhur & Gopalan 2017) and NegUCB (Li et al. 2024 transform contexts into high-dimensional spaces and apply LinUCB to the mapped contexts. Neural-UCB (Zhou et al. 2020 and Neural-TS (Zhang el al.) 2021b) leverage neural networks to model the complex relationships bet ween contexts and rewards. However, their computational complexity of O(z²), where n denotes the number of network parameters, limits their scalability in real-world applications. Neural-LinT'S (Riquelme al. 2018 and Neural-LinUCB (Xu et al., 2022) mitigate this limitation by decoupling represcntation learning from exploration strategies, improving the practicality of neural MAB.
Provable exploration in RL. Provably efficient exploration methods (Karrs & Singh 2002 Osband
et al. 2016 2019 Jin et al. 2018
2020 Agarwal et al. 2020 Cai et al. 2020 Daniil et al. 2022 2023
often face empirical limitations or remain primarily theoretical, with limited applicability to deep RL. Some
studies (Alessio & Filippo 2024 Kamyar & Animashree, 2018 Ash et al., 2022 Ishfaq el al. 2024a) propose methods with theoretical guarantees under tabular or linearity assumptions and extend them directly to deep RI. settings. Other works (Ishfaq et al. 2021 2024bb provide provable bounds for deep RI,, but these approaches may suffer from any of the following limitations: computationally prohibitive, practically burdensome, or reliance unknown sampling errors. A comparative analysis is presented in Table
3

---

Published in Transactions on Machine Learning Research (02/2020)
Practical exploration in deep RL. Empirically successful methods (Bellemare et al.
2016
Pathak
et al. 2017: Burda et al., 2019a Raileanu & Rocktäschel 2020 Burda et al. 2019b: Zhang et al.
2
F'et-Berliae et al. 2021; Henaff et al. 2022 2023 Jarrett et al. 2023 Yuan et al. 2023) typically generate
exploration bonuses to encourage agents to visit novel states. However, these approaches often lack rigorous
theoretical loundations. In contrast, methods inspired by potential-based reward shaping (Andrew et al.
1999), such as Liberty (Yiming al., 2023) and EME (Yiming al. 2024). offer stronger theoretical grounding, but are challenging to implement in practice. Moreover, both classes of methods generally require training substantial number of additional parameters. In comparison, CAE and CAE+ utilize MAB techniques, assisted by embedding layers within the RL value networks, providing empirical benefits with minimal additional parameters. Figure Tillustrates the differences among various exploration methods, while Table summarizes their additional networks and parameters.
Table 2: Comparison of exploration methods MiniHack. Networks: additional networks beyond those in the base RL algorithm IMPALA (Espeholt et al. 2018), which contains 25, 466, 652 parameters; # Params: the number of additional parameters introduced by the exploration method. Networks in bold represent those with significant parameters, while those in gray indicate substantially fewer parameters.
Method
Networks
Params
Params
ICM
Pathaa et sl.
2017
Embedding Forward dynamics Inverse dynamics
16, 074, 512 +-2, 110, 461 + 371,371
73%
RND
Burda
20195
Embedding
16, 071,
63%
RIDE
Burda
20196
Embedding Forward dy dynamics Inverse dynamics
16, 074, 512 +-2, 110, 464 + 527,371
73%
NovelD
Zhang et
2021a
Embedding
16, 06,074,512 512
63%
E3B
Henalf et al.
2122
2723
Embedding + Inverse dynamics
16, 072, 512 3717877
65%
CAE
0
CAE
Inverse dynamies
199, 819
0.8%
3 Methodology
Unless otherwise specified, bold uppercase symbols denole matrices, while bold lowercase symbols represent vectors. I refers to an identity matrix. Frobenius norm for matrices and 12 norm for vectors are both denoted by I1-112- Mahalanobis norm of a vector with respect to A is defined as |=l|A= Vxl Ax. For any integer K > 0, the set of integers 21, K} is denoted by [K].
3.1 Preliminary
An episodic Markov Decision Process (MDP) is formally defined as tuple H,,r, where S denotes the state space and A is the action space. Integer H indicates the duration of each episode. Functions P. : S x A + [0, 1] and rr: S x A + [0, 1] are the Markov transition and reward functions, respectively. During an episode, the agent follows a policy
S A + [0, 1]. At each time step h E [H] in the episode, the agent observes the current state 8). E S and selects an action 0Ą ~ ((11%)) to execute, then the environment
transits to the next state 8h+1 ~ P(-)s), an), yiclding an immediate reward Ta = r(sh, on). At time step h, the action-value function Q(sn, un) measures the cumulative return obtained by taking action as in state 8n and subsequently following policy
H Σg t=h
Q(sh, an)
7 r
(L)
where 0 5 7 I 1 is the discount parameter.
Many algorithms have been developed to learn the optimal policy n" for the agent to select and execute actions at each time step h in the episode, thus ultimately maximizing the cumulative return Σ 2 h- Th. Notable algorithms include DQN (Mnih et al., 2015). PPO (Schulman et al. (017). SAC (Haarnoja et al. 2018), TD3 (Fujimoto et al. 2018)) IMPALA (Espeholt et al.) 2018), DSAC Duan et al. 2021 (023). and others. A common component of these algorithms neural network that parameterizes the action-value
4

---

Published in Transactions on Machine Learning Research (02/2026)
function .(:-)) under specific policy as Equation 2 where is the embedding layers, 0 and W are trainable parameters of the network.
Q(s, = "(ss=a'((ssaaW))
Bellman loss as Equation iss often employed to learn the action-value function. Using the most recent action- value function, the policy can be updated in various ways, depending on the specific algorithm. Since CAE focuses on leveraging Equation 2 [or efficient. exploration while preserving the core techniques of existing RL algorithms, introduce CAE within the context of DQN for simplicity. However, it can be easily adapted to other RL algorithms.
[en)))Bnnnnte LB = (Q(s)) an) Bent ((oos,aw)
rh + + max Q( ((h++1,0++1)) ah+1
(3)
3.2 CAE: the Critic as an Explorer
For a state-action pair (s, a), the estimated action-value Q(s, a) is subject to an uncertainty term B(s, a), arising from the novelty or limited experience with the particular state-action pair. Similar to MAB prob- lems, explicitly accounting for such uncertainty crucial. Incorporating this uncertainty term promotes exploration and can lead to improved long-term returns. Accordingly, with an uncertainty bonus, as shown in Equation f where a 2 0 denotes the exploration coefficient. In the literature, uncertainty is often also referred to as a bonus, and we use the two terms interchangeably when no ambiguity arises.
adjust the action-value function
Q(8, a) = 0 0T, W) (1)
(4)
However, defining B(s, a) remains challenging. Provably efficient methods often attempt to address this by either assuming lincar value function (Jin et al.) 2018) requiring On²² computation time (Yang et al. 2020) in terms of the nunber of parameters n in the value network. Both of these approaches have drawbacks, t.e., linearity fails to capture the complexity of tasks while the O(n²) computational cost is impractical.
To overcome these limitations, we draw inspiration from Neural-LinUCB (Xu et al. 2022 and Neural- LinTS (Riquelme el al., 2018), which effectively decouple representation learning from exploration strategies.
Building on this idea and following the standard value network structure in Equation 2 CAE decomposes the action-value function into two distinct components.
Network (88 a W) extracts the embedding of the stale-action pair (s, a);
Q(s TT (0, (,,00 a W) is a linear function of the embedding Φ(8, al W) with parameter 0.
Consequently, after appropriate modifications, MAB theory under the linearity assumption can be adapted to work with the embeddings Φ(8, a) for Vs E S and Va E A. Simultaneously, the action-value function retains its representational capacity through the embedding layers 6(s, a), ensuring promising practical performance. While various MAB techniques can be adapted to the emboddings, we illustrate CAE using the two most representative ones. Other techniques can be utilized similarly, showcasing that CAE is generalizable framework rather than fixed method.
Upper Confidence Bound (UCB) is optimistic exploration strategy in MAB. It defines the uncertainly term as Equation 5 where o(--)) denotes the latest embedding layers, and A is the Gram matrix, initialized as A = XI with À being the ridge regularization parameter. At each step, A is updated using Equation 0
In some algorithms, state-value function is learned instead of the action-value function. However, this does affect. the implementation and conclusion of method, will be seen Subsection 3.2
5

---

Published in Transactions on Machine Learning Research (02/2026)
B(s,a) / (
(5)
A + a (s,a)
(6)
Thompson Sampling is a randomized exploration strategy that samples the value function, adjusted for uncertainty, from a posterior distribution. It defines the uncertainty term as Equation 7 where the Gram matrix A is initialized and updated in the same manner in UCB.
A ~ ~ N(0, )(s, os
(7)
=
As the value network undergoes continuous updates, exploration based on the ever-changing embedding layers ob can become highly unstable, significantly impairing practical performance. Inspired by existing scaling strategies (Welford 1962 Elsayed et al.] 2024), we adopt appropriate one for the generated uncertainty at each time step, ensuring both stability and practical functionality, detailed in Algorithm This scaling strategy normalizes the generated uncertainty at each time step using the running standard deviation, which, despite its simplicity, has a profound impact on the performance of CAE. The critical importance of this design further highlighted through ablation studies presented in Appendix E
Adapting CAE to General RL Algorithms. Depending on the RL algorithm employed, we may sometimes learn a state-value network instead of an action-value network. In such cases, the network produces embeddings for states rather than for state-action pairs. Even when an action-value network is learned, it might still output only state embeddings if it is designed to take state as input and produce values for multiple actions. In these scenarios, we either the embedding of the next state the embedding concatenated with the action as proxy for the current state-action action embedding when computing uncertainty.
Algorithm Scaling strategy for the uncertainty
1: Input: Uncertainty b, rumning
μA, cumulative squared deviation 22, and running count of samples / 2: Update the sample count N - +1
3: Compute 5 = b-=
4: Update the running mean μ +- 1+
5: Update the cumulative squared deviation 2 + u² +8x (b- and the updated μ,, v², and N
6: Output: Scaled uncertainty V
3.3 CAE+:
Enhancing CAE with Minimal Overhead
For tasks with complex dynamics very sparse rewards, learning value networks is particularly challenging, which in turn hinders exploration reliant on them. Accordingly, we propose CAE+, an extension of CAE that incorporates a lightweight auxiliary network, introducing less than 1% additional parameters.
Specifically, we utilize an Inverse Dynamics Network (IDN) PPthak et al., 2017 Raileanu & Rocktäschel 2020 Henaff et al., (202)) to enhance the learning of the embedding layers contained in the value networks.
This is achieved by compact network ff that infers the distribution p(ax) over taken actions given consecutive states 8), and 8h+1, which is trained by maximum likelihood estimation Equation g
L log p(an (s,, 8h+1)
(8)
We utilize the embedding layers as follows:
If the value network is an action-value network with embodding layers ((s, a), a fixed default action ä is assigned to the action input while the true states are used: the resulting outputs of Φ(-, a) are then treated state embeddings.

---

Published in Transactions on Machine Learning Research (02/2026)
If the value network is state-value network with embedding layers Φ(s), the actual states are directly fed in to generate their embeddings.
These state embeddings are subsequently transformed by a linear layer U, followed by a small network J, which processes the transformed consecutive embeddings to infer the action. Equation 9 illustrates this procedure for the case embedding layers d(s,a).
plan|on, 8h+1) = [bb(s, ä), ((*++1 a)) ((U@(sn ä), Uő($n+1,))
(9)
Although incorporating the IDN loss can accelerate learning of the embedding layers by leveraging knowl- edge of environment dynamics, it also introduces additional constraints on the shared embedding space, thereby limiting the flexibility of the embeddings for exploration. In CAE+, to address this limitation, we adopt the transformed embeddings Uć(s, a) instead of the original ones Φ(s, a) to calculate the uncertainty. Consequently, by replacing Φ(s.a) a) with (o(s,00 a), Equations and 7 which are used in CAE generate uncertainty, are modified into Equation 10 with the Gram matrix A updated according to Equation 11 Complete procedure of CAE+ is in Algorithm
B(s,a) a A
UCB
(10)
(AO)) Iao Thompson Sampling
A + A+ ())
(11)
In CAE+, the structure of the network offers several advantages. First, the transformation U decouples environment dynamics from returns, mitigating interdependenctes that could hinder flexibility and thereby enhancing empirical performance, as evidenced by the ablation studies presented later. Second, since U is a simple linear transformation, it approximately preserves the theoretical guarantees of UCB-based and Thompson Sampling- based exploration ion strategies, ensuring both rigor and stability in practice. Third, by projecting ((s, a) into a lower- dinensionan embedding with d < d, the approach not only reduces the number of additional parameters but also lowers the computational complexity of uncertainty estimation cach time step, i.e., from (dd) to Odd), making the method more efficient.
Speed Up CAE+ with Rank-1 Update According to Algorithm 2 the Gram matrix A needs to be inverted at cach step, which is cubic in dimension. Alternatively, we can use the Sherman-Morrson matrix Henaff et al. 2022) to perform rank-1 updates of A-1 in quadratic
identity (Sherman & Morrison
1950
time as Equation 12
A Unls, (s..0)))AA
A-
(12)
1t (s UUbss,
4 Theoretical Analysis
Under the optimal policy x", let the corresponding action-value function Q' be structured as in Equation 2 and parameterized by 0* and W* In Algorithm 2 the policy executed episode m [M] is denoted by Tyn. and its associated action-value function QTT.. Cumulative regret of Algorithm 2 is given in Definition [
Definition 1. Cumulative Regret. After M episodes of interactions with the environment, the curmulative regret of CAE CAE+ is defined as Equation 13 where up is the optimal action at state sT. generated by policy T" while at is that selected by the executed policy Tm.
RM =
Σ Q'( ("("""""") ) Q (x (5TT
(13)
m=1

---

Published in Transactions on Machine Learning Research (02/2026)
Algorithm 2 CAE+ with Action-value Network
1: Input: Ridge parameter À > 0, exploration parameter a 2 0, cpisode length H, episode number M, learning rate
Initialize: Gram matrix
AI, initial policy st-) and value function Q(:-), network f(-UU), running mean 0.
cumulative squared deviation ش² = 0, running count N
3: for episode
M do Receive the initial state s1 from the environment for step h 1,2,,.., H do
6: Execute action 4% ~ m(s)", observe the next state $441 and receive the immediate reward ri
7:
Generate bonus ((5 o%% by Equation 10
8:
Provide B(sg -0 f4, v², and N inputs to Algorithm to obtain scaled honus & and updated is, u², and N
9:
Reshape the reward F "h" + a.5%
10:
Update the Gram matrix A by Equation 11 end for
11:
12:
Sample batch B= {s), "i. 5
-1, (
13:
Calculate the IDN loss Ly by Equation [ and the Bellman loss Le by Equation g on batch B
14:
Update value function Q(--)) and network jointly by mininizing the combined loss min(Ly La) with step size y)
15:
Update the policy T(-) based on the latest value function Q(:,)
16:
end for
The cumulative regret measures the gap between the optimal return and the actual return accumulated over M episodes. As discussed earlier, CAE draws inspiration from Neural-LinUCB (Xu al. 2022) and Neural- LinTS (Riquelme al. 2018). While Neural-LinUCB is supported by theoretical guarantees, Neural-Lin has so far only been validated empirically. In this work, we complete the regret analysis for Neural-T.inTS and subsequently derive the regret bound of CAE. Before stating Theorem | we introduce the standard assumptions used in the ure on deep representation and shallow exploration (Xu el al.) 2022) as Assumption
Assumption is deferred to the Appendix because it requires more [ and Assumption 2 detailed notation.
Assumption 1. Assume that (1s; = 1 for Vs E E.E S,Ya E A. The entries of (8; satisfy Equation 14 where j = 1,2,..., 2
D. and D represents the dimension of (s;
(s;a), (5;
(14)
Note that even if the original stato-action pairs (s;a) do not satisfy this assumption, they can be preprocessod by augmenting them to (s; 8; and applying appropriate scaling to ensure the assumption holds. Assumption 2. The neural tangent kernel H of the action-value network positive definite.
Neural tangent kernel H is defined in accordance with a recent line of research (Jacot et al. 2018 Arora et al. 2019 Xu al. 2022) and is essential for the analysis overparameterized neural networks. A detailed discussion of these assumptions is deferred to Appendix D.3, where we show that they are mild and commonly adopted in the literature. In the following, we present the regret guarantee of CAE.
Theorem 1. Assume that Assumption 1 Assumption and Assumption 3 hold, and that [|0 S as well as [|o(s, a))l, < for Vs E S, Va E A. For any a E (0, 1), assume that the number of paramelers in each of the L layers of -(.,)) satisfies poly(L, D, 1, log MlAl), where |A] denotes the size of the action space and poly(-) denoles a polyommial function of the listed variables. Sel the exploration coefficiend and slep size as:
a = v 2 + M log log//A log 17) + VA
log(1
n 9 D² 1 log M
then with probability at least a, it holds that:
8

---

Published in Transactions on Machine Learning Research (02/2026)
M XD CaHl Mfngg-++ C&HL. M /oog log (:) log (MAA) l1q --
RM S CzoHl M
t7
where C1. C2 C3. C4 are conslants; q and q are the lorget value vector and the eslimated value vector of the action-value network, respectively. More discussions of these notations are Appendia B and Appendir
Specifically, assume | 122 s and [|o(s, a)ll2 I to make the bound scale-free. From this theorem, we can conclude that the upper bound of the cumulative regret grows sub-linearly with the number of episodes M, i.. ((vM) where O-) hide constant and logarithmic dependence of M, indicating that the executed policy improves over time. Since MAB techniques are applied to the linear layer on top of the embedding layers, the cumulative regret naturally consists of two components, i.e., the exploration regret from the linear layer and the error induced by the network's estimation, which appears the last term in the regret bound. It involves trade-off between M and t. Moreover, as the estimation error ||q -9ll H decreases over time, this term typically becomes negligible.
5 Experiment
Benchmarks. In our experiments, we evaluate CAE and CAE+ on MuJoCo, MiniHack, and Habitat, which correspond to dense-reward, sparse-reward, and reward-free settings, respectively.
Baselines. We evaluate our approach against nine baselines, i.e., SAC HHarnoja et al. 2018 PPO Schuu-
man et al. 2017), TD3 (Fujimoto et al., 2018), DSAC (Duan et al. 2021 2023
ICM (Pathak et al. 2017
RND (Burda et al. 2019b). RIDE (Raileanu & Rocktäschel 2020 NovelD Zhang et. al. 2021a) and
E3B (Henaff et al. 2022 2023
For MuJoCo tasks, we evaluate SAC, PPO, TD3, and DSAC, both with and without CAE. Notably, the other baselines are excluded from the MuJoCo experiments, as they are rarely applied to dense reward settings. Since CAE introduces no additional parameters, meaningful to assess whether it can improve existing RL algorithms without increasing training overhead.
For MiniHack and Habitat tasks, we adopt IMPALA (Espeholt et al. 2018 and PPO as the base RL algorithms, respectively, following the standard configurations in the open-source codebases. We compare CAE and CAE+ against ICM, RND, RIDE, NovelD, and E3B. Since E3B achieves state-of-the-ard perfor- mance on both MiniHack and Habitat, we report only the results of E3B. For results of TCM, RND, RIDE, and NovelD,, refer to the E3B paper (Henaff et al. 2022 2023
All the experiments are based on open-source codebases from E3B, CleanRL (Huang al. 2022 DSAC, and
Habitat-lab (Savva et al. 2019 Andrew et al. 2021 Xavi et al., 2023). The core code and hyperpa parameters
are provided in Appendices A and E respectively. All experiments were conducted on Ubuntu 22.04 LTS
system equipped with 13th Gen Intel Core i9- 19-13900KF CPU and an NVIDIA RIX 4090 GPU.
5.1 MuJoCo tasks with Dense Rewards
Table 3: Experimental results after 1e6 environment interaction steps on MuJoCo-v4 tasks, except for the Humanoid task, which evaluated after 4e6 steps. RPT represents the Relative Performance Improvement achieved by CAE. Refer to Appendix for the corresponding experimental curves.
Alg.
Euv
PPO
PPO
CAE
RPI %
TD3
TD3
CAE
RPI %
SAC
SAC + CAE
RPI %
Swimmer
99
107 6.47
8.08
78
15.4
66.7
61 35.2
Hopper
2503 786.6
2453
673.2
-2.00
3044 + 574.0
3244
226.3
6.57
2908 600.8
3188 +: 485.2
9.63
Walker2d
3405 + 842.0
3554
1164-9288 928.0
4.38
3764 + 234.4
4251 + 567.1
12.9
4362 = 405.5
4742 - 48444
8.71
Aut
1762 - 510.0
2378
= 813.4
35.0
3192
1745.7
5074 519.3
45.3
1846 - 1306.4
5-182 - 511.9
13.1
HallChestal
2636 = 1344.3
3104 = 926.0
17.8
10316 = 193.8
10473
563.4
1.52
11154 1 457.1
11587
418.3
3.88
Hummmoid
92.1
127.1
4.36
257.7
483.2
3.06
5261
228.4
-0.82
RPI Meno
11.3
23.0

---

Published in Transactions on Machine Learning Research (02/2026)
MuJoCo testbed is widely used physics-based simulation environment. MuJoCo provides a suite of contimu- ous control tasks where agents must learn to perform various actions, such as locomotion, manipulation, and balancing, within simulated robotic environments. Since comparisons among state-of the-arrt RL baselines, such as PPO, SAC, TD3, and DSAC on MuJoCo, have been extensively covered in previous studies, our locus is on invesligating how CAE can enhance these algorithms.
Results are summarized in Table 3 averaged over random seeds (1,2,3.4,5) The results show that CAE consistently improves the performance of PPO, TD3, and SAC across most MuJoCo tasks. Notably, TD3 and SAC augmented with CAE achieve sub- stantially better performance on the Swimmer task. Although this task is not considered particularly challenging, the standalone TD3 and SAC basclines obtain relatively limited returns.
Table 4: Experimental results after 1e6 interaction steps on MuJoCo-v3, except for the Humanoid task, which is evaluated after 266 steps.
Alg.
DSAC
DSAC CAE
RPI %
Euv
Swimmer
131 4: 14.8
150 7.96
14.5
Hopper
2417 + 541.6
2845 594.5
17.7
Walker2d
5550 + 624.0
6069
422.1
9.35
Ant
5912 + 809.7
6305 = 322.7
6.65
In Table ! summarize the performance of DSAC with and without CAE. These experiments are con- ducted on MuJoCo-v3, rather than MuJoCo-v4, be- cause the open-source DSAC codebase built upon MuJoCo-v3. As shown, incorporating CAE consis- tently improves the performance of DSAC across the MuJoCo benchmark tasks.
HalfChectah
16036 1 439.1
16338 1 249.1
1.88
Humanoid
10059 1 906.1
10333
1104.4
2.72
RPI Mean
8.80
5.2 MiniHack tasks with Sparse Rewards
MiniHack (Samvelyan et al. 2021 is built on the NetHack Learning Environment (Küttler et al., 2020), a challenging video gain where an agent nav- igates procedurally generated dungeons to retrieve magical amulet. MiniHack tasks present a diverse set of challenges, such as locating and utilizing mag- ical objects, traversing hazardous environments like lava and monsters. These tasks are characterized by sparse rewards, and the state provides a wealth of information, including images, texts, and more, though only a subset is relevant to each specific task.
E38 65%
1.0
E38 85%
CAE 0.8%
GAE 0.8%
no 2.1%
no U 2.1%
0.5
0.0
0.0
-0.5
-1.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
(a) Horn- Rent-Resrrictd
(b) N6-Locked
Figure 2: Ablation study to U on MiniHack. Horizon- tal axis denotes the steps in multiples of le7.
As shown in Table 2 CAE+ introduces only 0.8% increase in parameters compared to the base RL al- gorithm, IMPATA. In contrast, other exploration
baselines, such as RIDE and E3B, require 60% 80% additional parameters, underscoring the lightweight design of CAE+. Experimental results for E3B and CAE+, averaged over seeds 21, 3), are summarized in Table 5 Performance is evaluated nine representative tasks, i.e., five navigation tasks and four skill tasks. The results demonstrate that CAE+ consistently outperforms E3B across tasks. In particular, on challenging tasks such as N6-Locked and LavaCross, CAE+ achieves substantial performance improvements of 348% and 282%, respectively, highlighting its strong exploration capabilities.
Ablation study CAE on MiniHack. Results of CAE on MiniHack tasks are provided in Table As shown, CAE successfully solves a subset of tasks and even surpasses CAE+ in certain cases. However, it struggles to achieve positive performance in others, such as N6-Locked, etc., which pose significant explo- ration challenges. This limitation stems from the difficulty of training effective value networks in complex environments, adversely affecting exploration reliant on them.
Ablation study to the transformation U. Additionally, we present experimental results for CAE+ without the transformation matrix U in the auxiliary network f. As shown in Figure CAE+ without occasionally outperforms E3B, though there instances where it does not. Importantly, it consistently
10

---

Published in Transactions on Machine Learning Research (02/2026)
underperforms the full CAE+ method with U. Moreover, CAE+ introduces more additional parameters without matrix U, specifically 2.1%.
Wall-clock running time analysis. RL experiments involve both network training and environment interaction CPUs; therefore, wall-clock time is typically not regarded standard evaluation metric. Nevertheless, to provide a clear picture of the practical efficiency of CAE, we report wall-clock running times on MiniHack tasks. CAE requires approximately 17 hours to complete training per task, whereas E3B takes around 22 hours, demonstrating the superior efficiency of CAE.
Table 5: Experimental results after 2c7 - 3c7 interaction steps on nine MiniHack tasks, whose detailed descriptions are in Appendix F.2 RPI quantifies the improvement of CAE+ compared to E3B. Since E3B is the state-of-the-art on MiniHack (Henaff et al. 2022), and CAE+ consistently outperforms it, we conclude that CAE+ E3B, ICM, RND, RIDE, NovelD. Refer Appendix B for experimental figures.
Env
Alg.
N4
N4-Lockd
N6-Locld
N10-OD
Horn
Raadom
Wand
LavaCross
0.57
CAF
0.93 + 0.014
0.84 + 0.041
0..6
0.193
0.37 + 0.310
0.84 + 0.216
0.92 + 0.022
0.93 + 0.022
0.93 + 0.030
0.16 0.334
CAE+
0.97 0.006
0.87 0.017
0.94 0.014
0.77 0.093
0.86 d: 0.023
0.84 1: 0.055
0.80 0.040
0:65 0.131
0.84 0.024
RPT
12.79
20.83
348.39
78.72
40.35
32.65
281.82
5.3 Reward- free Habitat task
Habitat (Savva et al. 2019: Andrew et al. 2021 Xavi et al. 2023 is a platform for embodied AT research that supports agent navigation and interaction within simulations of real-world indoor environments. The experiments in this subsection are designed to evaluate exploration capabilities in visually rich, realistic settings. We employ the HM3D dataset (Santhosh et al. 2021), which comprises high-quality reconstructions of 1, 000 diverse indoor spaces. Agents are trained solely with the generated exploration bonuses on the PointNav task. Evaluation is performed in unseen test environments by measuring the proportion of the environment revealed.
Results for E3B, CAE, and CAE+, averaged over three seeds {1, 21,2,3, 3}, are summarized in Table 6 highlighting the superior performance of CAE+. Since E3B is the state-of-the-art on Habitat, and
Table 6: Experimental results after 1e8 interaction steps Habitat.
E3B
CAE
CAE+
RPI %
CAE+ further outperforms E3B, it follows that CAE+ E3B, ICM, RND, RIDE, NovelD. Figure 3 provides illustration of specific case, where the trained policy of CAE+ explores larger portion of the environment compared to that of E3B.
0.51 = 0.097
0.49 0.102
0.69 = 0.074
35.29
(a) CAE+ reveals 0.67 of the map
(b) E3B reveals 0.53 of the map
(c) CAE reveals 0.51 of the map
Figure 3: Trajectories of the learned policies Habitat environment unseen during training.
6 Conclusion
In this paper, we propose CAE, lightweight exploration method that seamlessly integrates with existing RL. algorithms without adding parameters. CAE exploits the value network's embedding layers to guide
11

---

Published in Transactions on Machine Learning Research (02/2026)
exploration, requiring no changes to the rest of the algorithm. A simple scaling strategy ensures stable learning. For sparse-reward tasks, extend CAE to CAE+ by adding small auxiliary network, accelerating learning with minimal overhead. We provide theoretical guarantees in the form of sub oub-linear regret bounds. Extonsive experiments show that CAE and CAE+ significantly outperform bascline methods across dense- reward, sparse-reward, and reward-free settings.
Broader Impact Statement
CAE and CAE+ bridge the gap between provably efficient and practically successful exploration methods. While theoretically grounded approaches often suffer from scalability and applicability issues, empirically driven methods typically lack thcoretical guarantees and require extensive parameter training. Inspired by the deep represenlation und shallow exploration paradigm, this work proposes novel framework that decomposes value networks in deep RT. and repurposes their embedding layers for exploration, thereby achieving theoretical guarantees with minimal or no additional parameter training.
This framework contributes to the development of sample-eficient and interpretable exploration methods in deep RI, potentially accelerating progress in applications such as robotics, recommendation systems, autonomous deeision-making systems, and large language models. Moreover, the lightweight nature of the method makes it suitable for deployment in resource-onnstraindd settings. Future research could focus integrating a broader spectrum of MAB techniques, evaluating the robustness across wide range of tasks, and improving the computational efficiency of uncertainty estimation.
Acknowledgments
The first author thanks Ping Huang and Hanfang Zhang for their assistance with configuring several open- source baselines, and Shuo Chen and Siyuan Qi for their substantial help in revising and improving the manuscript.
This work is supported by the National Natural Science Foundation of China (No. 62506041).
References
Alekh Agarwal, Sham Kakade, Mikael Henaff, and Wen Sun. Pc-pg: Policy cover directed exploration for provable policy gradient learning. In Proceedings of the 34th Conference on Neural Information Processing Systems, 2020.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payolls. In Pro- ceedings of the 30th International Conference on Machine Learning, pp. 127-132111111 PMLR, 2013.
Russo Alessio and Vannella Filippo. Multi-reward best policy identification. In Proceedings of the 38th Conference on Neural Information Processing System, 2024.
Zanette Andrea, Brandfonbrener David, Brunskill Emma, Pirotta Matteo, and Lazaric Alessandro. Frequen- List. regret. bounds for randomized least-squares value iteration. In Proceedings of the 23rd Internalional Conference on Artificial Intelligence and Statistics. PMLR, 2020.
Szot Andrew, Clegg Alex, Undersander Eric, Wijmans Erik, Zhao Yili, Turner John, Maestre Noah, Mukadam Mustala, Chaplot Devendra, Maksymels Oleksandr, Gokaslan Aaron, Vondrus Vladimir, Dharur Sameer, Meier Franziska, Galuba Wojeiech, Chang Angel, Kira Zsolt, Koltun Vladlen, Malik Jitendra, Savva Manolis, and Batra Dhruv. Habitat 2.0: Training home assistants to rearrange their habitat. In Proceedings of the 35th Conference Neural Information Processing System, 2021.
Y. Ng Andrew, Harada Daishi, and J. Russell Stuart. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the 16th International Conference on Machine Learning. PMLR, 1999.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact com- putation with an infinitely wide neural net. In Proceedings of the 33nd Conference on Neural Information Processing Systems, 2019.
12

---

Published in Transactions on Machine Learning Research (02/2026)
Jordan T. Ash, Cyril Zhang, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Anti-concentrated confidence bonuses for scalable exploration. In Proceedings of the 10th International Conference on Learn- ing Representations, 2022.
Mare G. Bellemare, Sriram Srinivasan, Georg Ostrovaki, Tom Schaul, David Saxton, and Remi Munos.
Unilying count-based exploration and intrinsic motivation. In Proceedings of the 30th Conference on Newral Information Processing System, 2016.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and A. Alexei Efros. Large- scale study of curiosity-driven learning. In Proceedings of the 7th International Conference on Learning Representations, 2019a.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In Proceedings of the 7th International Conference on Learning Representations, 2019b.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In Proceedings of the 37th International Conference Machine Learning, 2020.
Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In Proceedings of the 34th International Conference on Machine Learning. PMLR, 2017.
Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pp. 208-2144444 214, 2011.
Tiapkin Daniil, Belomestny Denis, Moulines Éric, Naumov Alexey, Samsonov Sergey, Tang Yunhao, Valko Michal, and Pierre Ménard. From dirichlet to rubin: Optimistic exploration ion in rl without bonuses. In Proceedings of the 39th International Conference on Machine Learning. PMLR, 2022.
Tiapkin Daniil, Belomestny Denis, Calandriello Daniele, Moulines Éric, Munos Remi, Naumov Alexey, Per- rault Pierre, Valko Michal, and Ménard Pierre. Model-free posterior sampling via learning rate random- ization. In Proceedings of the 37th Conference on Neural Information Processing System, 2023.
Jingliang Duan, Yang Guan, Shengbo Li, Yangang Ren, Qi Sun, and Bo Cheng. Distributional soft actor- critic: Off-policy reinforcement learning for addressing value estimation errors. IEFE Transactions Newral Networks and Learning Systems, pp. 6584 - 6598, 2021.
Jingliang Duan, Wenxuan Wang, Liming Xiao, Jiaxin Gao, and Shengbo Li. Dsac-t: Distributional soft actor-critic with three refinements. arXim:2310. 05555884 2023.
Mohamed Elsayed, Gautham Vasan, and A. Rupam Mahmood. Deep reinforcement. learning without expe- rience replay, target networks, or batch updates. 38th Workshop on Fine- Fine-Tuning in Machine Learning, NewrIPS, 2024.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymyr Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Tain Dunning, Shane Legg, and Koray Kavukcuoglu. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In Proceedings of the 35th International Conference on Machine Learning. PMLR, 2018.
Yannis Flet-Berliac, Johan Ferret, Olivier Pictquin, Philippe Preux, and Matthieu Gcist. Adversarially guided actor-critic. In Proceedings of the 9th International Conference Learning Representations, 2021.
Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In Proceedings of the 35th International Conference on Machine Learning. PMLR, 2018.
Tuomas Haarnoja, Aurick Zhou, Picter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proceedings of the 35th International Conference Machine Learning. PMI.R, 2018.
13

---

Published in Transactions on Machine Learning Research (02/2026)
Mikael Henaff, Roberta Raileanu, Minqi Jiang, and Tim Rocktäschel. Exploration via elliptical episodic bonuses. In Proceedings of the 36th Conference on Neural Information Processing System, 2022.
Mikael Henaff, Minqi Jiang, and Roberta Raileanu. A study of global and episodic bonuses for exploration in contextual mdps. Tn Proceedings of the 40th International Conference on Machine Learning. PML.R, 2023.
Shengyi Huang, Rousslan Fernand Julien Dossa, Chang Ye, Jeff Braga, Dipam Chakraborty, Kinal Mchta, and João G.M. Araújo. Cleanrl: High-quality single-file implementations of deep reinforcement learning algorithms. Journal of Machine Learning Research, pp. 1-18, 2022.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Yang Zhuoran, Zhaoran Wang, Doina Precup, and F. Lin Yang. Randomized exploration for reinforcement learning with general value function approximation. In Proceedings of the 38th International Conference Machine Learning, 2021.
Haque Ishfaq, Qingfeng Lan, Pan Xu, A. Rupam Mahmood, Doina Precup, Anima Anandkumar, and Kamyar Arizzadenesheli. Provable and practical: Efficient exploration reinforcement lcarning via langevin monte carlo. In Proceedings of the 12nd International Conference on Learning Regresenlations, 2024a.
Haque Ishfaq, Yixin Tan, Yu Yang, Qingfong Lan, Jianfong Lu, A. Rupam Mahmood, Doina Precup, and Pan Xu. More efficient randomized exploration for reinforcement learning via approximale sampling. In Proceedings of the 1st Reinforcement Learning Conference, 2024b.
Arthur Jacot, Franck Gabriel, and Clément. Hongler. Neural langent kernel: Convergence and generalization in neural networks. In Proceedings of the 32nd Conference on Newral Information Processing System, 2018.
Daniel Jarrett, Corentin Tallec, Florent Altché, Thomas Mesnard, Rémi Munos, and Michal Valko. Curiosity in hindsight: Intrinsic exploration in stochastic environments. In Proceedings of the 40th International Conference on Machine Learning. PMLR, 2023.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael 1. Jordan. Is q-learning provably efficient? In Proceedings of the 32nd Conference on Newral Information Processing System, 2018.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. In In Conference Learning Theory. PMLR, 2020.
Azizzadenesheli Kamyar and Anandkunar Animashree. Efficient exploration through bayesian deep q- networks. Information Theory and Applications Workshop, 2018
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 2002.
Heinrich Küttler, Nantas Nardelli, Alexander H. Miller, Roberta Raileanu, Marco Selvatici, Edward Grefen- stette, and Tim Rocktäschel. The nethack learning environment. In Proceedings of the 34th Conference on Neural Information Processing Systems, 2020.
Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, pp. 661-670, 2010.
Yexin Li, Zhaneun Mu, and Siyuan Qi. A contextual combinatorial bandit approach to negotiation. In Proceedings of the 41st International Conference Machine Learning, 2024.
Timothy Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Proceedings of the 4th International Conference Learning Representattons, 2016.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint orxiv 1312.5602u1, 2013.
14

---

Published in Transactions on Machine Learning Research (02/2026)
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonogiou, Helen King, Dharshan Kumaran, Daan Wierstral, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. nature, pp. 529-533, 2015.
Ian Osband, Van Benjamin Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In Proceedings of the 33rd International Conference on Machine Learning. PMLR, 2016.
lan Osband, Van Benjamin Roy, J. Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, pp. 1 61, 2019.
Deepak Pathak, Pulkit Agrawal, Alexci A. Efros, and Trevor Darrell. Curiosity-driven exploration by self- supervised prediction. In Proceedings of the 34th International Conference Machine Learning. PMLR, 2017.
Roberta Raileanu and Tim Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally- generated environments. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical compar- ison of bayesian deep networks for thompson sampling. In Proceedings of the 6th International Conference on Learning Represenlations, 2018.
Mikayel Sanvelyan, Robert Kirk, Vitaly Kurin, Jack Parker-Holder, Minqi Jiang, Eric Hambro, Fabio Petroni, Heinrich Kuttler, Edward Grefenstette, and Tim Rocktäschel. Minihack the planet: A sand- box for open-ended reinforcement learning research. In Proceedings of the 35th Conference on Neural Information Processing Systems, 2021.
K. Ramakrishnan Santhosh, Gokaslan Aaron, Wijmans Erik, Maksymets Oleksandr, Clegg Alex, Turner John, Undersander Eric, Galuba Wojeiech, Westbury Andrew, X. Chang Angel, Savva Manolis, Zhao Yili, and Batra Dhruv. mabitat-matterport 3d dataset (hm3d): 1000 large-scale 3d environments for embodied ai. arxiv preprint Xrxiv: 2109. 082.81288... 2021.
Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, Devi Parikh, and Dhruv Batra. Habitat: A platform for embodied ai rescarch. In In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimiza- tion algorithms. arXiv preprint ar 1707. 000700634770 7w2, 2017.
Jack Sherman and J. Winifred Morrison. Adjustment of an inverse matrix corresponding to a change in one element of given matrix. The Annals of Mathematical Statistics, 1950.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, and Timothy et al. Lillicapp. Mastering the game of go without human knowledge. Nature, 2017.
Michal Valko, Nathaniel Korda, Remi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv: 1309.6869., 2013.
Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H. Choi, Richard Powell, Timo Ewalds, and Petko et al. Georgiev. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 2019.
B. P. Welford. Note on method for calculating corrected sums of squares and products. Technometrics, 1962.
Zheng Wen, Branislav Kveton, and Azin Ashkan. Efficient learning in large-scale combinatorial mani-bandits. In Proceedings of the 32nd International Conference Machine Learning, pp. 1113-1122. PMI.R 2015.
15

---

Published in Transactions on Machine Learning Research (02/2026)
Puig Xavi, Undersander Eric, Szot Andrew, Dallaire Cote Mikael, Partsey Ruslan, Yang Jimmy, Desai Ruta, William Clegg Alexander, Hlavac Michal, Min Tiffany, Gervet Theo, Vondruš Vladimír, Berges Vincent-Pierre Turner John, Maksymets Oleksandr, Kira Zsolt, Kalakrishman Mrinal, Malik Jitendra, Singh Chaplot Devendra, Jain Unnat, Batra Dhruv, Rai Akshara, and Mottaghí Roozbeh. Habitat 3.0: A co-habitat for humans, avatars, and robots. arXiv preprint arv: 2310.137244 2023.
Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. In Proceedings of the 10th International Conference on Learning Representations, 2022.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I. Jordan. On function approximation in reinforcement learning: Optimism in the face of large state spaces. In Proceedings of the 34th Conference on Neural Information Processing System, 2020.
Wang Yiming, Yang Ming, Dong Renzhi, Sun Binbin, Liu Furui, and Hou U Leong. Efficient potential- based exploration in reinforcement learning using inverse dynamic bisimulation metric. In Proceedings of the 37th Conference on Neural Information Processing System, 2023.
Wang Yiming, Zhao Kaiyan, Liu Furui, and Hou U Leong. Rethinking exploration in reinforcement learning with effective mesric-based exploration bonus. In Proceedings of the 38th Conference on Neural Information Processing System, 2024.
Mingqi Yuan, Bo Li, Xin Jin, and Wenjun Zeng. Automatic intrinsic reward shaping for exploration in deep reinforcement learning. Tn Proceedings of the 40th International Conference on Machine Learning, pp- 40531 40554. PMLR, 2023.
Tom Zahavy and Shie Mannor. Neural linear bandits: Overcoming catastrophic forgetting through likelihood matching. arXiv preprint arXiv: 1901.0861 2v2, 2019.
Tianjun Zhang, Huazhe Xu, Xiaolong Wang, Yi Wu, Kurt Keutzer, Joseph E. Gonzalez, and Yuandong Tian. Noveld: A simple yet effective exploration criterion. In Proceedings of the 35th Conference on Newral Information Processing System, 2021a.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In Proceedings of the 9th International Conference Learning Representations, 2021b.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In Proceedings of the 37th International Conference on Machine Learning, pp. 11492-11502. PMLR, 2020.
16

---

Published in Transactions on Machine Learning Research (02/2026)
A
Implementation
Our experiments are based on the following open-source codcbases:
E3B (Henaff et al.
2022
CleanRL
Huang al.
2022
https:
DSAC Duan et al.
2021
2023
https:
Habitat-lab Andrew et al.
2021
Xavi et al. 2023 htte:///gtttukcccm//ooooooesesss
In Listing D we present the core code of CAE, while the rest of the deep RL algorithm remains unchanged.
As shown, CAE is simple to implement, integrates searllessly with any existing RL algorithm, and requires no additional parameter learning beyond what already in the RL algorithm.
Listing CAE core code
(A)
phi genet.get, _et_.nbb emb (torch. Tensor (oba), torch. Tensor (actien)). squeeze () detaac () agrt (torch. natmul (phi.T, reward +a acaled_bong bonus
(A_ inverve,,, iten
+- torch. torch.outer (phi, phi)
In Listing 2 we present the additional code of CAÉ+ alongside that of CAE. As shown, CAE+ minimizes an additional loss, specifically the Inverse Dynamics Network (IDN) loss, in addition to the losses from the original RL algorithm.
Listing Additional core code of CAE+
phi sennet.ge__eee (torch, (batch obbs ']), Tensor (default_actione
predict_action inverse_
idn_loss wwweerseddysnic.... de (phi (:-1), , phi (1:])
(pradict,
batch['actian [[:11])
def compute_invee inverse, Dess=F.nl__ba tog_ (action, dim--1), true_action, reduction- 'none 'none
htt.eiieeeeedeaiiieeeeeee dynanics lose (action, true_action);
return loss
17

---

Published in Transactions on Machine Learning Research (02/2026)
B
Long version of CAE
For more comprchensive thcoretical analysis, we present the theoretical version of CAE in Algorithm 3 where, for conciseness, we denote the embedding of the state-action pair at time step in episode m by Φ ( o4 WT) Following the standard notation the literature on provable algorithms (Jin et al. Yang et al, 2020), function parameters are assumed to be independent across different time steps H. J. and this convention also adopted in Algorithm 3 As shown in the algorithm, the paramcters 0n and Wh are updated iteratively to learn the two decomposed components of the action-value function in Equation via the Bellman equation. Specifically, 0₂ is updated in Line 9 using its closed-form solution (Li et al. 2010 while the embedding network o(,,- Wi.) is kept fixed. Subsequently, in Line 10, the embedding network o a Wi.) is updated with 0, held fixed. In this step, 7) denotes the learning rate, L% is the Bellman loss, and s/ o/ r for At E [m] denote the collected historical experiences.
2020
E
Algorithm 3 DQN (Mnih et al. 2015) enhanced with CAE
1: Input: Ridge parameter À 0, exploration parameter a 2 0, episode length H; episode number M, step size y, and the discount factor y
2: Initialize: Gram matrix A = MI, by = o, parameters 02 ~ 1N I), networkss Xu et al. 2022 Q) = Te,)))( (o, and the target netwersetworks Q Q2 for E [H]
3: for episode m = 1 to M do
4: Sample the initial state of the episode 8
5: for step h = 1, H do
Execute action d% arg maxa Q (si), a) and get the next state 144 and reward r
Compute the target value qhh"" = .h + 7 max. 2h+ (
8:
Update A Am+L ATT 2% (TT))) and b by + 9% "7
Update parameter 0% (A 1 1
10:
Update the embedding network to o(, (W by performing a gradient step W W WW Lg where
(ooTTo((,,, ((T") r --- max Q (st 1 (5)
LE
11:
Obtain UCB-based uncertainty
) 5 (5)) (W(:-IWa (AA -- w.m
12:
Obtain Thompson Sampling based uncertainty
1 N(O, (AT--))=1) 8 gm+l (.. (10 1 | (
13:
Approximate the action-value function
(..+) (0 ((. w a.gh a
14:
end for
15:
Update the target network Q @m+1 (.)) 2 gutt (..)))
16:
end for
Notably, Q (s a denotes the estimated value, whereas g. represents the corresponding target value at each time step h in episode m. By concatenating the values over all time steps h [H] and episodes m [M], we construct the estimated value vector ğ and the target value vector q of the action-value network, referenced in Theorem 1
18

---

Published in Transactions on Machine Learning Research (02/2026)
C Proof of Theorem
In this section, we analyze the cumulative regret bound of Algorithm 3 As U is straightforward lincar transformation of the embeddings, it approximately preserves the theoretical guarantees of UCB-based and Thompson Sampling- based exploration strategies, thereby maintaining the rigor of CAE+.
Before delving into the detailed thoory, we first review the notation used this appendix. Let denote the true optimal policy, and let Tm denote the policy execuled in episode E [M]. More generally, for any policy-illustrated here with Rm the relationship between the action-value function Q"' and the corresponding maximun return V*m can be expressed by:
T (s) = max QTTT! (s, (s)
(15)
Qh (8, (n( a) + E (e Vir (8141)
(16)
In Algorithm the estimated action-value function at step h in episode m is denoted by Q (8, (,,)), with the corresponding state-value function represented as VAT (s). For clarity of presentation, introduce the following additional notations.
(s8 4x) = B -FN V Vh+1
(17)
8% (8% th 0 = + (PA V (8 ax) - 17 (5% ah
(18)
5 VIn (sh) - -( (5%,
m ,aaa)))))) - Qh (s% a%)
(19)
ch (Px 1) a (P VTTT (sT [
(va (s Vii (8%
(20)
Specifically, 0% (8% a represents the temporal-difference error for the state-action pair (s) a.)) The notations 5ht and Ex capture two sources of randomness, Le., the selection of action aj ~ Tea (1s5)) and the generation of the next stale nn #+1 Pn(-lom, a from the environment.
Proof. Theorem
Based on Lemma the cumulative regret in Equation 13 can be decomposed into three terms as follows,
where (5)) means the inner product of two vectors.
Ras
Σg (1 uT -Q"" """" aT")
m=1
и
Ey (sh, an)ss: ss7'] 8%% an
(C + Eh
h=1
M H
Ex 11T 1), (-188) T. T. (-18x)) 181 = -7
According the definition of Tms there is Equation 21
(Q (sh, +), (-1s) Fm (-Isw))
(21)
19

---

Published in Transactions on Machine Learning Research (02/2026)
Consequently, with probability at least for (0, 1), the cumulative regret in Equation 13 can be bounded as follows.
M
RM S
Ex- joh (Sh, an)|si = sq"] -6% 0%' (sh oh
CC + En )
(22)
Ex- (6% (Sh, an)|s= si"] 5% (5h oh
16M
01
SAH V MH log 2 + Cratt
M
MD log(1 +
AD
Cs HLLDDMM M
1 log clog
log
MIAl) 02
11q Ell--
02
16MH 2
46
M CaHLLDåM log log ( log MIAA 11g
q H-1
SCiH MH log CzaHl y MD LID-log(1+ +
XD
Here, 01,02 E (0, Specifically, the second inequality follows from Lemma 2 and the third inequality follows from Lemma By setting 01 02 and applying union bound, the result holds after absorbing constant factors into C2. Cz. and C4.
D Lemmas
Lemma 1. Adapted from Lemma 5.1 of Yang et al. (200)). the regret in Equation 13 can be decomposed as Equation 23 where ( means the inner product of two vectors.
M Σ
R
Qi "T" - Q (sT,, "T"
m=1
M
(6T)
1iTT (8T")
m=1
Σ
Exg [6 (sh, as) = =s -8,
-8% (5
(CT + 6%
(23)
M
H
E [12)" (8h, 1) (=(ss)) T.. (.18n)) 181 = s
Lemma 2. Adapted from Lemma 5.3 of Yang al. (2020), with probability at least σ1, the second term in Equation 22 can be bounded follows:
2 16MH
Σ
E + <
(24)
01
Lemma 3. For any 02 E (0, 1), assume the width of the action-vale network satisfies:
M|A
= poly(L (1, D, log
(25)
a2
20

---

Published in Transactions on Machine Learning Research (02/2026)
where L is the number of layers in the action-value network, and poly(.) means polynomial function depending on the incorporated variables, and let:
M log|A!
a= 1 2(D-Log(1 log(1 +
- log 02) + VA
(26)
A
n s Ci(l. D²M L log M|
(27)
02
then with probability at least 52, the first term in Equation
22 is bounded as:
Er 16% (sh, 08)]81 = x]") 8% (8% aF
(28)
A=1
2 MHllg log
M
C3 HLL M log log (1))
log
(MIA)
119
4 H-
SAH MH
Cratt
MD log(1 +
+
02
XD
67
Proof. According to
Yang et al.
2020 there is:
Em- 16% (sh, a1) = =s"]]
6% (5% 1o%%aa aa
Σ
Σ
8 (5h ah
(29)
k=1
Considering (5% af), , can be decomposed as:
0% (S a. - (PAVH h+ (S a. Q (5% a.
(30)
= + (Px V axh
(7 + Q7 ( a/
Q a
-P Vi++n 0% + (Q) Q7 (5 kx
(V
Vh+1 (5 0% (V Vh (s
(V/41 V*+1) + (Q) Q (s a%
Ph11
By Azuma-Hoeffding inequality, bound ΣM Elr A= with Equation - 0g where E (0, 1).
31
with probability at least
2 2H MH log
Σ
Σ
wh < 2H
2 MH MH log
(31)
σ3
σ3
==
h=1
As Ph+ be decomposed as Equation
32 where wff (- there is Equation
33
21

---

Published in Transactions on Machine Learning Research (02/2026)
Ph+1
(V
Vh+1)(0741) Qh+ 00+1(6h+1: (h+1)) (0+11
(32)
M
Phit1 + +
(33)
1=1
M M-
M
Q (s (.+1 - 1 2 ]]
+
QQ
2hh ,
h=1
m2
h=1
M
Qhish: x Q%( 2h
Σ
(34)
M=
2=
==
RMAB
Specifically, the second equation follows from QH+1
( H+1, #+++,:#+1 = 0 and ( # = 0. The
second term in Equation 34 originates from the estimation error of the action-value function, which is constrained by the convergence properties of DQN. Consequently, to complete the proof Lemma 3 it suffices to establish bound for the RMAB term, while the second term is omitted for conciseness in the remaining discussion. Bounds of RMAB under UCB- and Thompson Sampling- based exploration strategies are proved in Lemma and Lemma 5 respectively.
By setting C2 max C 03 04 2, applying union bound, and absorbing constant factors into C2 and C3. the proof is completed.
D.1 Regret Bound of UCB-based Exploration
In this subsection, we first introduce the third assumption from deep representation and shallow explo- ration [Xu et al. 2022). which, with Assumptions and forms the standard assumptions. We then present Lemma
Assumption 3. For Vss, 52 E S and Vai, ag E A, there is constant lepp > O, such that:
V wh) V a2 w s Liip (1(11;))) - (52:
(35)
Lemma 4. Adapted from Theorem 4.4 of Xu et al. (202)), suppose the standard initializations and assump- tions hold. Additionally, assume without loss of generality that ||0' S and [ an)llz S 1. If with the UCB-based exploration stralegy, then for any 44 (0, 1), let the width of the action-value network satisfies:
1 L= poly(L,, D, - log MIA
log
(36)
04
where the number of layers in the action-value network, and poly(.) means a polynomial function depending on the incorporated variables, and let:
a 1 2(D log(1 + M log/AA
log + VT
(37)
M|A -1
S. Ci(c. 4 1 log
(38)
a4
22

---

Published in Transactions on Machine Learning Research (02/2026)
then with probability at least Ja, the term RUCB in Equation 34 be bounded as follows:
CaHL M v log log (2) log M (MaA) llq Fl
M AD
RUCB SCucb oH MD log(1 +
(39)
et
where C1 Cucb. C3 are constants independent of the problem parameters; q = (qi: qb:... g.i....: : qll and i = (Q](s), o.): Qu (s) a ( )) are the largel and estimated value veclors, respeclively.
Notably, the proof of the above lemma relies on the concentration self normalzeddd stochastic processes. However, since Qh not independent of historical data, this result cannot directly applied. Instead, similar approach to that in Yang al. (2020) is adopted by leveraging Uniform Convergence across all possible inputs within the value function class Q. This ensures that. the maximum deviation between the true and learned values over all time steps remains small, i.e., suporee 1Q - Q S 6m for Ah [M]. Crucially, the error fm decreases the nunber of episodes increases. Applying triangle inequality, decompose the error bound RUCB into two terms to manage the dependency:
A true optimal value function component, to which the concentration of self-normalized stochastic pro- cesses applies.
A cumulative error term dependent on cms which can be systematically bounded.
D.2 Regret Bound of Thompson Sampling- bassd Exploration
Lemma 5. Under the same settings as those of Lemma 4 if with the Thompson Sampling-bass basedd exploration
strategy, the term RThompson Sampling in Equation 34 con be bounded as Equation 40 where Cts constant.
R Thompson Sampling <Cno aH MD log(1 + C2HLED& M log c llog
log (1))
MMAl 44
l|4
M
AD
(40)
166
2022 there exits W such that (7 u) - Q2 a) can be decomposed as Equation 41 where g(8, a; W) Vwols, W).
Proof. According to Lemma A.1 Xu et al.
Q7(s, u) - (s)a)
(41)
=(0)) (Ø(s, u: W - o(s W. + (0)) [g(s, u; W;:) - g(s, a; wh)) (W w
= [g(s, u: w - g(s.((sss W W - W
+ ) (0(s, u: W o(s W -00 - ON) [ø(s, u; W.") - o(s, Wi))
Based on the action selection process using Thompson Sampling based exploration strategy in Algorithm derive Equation 42
OO + aAO T WxT) < (0 + Taa0m) b(s, WT))
(42)
Consequently, for any as (0, 1), with probability at least. 1 as, the term 0h is bounded Equation
43
23

---

Published in Transactions on Machine Learning Research (02/2026)
0% < | Am |0(s, W - ő(s, (ap)-
(43)
S(VD + v 2 -
1lo(s, Ó(s, un W (aa)))
55
Specifically, the last inequality above is because A ~ (AK)) Substituting the bound of 0% back into Equation 41 further yields:
()(s,))- - (x, ((0)) [g(s, u; w g(s, a; w])] (w - W
(44)
+ (VD V 2 1 |lo(s, a: W - ((s, u; W ((ag))))))
(0 0%) (6(8, us WTT)
W
Comparing Equation 44 with Equation A.7 of Xu (0022). the difference between the regrets of the
Thompson Sampling based and UCB-based exploration strategics is bounded as in Equation 45
Thompson Sampling
RUCBI
H (VD + 2log O5
110(8% 0x W.t)) 6(8% ux W (((ay)>)
m= h=1
M
M H
111(8h 0g W (l()))
a || u WT (((g))
m=
A=1
m=1 h=1
M
<CgaH MD log(1+
(45)
AD
Setting Cts Cueb + Cs completes the proof.
Notably, the above proof applies a union bound, which requires assigning a constant to a in Equation 37 For brevity, we omit the allocation of this constant and the corresponding discussion of the failure probabilities.
D.3 Discussion about the Standard Assumptions
Assumption ! can be readily satisfied by transforming the state action pairs (s; into (s; a; 8; a) and applying appropriate scaling.
Assumption 2 is mild condition. Specifically, prior studies have demonstrated that for two-layer RcLU networks, this assumption can be directly derived from Asumption [ A diverse input distribution and a wide neural network can largely ensure that remains positive definite.
Assumption 3 holds when the gradient of the neural network with respect certain weights does not fluctuate excessively. In other words, within neighborhood of given aatteacction pair, the gradient with respect to these weights remains well-controlled. This is standard assumption in the non-convex optimization literature, commonly used to ensure the convergence of alternating optimization procedures in which parameters are updated iteratively.
24

---

Published in Transactions on Machine Learning Research (02/2026)
175
3500
6000
150
3000
5000
2500
4000
100
2000
75
3000
1500
50
2000
1000
25
DSAC
DSAC
1000
DSAC
DSAC CAE
500
DSAC CAE
DSAC CAE
0
0.25
0.50
0.75
1.00
1.0
0.25
0.50
0.75
1.00
(a) Swimmer
(b) Hopper
(c) Walker2d
7000
250
SAC
8000
5000
SAC CAE
200
CAE scaling
5000
4000
3000
100
3000
2000
2000
SAC
50
1000
DSAC
SAC + CAE
1000
DSAC CAE
CAE scaling
0.25
0.50
0.75
1.00
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
(d) Ant
(e) Walker2d
(f) Swimmer
Figure 4: Experimental results of DSAC MuJoCo-v3, iee., from Figure 4a to Figure ablation study to the scaling strategy MuJoCo-v4, de., Figure 4el and Figure
4d and those of
41
E
Experiment
In this section, we present additional experimental results and provide the hyperparameters used to reproduce the experiments reported in this paper.
E.1 Experiment on Mujoco
Ablation study to the scaling strategy. We conduct experiments to assess the necessity of the scaling strategy. Experiment results, illustrated Figure 4e and Figure 4i are based on randomly selected tasks for SAC. As shown, SAC enhanced with CAE fails to deliver satisfactory performance on Walker2d and Swimmer tasks when the scaling strategy not applicd. achieves high performance under certain seeds, while it performs poorly under others, leading to poor overall results and large variance. This highlights the critical role of the scaling strategy in ensuring the practical stability and effectiveness of CAE.
Hyperparameters of various RI. algorithms for the experiments on MuJoCo are completely the same those in the public codebase CleanRL. CAE introduces only two more hyperparameterrs, i.e., the exploration coefficient a and the ridge which set as = Exploration coefficients are summarized Table 7 for various tasks and algorithms, and the experimental results on various MuJoCo tasks involving different RL algorithms are Figure 4 and Figure 5 Notably, we only present results for cases where the RPI exceeds 5. 5.0%, as smaller RPT is not clearly distinguishable in the figures.
25

---

Published in Transactions on Machine Learning Research (02/2026)
Table 7: Exploration coefficient for various MuJoCo tasks and algorithms
Algorithms
SAC
PPO
TD3
DSAC
Env
Swimmer
0.2
0.1
0.1
Ant
0.2
1.0
Walker2d
1.0
0.13
0.8
3.0
Hopper
0.4
0.14
0.3
2.0
HalfCheetah
0.4
0.5
3.7
3.0
Humanoid
4.0
0.1
4.5
E.2 Experiment on MiniHack
In Subsection 5.2 we evaluate our methods CAE and CAE+ on nine representative MiniHack tasks, whose detailed descriptions are provided in Table
Table 8: Minillack tasks evaluated in Subsection 5.2
Short names in Subsection 5.2
Full names
Task types
N4
MultiRoom-Ne
Locked
MultiRoom-N4 N4- Locked
N6
MultiRoom-NV
Navigation-bused
N6-Locked
MultiRoo--66-Lockee
N10-OD
MulliBoom-N1O-OpeeDDDD
Horn
Freeze Rest-retreee
Random
Skill-based
Wand
Freeze-
LavaCross
LavaCros-Reesrictee
The hyperparameters for IMPALA, E3B, CAE, and CAE+ used in our experiments are summarized in
Table and Table [0] aligning with those from the E3B experiments (Henaff et al. 2022). The experimental results on MiniHack are presented in Figure B
Table IMPALA Hyperparameters for MiniHack Henall et al.
2022
Learning rate
0.0001
RMSProp smoothing constant
0.99
RMSProp momenttum
RMSProp
10
Unroll length
80
Number of buffers
80
Number of learner threads
4
Number of actor threads
Max gradient norm
Entropy cost
0.0005
Baseline cost
0.5
Discounting factor
0.99
26

---

Published in Transactions on Machine Learning Research (02/2026)
Table 10: E3B, CAE, and CAE+ Hyperparameters for MiniHack
Scaling strategy
True
Ridge regularizer
0.1
E3B, CAE, and CAF+
Entropy Cost
0.005
Exploration coellicient
CAE+
Dimension of U
128 256
E.3
Experiment on Habitat
The hyperparameters for PPO, E3B, CAE, and CAE+ used in these experiments are summarized in Table [1 and Table I2
Table 11: PPO Hyperparameters for Habilat adopted from habital-lab
(Savaa al. 2019 Andrew al.
2021
Xavi et al. 2023
Clipping
0.2
PPO epoch
4
Value loss coefficient.
0.5
Entropy coefficient
0.01
Learning rate
2.5e 4
<-greedy
le-5
Max gradient norm
0.2
Rollout steps
128
Use GAE
True
Discounting factor
0.99
Number actor threads
16
Table 12: E3B, CAE, and CAE+ Hyperparameters for Habitat
Scaling strategy
False
Ridge regularizer
0.1
E3B, CAE, and CAE+
Inverse Dynamics Model updates per PPO epoch
Exploration coefficient
0.1
CAE+
Dimension of U
256
F
Limitations
One limitation of the proposed method is that, despite the small number of additional trainable parameters, computing the uncertainty incurs a non-negligible computational overhead due to the need for matrix inver- sion. This can be mitigated by using approximation techniques, such as the Rank-1 method described Subsection 3.3 Additionally, other linear MAB methods could be integrated into the proposed framework to avoid the need to calculate the inverse Gram matrix.
27

---

Published in Transactions on Machine Learning Research (02/2026)
12000
10000
200
5000
8000
4000
6000
3000
100
4000
2000
50
2000
SAC
SAC
1000
SAC
SAC CAE
SAC CAE
SAC CAE
0.00
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
1.0
(a) HalfCheetah
(b) Swimmer
(c) Ant
7000
3500
5000
6000
3000
4000
2500
3000
4000
2000
3000
1500
2000
2000
1000
SAC
1000
SAC
TD3
500
SAC CAE
SAC CAE
1000
TD3 CAE
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
3
(d) Hopper
(e) Walker2d
(f) Humanoid
6000
3500
5000
3000
150
4000
2500
2000
3000
100
1500
2000
1000
50
TD3
1000
TD3
TD3
500
TD3 CAE
TD3 CAE
TD3 CAE
0
0
0.25
0.50
0.75
1.00
0.25
0.50
0.75
1.00
0.2
0.4
0.8
1.0
(x) Swimmer
(h) Ant
(1) Hopper
5000
3000
4000
100
2000
3000
80
2000
60
1000
1000
40
TD3
PPO
TD3 CAE
PPO + CAE
PPO CAE
0
20
0.2
0.4
0.6
0.8
1.0
0.25
0.50
0.75
1.00
0.2
0.4
0.6
0.8
1.0
(i) Walker2d
(k) Swimmer
(I) Ant
Figure 5: Experimental results on MuJoCo-v4.
28

---

Published in Transactions on Machine Learning Research (02/2026)
1.00
1.00
1.0
0.75
0.75
0.50
0.5
0.25
0.25
0.00
0.00
-0.25
-0.5
-0.25
E3B 65%
E3B 65%
E3B 65%
-0.50
CAE+ 0.8%
-0.75
CAE 0.8%
-1.0
CAE+ 0.8%
-0.75
0.5
1.5
2.0
1.5
2.0
1.5
(a) Nulv
(b) MullaRoooo-NLLockeeeeu
(c) MultiRoon-N6-v0
1.0
E3B 65%
1.0
CAE 0.8%
0.5
0.5
0.5
0.0
0.0
0.0
-0.5
-0.5
-1.0
-1.0
E38 65%
-1.0
E3B 65%
-1.5
CAE+ 0.8%
CAE+ 0.8%
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
(d) CaltiRooom-N-LLooeedee
(e) MultiRoom--N10-ppnn
(f) Preeze-Horns Host--errrreeeed--
1.00
0.5
0.5
0.75
0.0
0.50
0.0
0.25
0.5
0.00
11.0
-0.25
-1.0
E3B 65%
-1.5
E3B 65%
-0.50
E3B 65%
CAE+ 0.8%
-2.0
CAE+ 0.8%
-075
CAE+ 0.8%
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
0.5
1.0
1.5
2.0
g Freeze- Random- Restricted-v0
(h) Freeze- WWand-Restricted
(i) LavaCross Restricted
LavaCross-Restrictee
Figure 6: Experimental results on MiniHack.
29


Reviews:
[{"review_id": "9g5uwWBnVa", "reviewer": "Reviewer_pnds", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors look to model the uncertainty in estimating the action-value network parameters - the goal is to aid exploration by taking up actions which have not been explored yet until that point. To do so, the authors take inspiration from the literature of MAB and model the uncertainty as done for linear MAB's. The authors provide two algorithms - CAE and CAE+, both of which are efficient and hardly introduce any additional parameters to incorporate the uncertainty/exploration into the model. Extensive experiments are shown with and without CAE for several existing algorithms to validate the updated algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims look good to me - I did not find any glaring issue", "audience_yn": "Yes", "audience_explanation": "Yes, the uncertainty based updated RL algorithms are important for the community", "requested_changes": "Here are my questions/suggested changes for this paper (the paper has been written very well by the way)\n\n1. It would be good to explain more regarding the uncertainty in linear bandits and why it is an approximation for this case. For instance, the uncertainty is derived theoretically only if W is fixed for calculating the embeddings - that is to capture the uncertainty in $\\theta$. \n\n2. Algorithm 1 needs 4 parameters and yet, when it is invoked in Algorithm 2, the parameters are not provided clearly - this led to confusion. Can the authors also provide intuition on why this scaling is necessary in RL algorithms and not in linear bandits? \n\n3. Why is the model for learning the action probabilities (equations 8,9) leading to the uncertainty definition in equation 10? This is a connection I failed to understand. Is the authors somehow saying that the embeddings are projected into a different space via U and hence it is captured in the uncertainty? However, U does not come into the picture for learning the Q function - hence my confusion. Also  Line 14 in Algorithm 2 needs to be expanded (Q function is updated how?) - why does $min(L_f, L_b)$ make sense? \n\nOverall the formulation in CAE+ confused me significantly\n\n4. In the experiments, did the authors compare with random exploration or $epsilon$-greedy or by injecting noise into the actions?", "broader_impact_concerns": "None", "additional_comments": "Please see my clarification questions in the section for requested changes", "extra_scores": {}, "extra_text": {}}, {"review_id": "xhLlSXnpTm", "reviewer": "Reviewer_xgnH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes Critic as Explorer method, CAE, which repurposes the embedding layers of value networks to compute exploration bonuses using linear MAB techniques. CAE claims to require ~10 lines of code and no extra parameters. For sparse-reward tasks, CAE+ adds a tiny inverse-dynamics network (<1% additional parameters). The method was evaluated on MuJoCo, MiniHack, and Habitat, reporting big improvements over multiple base algorithms and SOTA exploration methods such as E3B.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper is well-organized with both numerical experiments and theoretical analysis.\nThe benchmarks are relatively comprehensive.", "audience_yn": "Yes", "audience_explanation": "The method is easy to implement with minimal additional coding and extra parameters. It potentially has high practical value.", "requested_changes": "1. Add results about the computational cost of CAE.\n2. Explicitly discuss the assumptions in the proof, instead of saying “standard assumptions from the literature”.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "oV5x6eF70g", "reviewer": "Reviewer_fQk7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes CAE and CAE+, two lightweight exploration modules that adapt linear MAB techniques to deep RL by leveraging the critic’s learned representation. The methods require minimal additional computation and come with a theoretical regret guarantee. Extensive experiments across MuJoCo, MiniHack, and Habitat, with some competitive baselines, show strong empirical performance.\n\nStrengths:\n\n1. Provides a theoreticalregret bound, with practical applicability.\n\n2. Simple, low-overhead design that integrates easily with existing algorithms.\n\n3. Strong empirical results across diverse environments.\n\nWeaknesses:\n\n1. Conceptual novelty is somewhat limited, as the core idea resembles prior UCB/uncertainty-based exploration methods.\n\n2. Some comparisons (e.g., Table 1) appear overly categorical and would benefit from clearer justification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Overall, most of the main claims are supported by reasonable evidence. The theoretical regret analysis is clearly stated and appears technically sound, and the empirical evaluation is extensive, covering diverse environments with strong baselines. The experimental results consistently support the performance claims. However, some of the comparative statements (eg. Fig 1) are not fully justified and may overstate differences from prior methods. Despite these minor issues, I believe the core claims are generally well supported.", "audience_yn": "Yes", "audience_explanation": "Yes. Exploration in deep reinforcement learning remains a central challenge, and methods with both theoretical guarantees and practical efficiency should be in an interest in the TMLR community.", "requested_changes": "1. Clarify the criteria used in Table 1.\nAlthough the table provides brief textual definitions of “Linearity,” “Network,” “Deep,” and “Low-overhead,” it is not clear how these criteria were operationalized when assigning ✓/✗ to each method. \n\nFor example, NN-UCB employs neural feature extractors, yet is marked as “Deep = ✗”. \n\nAnd for BDQN (and maybe ACB,  LMCDQN), the “Low-overhead = ✓” entry is questionable. The method relies on ensemble architectures, which will incur additional computational cost. It is unclear why it is classified as low-overhead.", "broader_impact_concerns": "I did not identify any further concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)