A Theoretical Justification for Asymmetric Actor-Critic Algorithms
Authors: Gaspard Lambrechts
Damien Ernst
Aditya Mahajan
Venue: ICML 2025 poster (2025)
Keywords: Partially Observable Environment
Asymmetric Learning
Privileged Information
Privileged Critic
Convergence Analysis
Asymmetric Actor-Critic
Finite-Time Bound
Agent-State Policy
Aliasing
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We derive a finite-time bound for an asymmetric actor-critic algorithm and compare it with the symmetric counterpart, offering a justification for the effectiveness of asymmetric learning

Abstract: In reinforcement learning for partially observable environments, many successful algorithms have been developed within the asymmetric learning paradigm. This paradigm leverages additional state information available at training time for faster learning. Although the proposed learning objectives are usually theoretically sound, these methods still lack a precise theoretical justification for their potential benefits. We propose such a justification for asymmetric actor-critic algorithms with linear function approximators by adapting a finite-time convergence analysis to this setting. The resulting finite-time bound reveals that the asymmetric critic eliminates error terms arising from aliasing in the agent state.

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
Gaspard Lambrechts 1*
Damien Ernst
Aditya Mahajan 2
Abstract
tional RL approaches have thus been adapted by considering history-dependent policies, usually with recurrent neural network to process histories (Bakker, 2001; Wierstra et al., 2007; Hausknecht & Stone, 2015; Heess et al., 2015; Zhang et al., 2016; 6; Zhu et al., 2017). Given the difficulty of learn- ing effective history-dependent policies, various auxiliary representation learning objectives have been proposed to compress the history into useful representations (Igl et al., 2018; Buesing et al., 2018; Guo al., 2018; Gregor et al., 2019; Han et al., 2019; Guo et al., 2020; Lee et al., 2020; Subramanian et al., 2022; Ni et al., 2024). Such methods usually seek to learn history representations that encode the belief, defined as the posterior distributions over the states given the history, which is sufficient statistic of the history for optimal control.
In reinforcement learning for partially observable environments, many successful algorithms have been developed within the asymmetric learning paradigm. This paradigm leverages additional state information available at training time for faster learning. Although the proposed learning objectives are usually theoretically sound, these methods still lack precise theoretical justifi- cation for their potential benefits. We propose such justification for asymmetric actor-critic al- gorithms with linear function approximators by adapting finite-time convergence analysis to this setting, The resulting finite-time bound reveals that the asymmetric critic eliminates error terms arising from aliasing the agent state.
While these methods are theoretically able learn optimal iietory-dependent policies, they usually learn solely from the partial state observations, which can be restrictive. In- deed, assuming the same partial observability at training time and execution time can be too pessimistic for many environments, notably for those that are simulated. This mo- tivated the asymmetric learning paradigm, where additional state information available at training time is leveraged dur- ing the process of learning a history-dependeer policy. Al- though the optimal policies obtained by asymmetric learning are theoretically equivalent to those learned by symmetric learning, the promise of asymmetric learning is to improve the convergence speed. Early approaches proposed imi- tate a privileged policy conditioned on the state (Choudhury et al., 2018 8), the state (Pinto et al., 2018). These heuristic methods initially lacked a theoretical framework, and a recent line of work has focused on proposing theoretically grounded asymmetric learning objectives. First, imitation learning of a privileged policy was known to be suboptimal, and it was addressed by constraining the privileged policy so that its imitation results in an optimal policy for the partially observable environment (Warrington et al., 2021). Simi- larly, asymmetric actor-critic approaches were proven to provide biased gradients. and an unbiased actor-critic ap- proach was proposed by introducing the history-state value function (Baisero & Amato, 2022). In model-based RL, sev- eral works proposed world model objectives that are proved to provide sufficient statistics of the history, by leveraging
1. Introduction
Reinforcement learning (RL) is appealing framework for solving decision making problems, notably because it makes very few assumptions about the problem at hand. In its purest form, the promise of an RL algorithm is to learn an optimal behavior from interaction with an environ- ment whose dynamies are unknown. More formally, an RL algorithm aims to learn a policy which is defined as mapping from observations to actions from interaction samples, in order to maximize a reward signal. While RL has obtained empirical successes for plethora of challeng- ing problems ranging from games to robotics (Mnih et al., 2015; Schrittwieser et al., 2020; Levine et al., 2015; Akkaya et al., 2019), most of these achievements have assumed full state observability. A more realistic assumption is partial state observability, where only a partial observation of the state of the environment is available for taking actions. In this setting, the optimal action generally depends on the complete history of past observations and actions. Tradi-
use an asymmetric critic conditioned
"Work done at McGill University and Mila Québec. 'oontefirre Institute, University of Liège 'Department of Electrical and Com- puter Engineering, McGill University. Correspondence to: Gas- pard Lambrechts <gaspard. @ uliege.be>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
the state (Avalos et al., 2024) or arbitrary state information (Lambrechts et al., 2024). Finally, asymmetric representa- tion learning approaches were proposed to learn sufficient statistics from state samples (Wang et al., 2023; Sinha & Ma- hajan, 2023). It is worth noting that many recent successful applications of RL have greatl benefited from asymmet- ric learning, usually through an asymmetric critic (Degrave et al., 2022; Kaufmann et al., 2023; Vasco al., 2024).
are studied. In Section 4, we provide the finite-time bounds for the asymmetric and symmetric actor-critic algorithms. Finally, in Section 5, we conclude by summarizing the con- tributions and providing avenues for future works.
2. Background
In Subsection 2.1, we introduce the decision processes and agent-state policies that are considered. Then, we introduce the asymmetric and symmetric Q-function for such policies, in Subsection 2.2 and Subsection 2.3, respectively.
Despite these methods being theoretically grounded, in the sense that policies satisfying these objectives are optimal policies, they still lack a theoretical justification for their potential benefit. In particular, there is no theoretical justifi- cation for the improved convergence speed of asymmetric learning. In this work, we propose such a justification for an asymmetric actor-critic algorithm, using agent-state policies and linear function approximators. Agent-state policies rely on an internal state, which is updated recurrently based on successive actions and observations, from which the next action is selected. This agent state can introduce aliasing, a phenomenon in which an agent state may correspond to two different beliefs. Our argument relies on the comparaison of two analogous finite-time bounds: one for a symmetric natural actor-critic algorithm (Cayci al., 2024), and its adaptation to the asymmetric setting that we derive in this paper. This comparison reveals that asymmetric learning eliminates error terms arising from aliasing in the agent state in symmetric learning. These aliasing terms are given by the difference between the true belief (i.e., the posterior distri- bution over the states given the history) and the approximate belief (i.e., the posterior distribution over the states given the agent state). This suggests that asymmetric learning may be particularly useful when aliasing is high.
2.1. Partially Observable Markov Decision Process
A partially observable Markov decision process (POMDP) is a tuple P (S, A,, R, 0,y), with discrete state space S, discrete action space A. and discrete observation space O. The initial state distribution P gives the prob- ability P(so) of 8g E being the initial state of the deci- sion process. The dynamics are described by the transition distribution T' that gives the probability T St+1 S being the state resulting from action a E A in state 8, E S. The reward function R gives the immediate re- ward r, at St+1) of the reward re E [0. 1] resulting from this transition. The observation distribution O gives the probability (o))(ss) to get observation or E O in state 8t E. Finally, the discount factor y E [0. 1) weights the rel- ative importance of future rewards. Taking a sequence of t actions in the POMDP conditions its exccution and provides the history h (oo, ao.... .r) H. where H. is the set of histories of arbitrary length. In general, the optimal policy in a POMDP depends on the complete history.
of
However, in practice it is infcasible to learn a policy condi- tioned on the full history, since the latter grows unbound- edly with time. We consider an agent-state policy M that uses an agent-state process M= (Z,U), in order to take actions (Dong et al., 2022; Sinha & Mahajan, 2024). More formally, we consider discrete agent state space 2, and an update distribution U that gives the probability U (z++ Izt, ae. 0(+1) of Z++1 E Z being the state resulting from action a, E A and observation o;- 1 E in agent state 24 E Z. Note that the update distribution U also describe the initial agent state distribution with = & 2 the null agent state and a & A the null action. Some examples of agent states that are often used are a sliding window of past ob- servations, or a belief filter. Aliasing may occur when the agent state does not summarize all information from the history about the state of the environment, see Appendix for an example. Given the agent state 2;, the policy ι sam- ples actions according to a, ~ (-122)). An agent-state policy n" E IIM is said to be optimal for an agent-state process M if it maximizes the expected discounted sum of rewards: nT" E Earg mexx ((T) with J(T) = -ET I 1dt Rt).
A recent related work proposed a model-based asymmet- ric actor-critic algorithm relying on belief approximation, and proved its sample efficiency (Cai et al., 2024). It also considered agent-state policies, and studied the finite-time performance by providing a probably approximately cor- rect (PAC) bound, instead of an expectation bound as here. While the algorithm was restricted to finite horizon and discrete spaces, notably for implementing count-based ex- ploration strategies, it tackled the online exploration setting and its performance bound did not present concentrability coefficient. This related analysis thus provides a promising framework for future works in a more challenging setting. However, it did not study the existing asymmetric actor- critic algorithm, and did not provides a direct comparison with symmetric learning. In contrast, we focus on providing comparable bounds for the existing model -free asymmetric actor-critic algorithm and its symmetric counterpart.
In Section 2, we formalize the environments, policies, and Q-functions that are considered. In Section 3, we introduce the asymmetric and symmetric actor-critic algorithms that
2

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
In the following, we denote by St. O Zz Ar and R the ran- dom variables induced by the POMDP P. Given POMDP P and an agent-state process M, the initial environment- agent state distribution Pis given by,
state and agent state (S,, Ze) are Markovian. Therefore, it can be shown that the fixed point @ the same as the asymmetric Q-function º
2.3. Symmetrie Q-function
P(,0, = P(00)
Σ OBEO
(1)
The symmetric Q-function Q of an agent-state policy и e M POMDP P is defined as the expected discounted of rewards, starting from agent state and action a, and using policy afterwards,
Furthermore, given an agent-state policy M.,, we define the discounted visitation distribution as,
d' (x,=)=
Σ
P( z0)
00
50.50
(=(xaa)=E" E" Σ 2 Zo = Ao =0
(6)
y =5, 20
-0)
The symmetric value function V/8 of an agent-state policy π II defined as -xx)==nne T (<a=))"" We also define the symmetric advantage function A (²,za) (²,zza) (z).
Finally, we define the visitation distribution m steps from the discounted visitation distribution as,
d (s, Σe d' (S0,
(3)
#0,20
Let us define the m-step symmetric Bellman operator as,
x Prr(Sm=ms22 = 2 su, Zo = 20)-
In the following, we define the various value functions for the policies that we defined. Note that we use calligraphic letters Q", V and A for the asymmetric functions, and regular letters Q V and A for the symmetric ones.
Q" (2(2a==EE')
E
Σ t=0
/ + "0" (Zm: Am)
7o = 2, Ao
(7)
It can be verified that the m-step symmetric Bellman opera- tor is -m"ttottractvve. Therefore, equation (7) has unique fixed point Q". However, because the agent state is not necessarily Markovian, in general Q #Q"
2.2. Asymmetric Q-function
Similarly to the asymmetric Q-function of Baisero Am- ato (2022), which conditioned on (s, h, a). we define an asymmetric Q-function that we condition on (s,2,0) where is the agent state resulting from history h. The asymmetric Q-function Q" of an agent-state policy π IIM is defined as the expected discounted sum of rewards, starting from environment state s, agent state and action and using policy π afterwards,
3. Natural Actor-Critic Algorithms
In this section, we present the asymmetric and symmetric natural actor-critic algorithms,, which make of actor, or policy, and a critic, or Q-function. The asymmetric vari- ant will use an asymmetric critic, learned using asymmetric temporal difference learning, while the symmetric variant will use a symmetric critic, Iearned using symmetric tempo- difference learning. These temporal difference learning algorithms are presented in in Subsection 3.1 and Subsec- tion 3.2, respectively. Then, Subsection 3.3 presents the complete natural actor-critic algorithm that uses temporal difference learning algorithm as subroutine.
2" ("((s,za)== = Ex
7' Re So = =, 3, A. (4)
1=0
The asymmetric value function y of an stant-state policy π E is defined as = T (a|2) ()) We also define the asymmetric advantage func- tion AT A (,) = (s, VTT (s,)).
Let us define the m-step asymmetric Bellman operator as,
For any Fuclidean space X, let (0, B) be the ballal cen- tered at the origin with radius 0, and let le; X X-4 C be projection operator into the closed and convex set C C X in fg-norm: Ta( arg min ||c - xi C, Va E X. Fi- nally, let define the p-weighted formm,, for any proba- bility measures μ E (AY) as,
1
(s, E
2a R4 + + 2" (Sm, Zmm Am)
So 70=
= =, A. 0 = a
(5)
Since this m-step asymmetric Bellman operator is -m contractive, equation (5) has a unique fixed point Ộ= No- tice that, when using an agent-state policy, the environment
|| V
Σ {m( ZEA
(8)
3

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
In the algorithms, we implicitly assume to be able di- rectly sample from the discounted visitation measure d=. When it is unrealistic, it is still possible to sample from d" by sampling an initial timestep to ~ Geom(1-3) from a geometric distribution with success rate 1 y, and then taking tu - actions in the POMDP. The resulting sample (otg 2 follows the distribution d=.
Algorithm m-step temporal difference learning algorithm
input: policy л M. bootstrap timestep step size a, number of updates K, projection radius B. for k: 00 I do
Initialize (84,0, =k,0) ~ d= do Select action 02 ~ IT (-1=x,))-
for :=
Get environment state sk, (-)sk,,)
3.1. Asymmetric Critic
Get reward rk, = i, (k (k.it))
Get observation 0R,4+1 (111s2,4+1).
Suppose we are given features o: S x 2 x A With- out loss of generality, we assume sup,, sup=.2.all0(5,2,10 2,) I 1. Given weight vector B E TR let 23 denote the linear approximation of the asymmetric Q-function Q that uses features o with weight B.
Update agent state 2k,i+1 ~ U-- (1 Ok 0k,1+1). end for
Sample last action ak,m ~ TT (-IZk,.)
Compute semi-gradient gbe according to equation (13)
or equation (17).
Update Bk+1 = [ (0, (3x + tgk))
end for
return:
average estimate 2* - ())=²)(() (B,
(B)))) or k-1
Given an arbitrary projection radius B> 0, we define the hypothesis space as,
with 3 # Ek= 3k.
F = ((s,,,) (3, =( :3 B). (10)
3.2. Symmetric Critic
We denote the optimal parameter of the asymmet- ric critic approximation by 8T argminge (1 - (-Ila, and denote the corresponding approximation by (7(+)= = (()). The corresponding error is,
Similarly, we suppose that we are given features x: x A Ad Without loss of generality, we assume sup ((2,))(( 1. Given weight vector B BeRs, let Q7 denote the linear approximation of the symmetric Q- function Q" that uses features with weight 3,
/ - e- 1/---11-11 ||:
:: -2-
Eapp = min
(11)
(ī(2,a)= (3,x(2,))
(14)
fE
The corresponding hypothesis space for an arbitrary pro- jection radius B >>0 0 is denoted with x The opti- mal parameter also denoted by 3 arg aiggminse I[B, (+ the corresponding optimal approxi- mation is Q: = -8 (.7.x())) and the corresponding error is,
with d (s,2) the sampling distribution.
In Algorithm 1, we present the m-step temporal difference learning algorithm for approximating the asymmetric Q- function Q* of an arbitrary agent-state policy ग E 11M. At each step k the algorithm obtains one sample (sk,0, zk,0) dh from the discounted visitation distribution. Then, actions are selected according to policy ı to provide samples (ou,1, t, Sk,4+1, Ok,t+I (,, for 0 < t m. Next, the temporal difference 0g and semi- aamiierrdient& Ok are computed, based on a last action diam ~ at (.,,))
f Q- = -00=- (15)
Eapp
min FEFB
with d(z,a)= Σ dm (s, [T(()( the sampling distribution. SES
Algorithm 1 also presents the m-step temporal difference learning algorithm for approximating the symmetric Q- function. The latter is identical to that of the asymmetric Q-function except that states are not exploited, such that the temporal difference 6₂ and semi-gradient gs are given by,
1 TT., + Th 27, (sk.m, m, ml
81
Σ
i=0
0% (5k,0,2k,0, 2k,0, ax.0):
(12)
9k 6 V 23, (Sk,0> 0x.00
(13)
8%
Σ 1=0
7 T'R + 7 Q (Zk.m ap.m)
Then, the semi-gradient update is performed with 97+11 = Be + agg and the parameters projected onto the ball
Q3 (2,,0,
(16)
of radius B: B = I T (B) At the end, the al-
9k - 8 V s pr (#k,0,
(17)
gorithm computes the average parameter 3 = R >kk 8k
the end, the algorithm returns the average symmetric
and returns the average approximation @- 27.
approximation Q = Q Note that this symmetric critic

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
approximation and temporal difference learning algorithm corresponds to the one proposed by Cayci al. (2024).
Our natural actor-critic algorithm generalizes the one of Cayci al. (2024) the asymmettic setting and is detailed in Algorithm 2. For each policy gradient step 0 S < T, the natural policy gradient w is first estimated using N steps of stochastic gradient descent. At each natural policy gradient estimation step S r N, the algorithm samples an initial state (st,)) ~ dd from the discounted distri- bution d and an action ar, ~ (=(((zt,n) according the policy n, no, Then, the gradient fr,n of the natural policy gradient estimate Wt.n is computed with,
3.3. Natural Actor-Critic Algorithms
For both the asymmetric and symmetric actor-critic algo- rithms, consider log- log-linear agent-state policy Ty MI More precisely, the policy uses features v:: 2 A y with supz,a (1,(2))) < without loss of generality, and softmax readout,
exp((0, no(ar|z))= EnEd exp( (0, (2+,
(18)
Ut.n
V w ((Vo log To (at,n (2t,a), Wt,n)
-A 2t, ar,n))
(23)
In this work, consider natural policy gradients, which are less sensitive to policy parametrization (Kakade, 2001). Instead of computing the policy gradient in the original met- ric space, the idea to compute the policy gradient on a statistical manifold, defined by the expected Fisher infor- mation metric. The natural policy gradient is thus given by the standard policy gradient multiplied by preconditioner Fisher information matrix. Natural policy gradients are at the core of many effective modern policy-gradient methods (Schulman et al., 2015).
The gradient step is performed with Wt Wt,n (ve, and the parameters are projected onto the ball of radius B: Wt,n+1 = I () ()) (wi, Finally, the algorithm com- putes the average parameter We = -N-1 Wi, and per- forms the policy gradient step: 0.+1 = 0r + mn,, After all policy gradient steps, the final policy is returned.
Algorithm Natural actor-critic algorithm
input: number of updates T, number of steps N, step sizes Ç. 17. projection radius B.
The natural policy gradient of policy Ta E IIM is defined as follows (Kakade, 2001),
Initialize 0u =0.
for 0= do
- = (1 (1-18 F) (Te(
(19)
Obtain _ or 2T using Algorithm 1. Initialize : for 0
where Ft is the pseudoinverse of the Fisher information matrix, which is defined as the outer product of the score of the policy,
Initialize (st.n; d'..
Sample ar, TT (+1z),). Compute the gradient Vt,n of the policy gradient using equation (23) equation (26).
FR = 0d (VllogTo (AlZ) & TologTo(A12)) (20)
Update Wi,n+1 Wi,n CVe,
As shown in Theorem 1, the natural policy gradient w is the minimizer of the asymmetric objective (22).
Project wr,++1 I ['B2(0,B) (w end for
Theorem (Asymmetric natural policy gradient). For any POMDP P and any agent- agent-state state policy ma E II,, we have,
Update 0.+1 = O2 11 En Wt.a
end for return: final policy कт Bey
- = (1 VoJ(TO) E argmin wER<#
(21)
As shown Theorem 2, the natural policy gradient wi is also the minimizer of the symmetric objective (25).
with,
Theorem 2 (Symmetric natural policy gradient). For any POMDP P and any agent-state policy To IIM, we have, (22)
((w)==1'" (1))
- () VoJ(TT) argmin L(w), weB
(24)
The proof is given in Appendix B. In practice, since the asymmetric advantage function is unknown, the al- gorithm estimates the natural policy gradient by stochas- tic gradient descent of L(w) using the approxima- tion T (S, A) = (S, A) - (S, Z) with Ti Eas n (a ((S,,,
with.
L(w) = [ ( w) (Z,,)))))
(25)
5

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
The proof is given in Appendix B. As in the asym- metric case, the symmetric advantage function is un- known, and the algorithm estimates the natural gradi- ent by stochastic gradient descent of equation (25) using the approximation A (2 ))=))=a - (2, A) V (2) with V ====Ea -aEA To(al QTh aZ,a).
where the temporal difference learning, function approxima- tion, and distribution shift terms are given by,
4B2 + ( 1-7 +2
Eid
(30)
2v 2VK(1 71)
Algorithm 2 also presents the symmetric natural actor-critic algorithm, initially proposed by Cayci al. (2024). The latter is similar to the asymmetric algorithm except that it uses the symmetric advantage function, such that the gradient of the policy gradient is given by.
1 1
app
min |lʃ - 2
(31)
1 1-7m
SEFO
1
27m
Sahil
=
+ 1- V 1 1--mm Ildm dlhiv
(32)
Ft,n = (VVoloo (t,n) Wz
with d(s, d" (s, z) (al=) the sampling distribution, and dm (m, 2,) a= d (s, 2 ( (a|z) the bootstrapping distri- bution.
- -A (zi,n;(t,,))
(26)
While Theorem 1 and Theorem show that w is the mini- mizer of both the asymmetric and the symmetric objectives, the next section establishes the benefit of using the asymmet- ric loss. More precisely, asymmetric learning is shown to improve the estimation of the critic and thus the advantage function, which in turn results better estimation of the natural policy gradient.
The proof is given in Appendix C, and adapts the proof of Cayci al. (2024) the asymmetric setting. The first term Eu is the usual temporal difference emror term, decreasing in K-1/4, The second term Eapp results from the use of linear function approximators. The third term Eshin arises from the distribution shift between the sampling distribution dM 8 क (i.e., the discounted visitation measure) and the bootstrap- ping distribution di @ π (i.e., the distribution m steps from the discounted visitation measure). It is consequence of not assuming the existence of stationary distribution assuming to sample from the stationary distribution.
4. Finite-Tree Time Analysis
In this section, we give the finite-time bounds of the previ- ous algorithms in both the asymmetric and symmetric cases.
The bounds the asymmetric and symmetric temporal dif- ference learning algorithms are presented Subsection 4.1 and Subsection 4.2, respectively. In Subsection 4.3, the bounds of the asymmetric and symmetric natural actor-critic algorithms are given.
4.2. Finite-Time Bound for the Symmetric Critic
Given a history h (oo, ao........0................ .e). the belief is defined as,
(s lha) = Pr(S, St H; = hh)).
(33)
We use ||и " to denote the total variation between two probability measures V E ((X) over a discrete space X,
Given an agent state 24, the approximate belief is defined as,
8 (xolz))) = Pr(S; = = =,))
(34)
|| - V1TTV sup (u(A)- u(A)l AÇX
(27)
We obtain the following finite-time bound for the Q-function approximation resulting from the symmetric temporal dif- ference learning algorithm detailed in Algorithm 1.
lu(x) -((o)~((a) v(x))-
(28)
TEA
Theorem (Finite-time bound for symmetric m--tep tempo- ral difference learning (Cayci et al., 2024)). For any agent- state policy æ E M. and any m N, we have for Algo- rithm with 1 and arbitrary B 0. VK
4.1. Finite-Time Bound for the Asymmetric Critic
Our main result is to establish the following finite-time bound for the Q-function approximation resulting from the asymmetric temporal difference learning algorithm detailed in Algorithm 1.
E ||00 12-1
S Eld + Eapp + Eshift + Eallas-
(35)
Theorem (Finite-time bound for asymmetric m-step temporal difference learning). For any agent-state policy π E IIM, and any m N, we have for Algorithm with 1 and arbitrary B>0 0.
where the temporal difference learning, function approxima- tion, distribution shift, and aliasing terms are given by,
( 11- +BB
2
4B² +
E F11
Snd Sapp + Sshift,
(29)
End
2VK(11 (1
(36)
6

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
Capp
1 +
min fl Q" ala fEFE
(37)
where the different terms may differ for asymmetric and symmetric critics,
1 1- ym
27th
B² + 22og |Al
Eshift
B
ym v I1dm dllTv
(38)
Epsc
(42)
2VT
Calios
1
2
B"
Am
TV
Zo=
Eactor
V (1 (1-7)VN
(2 (2-770 -
(43)
(39)
Ginf,arym
(44)
with d(z,a) = Eoes dd (s, (a)z) the sampling distribu- tion, and dm (2,a)= = Eves di (s)2) the bootstrap- ping distribution.
20 ET
Einfaym
7dt
1ig - by
(45)
TV
E Egradaasym
sup 0S1<T
min Li (w)) w
(46)
The first three terms are identical or analogous to the asym- metric case. The fourth term Eaiias results from the difference between the fixed point Q of the symmetric Bellman oper- ator (7) and the true Q-function Q*.
Egrad.sym =
sup 05t<T
min L (w),
(47)
and die given Theorem and Theorem 4.
We note some minor differences with respect to the original result of Cayci et al. (2024) that appear to be typos and minor mistakes in the original proof. We provide the corrected proof in Appendix D.
The first term Ence is the usual natural actor-critic term de- creasing in T-1 (Agarwal et al., 2021). The second term Cint is the inference error resulting from use of an agent state in a POMDP (Cayci et al., 2024). This term is zero for the asymmetric algorithm. The third term Eacor is the error re- sulting from the estimation of the natural policy gradient by stochastic gradient descent. The fourth term Egrad is the er- ror resulting from the use of linear function approximator with features V Te (a|z) for the natural policy gradient. Finally, the fifth term + ET= - is the error arising from the successive critic approximations. Inside of each etite terms, the aliasing term is thus zero for the asymmetric al- gorithm. The proof, generalizing that of Cayci et al. (2024) to the asymmetric setting, is available in Appendix E.
The results of Theorem 3 and Theorem 4 can be straight- forwardly generalized to any other sampling distribution. However, obtaining bounds in term of d= @ is useful for bounding the performance of the actor-critic algorithm.
4.3. Finite-Time Bound for the Natural Actor-Critic
Following Cayci et al. (2024), we assume that there exists concentrability coefficient Co < oc such that
suPoSe<T E|Ca] < Coo with,
d' (s, 2)T (alz) 8,2,a d (8,z 2 mo (a|z)
C = sup
(40)
4.4. Discussion
Roughly speaking, this assumption means that all successive policies should visit every agent states and actions visited by the optimal policy with nonzero probability. It motivates the log-linear policy parametrization in equation (18) and the initialization to the maximum entropy policy in Algo- rithm 2. We obtain the following finite-time bound for the suboptimality of the policy resulting from Algorithm 2.
As can be seen from Theorem 3 and Theorem 4, compared to the symmetric temporal difference learning algorithm, the asymmetric one eliminates a term arising from aliasing in the agent state, in the sense of equation (39). In other words, even for an aliased agent-state process, leveraging the state to learn the asymmetric Q-function instead of the symmetric Q-function does not suffer from aliasing, while still providing a valid critic for the policy gradient algorithm. That said, these bounds are given in expectation, and future works may want to study the variance of the error of such Q-function approximations.
Theorem 5 (Finite-time bound for asymmetric and symmet- ric natural actor-critic algorithm). For any agent-state pro- cess M = (Z,U), we have for Algorithm with a a= VR* B-T
< <=
v2N 17 VT
and arbitrary B >> O.
From Theorem 5, we notice that the inference term (45) in the suboptimality bound vanishes in the asymmetric setting, Moreover, the average error 7 - Faili made in the eval- uation of all policies To...., - appears in the finite-time bound that we obtain for the suboptimality of the policy. Thus, the suboptimality bound for the actor also improves in the asymmetric setting by eliminating the aliasing terms with respect to the symmetric setting.
(1 1) 7)
min E [E((TT") J[(r)) S Ensc + 20iml 0SteT
T-1
+ 0.0
Eactor + 25gru + 2/6
Σ
(41)
T
'The authors notably wrongly bound the distance ||@: hy Sapp at one point, which nevertheless yields a similar result.
@TI|
7

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
By diving into the proof of Theorem 5 equations (236) and (237), we understand that the Q-function error impacts the suboptimality bound through the estimation of the natural policy gradient (19). Indeed, this error term in the subopti- mality bound directly results from the error on the advantage function estimation used in the target of the natural policy gradient estimation loss of equations (23) and (26). This advantage function estimation is derived from the estimation of the Q-function, such that the error the latter directly impacts the error on the former, as detailed in equations (236) and (237). This improvement in the average critic er- ror unfortunately comes at the expense of a different residual error Egrd on the natural policy gradient loss. Indeed, as can be seen in equation (47); we obtain a residual error gyad,asym using the best approximation of the asymmetric advantage A a,) instead of residual error Egrad.ym using the best approximation of the symmetric critic A (2,a), Since both natural policy gradients are obtained through a linear regression with features Ve log Fe (a|z)) it is clear than the asymmetric residual error may be higher than the symmetric residual error, even in the tabular case.
be seen as nonlinear approximators with a sliding window agent state. Our analysis also motivates future work studying other asymmetric learning approaches that con- sider representation losses to reduce the aliasing bias (Sinha & Mahajan, 2023; Lambrechts et al., 2022; 2024).
Acknowledgements
Gaspard Lambrechts acknowledges the financial support of the Wallonia- Wallonia-Brussels Federation for his FRIA grant.
Impact Statement
This paper presents work whose goal is to advance the field of machine learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the Theory of Policy Gradient Methods: Optimality, Ap- proximation, and Distribution Shift. Journal of Machine Learning Research, 2021.
We conclude that the effectiveness of asymmetric actor- critic algorithms notably results from better approximation of the Q-function by eliminating the aliasing bias, which in turn provides a better estimate of the policy gradient.
Akkaya, I,, Andrychowicz, M., Chociej. M., teusz Litwin, M.. McGrew, B., Petron, A., Paino, A., Plappert, M., Powell, G., Ribas, R., Schneider, J.. Tezak, N., Tworek, J., Welinder, P., Weng, L.., Yuan, Q., Zaremba, W., and Zhang, L. Solving Rubik's Cube with a Robot Hand. arXiv:1910.077 1910.0710.. 2019.
5. Conclusion
In this work, we extended the unbiased asymmetric actor- critic algorithm to agent-state policies. Then, we adapted finite-time analysis for natural actor-critic to the asym- metric setting, This analysis highlighted that on the con- trary to symmetric learning, asymmetric learning is less sensitive to aliasing in the agent state. While this analy- sis assumed a fixed agent-state process, we argue that it useful to interpret the causes of effectiveness of asym- metric learning with learnable agent-state processes. In- deed, aliasing can be present in the agent-state process throughout learning, and in particular at initialization. More- over, it should be noted that this analysis can be straight- forwardly generalized to learnable agent-state processes by extending the action space to select future agent states. More formally, we would extend the action space to A+ = A A(z) with at = aī), the agent state space to z+ - O with z - (2,, and the agent-state pro- cess to U(=t 12,,t ,0, x exp(a,"* yd2; , This alternative to backpropagation through time would neverthe- less still not reflect the common setting of recurrent actor- critic algorithms. We consider this as a future work that could build on recent advances in finite-time bound for re- current actor-critic algorithms (Cayci& & Eryilmaz, 2024a;b). Alternatively, generalizing this analysis to nonlinear approx- imators may include recurrent neural networks, which can
Avalos, R., Delgrange, F., Nowe, A., Perez, G., and Roi- jers, D. M. The Wasserstein Believer: Learning Belief Updates for Partially Observable Environments through Reliable Latent Space Models. The Twelfth International Conference on Learning Representations, 2024.
Baisero, A. and Amato, C. Unbiased Asymmetric Reinforce- ment Learning under Partial Observability. International Conference on Autonomous Agents and Multiagemt Sys- tems, 2022.
Bakker, B. Reinforcement Learning with Long Short-Term Memory. Advances in Neural Information Processing Systems, 2001.
Buesing, L., Weber, T., Racanière, S.,, Eslami, S. M. A.. Rezende, D. J., Reichert, D. P., Viola, F., Besse, F., Gregor, K., Hassabis, D., and Wierstra, D. Learning and Querying Fast Generative Models for Reinforcement Learning, arXiv:1802.03006, 2018
2r41
Cai, Y., Liu, X., Oikonomou, A., and Zhang, K. Prov- able Partially Observable Reinforcement Learning with Privileged Information. Advances in Neural Information Processing Systems, 2024.
8

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
Cayei, S. and Eryilmaz, A. Convergence of Gradient De- scent for Recurrent Neural Networks: A Nonasymptotic Analysis. arXiv:2402. 122424442..12211, 2024a.
Igl, M., Zintgraf, L., Le, T. A., Wood, F., and Whiteson, S. Deep Variational Reinforcement Learning for POMDPs. International Conference on Machine Learning, 2018.
Cayci, S. and Eryilmaz, A. Recurrent Natural Policy Gradi- ent for POMDPs. ICML Workshop on the Foundations of Reinforcement Learning and Control, 2024b.
Kaelbling, L. P., Littman, M. L., and Cassandra, A. R. Plan- ning and Acting Partially Observable Stochastic Do- mains. Artificial Intelligence, 1998.
Cayci, S., He, N., and Srikant, R. Finite-Tima Analysis of Natural Actor-Critic for POMDPs. SIAM Journal Mathematics of Data Science, 2024.
Kakade, S. and Langford, J. Approximately optimal approx- imate reinforcement learning. International Conference on Machine Learming, 2002.
Choudhury. S., Bhardwaj, M.. Arora, S., Kapoor, A., Ranade, G., Scherer, S., and Dey, D. Data-Driven Plan- ning via Imitation Learning. The International Journal of Robotics Research, 2018.
Kakade, S. M. A Natural Policy Gradient. Advances in
Neural Information Processing Systems, 2001.
Kaufmann, E., Bauersfeld, L., Loquercio, A., Müller, M., Koltun, V., and Searamuzza, D. Champion-Level Drone Racing using Deep Reinforcement Learning. Nature, 2023.
Degrave, J., Felici, F., Buchli, J., Neunert, M., Tracey, B. D., Carpanese, F., Ewalds, T., Hafner, R., Abdolmaleki, A., de Las Casas, D., Donner, C., Fritz, L., Galperti, C., Huber, A., Keeling, J., Tsimpoukelli, M., Kay, J., Merle, A., Moret, J.-M., Noury, S., Pesamosca, F., Pfau, D., Sauter, O., Sommariva, C., Coda, S., Duval, B., Fasoli, A.,
Lambrechts, G., Bolland, A., and Ernst, D. Recurrent Net- works, Hidden States and Beliefs Partially Observable Environments. Transactions on Machine Learning Re- search, 2022.
Kohli, P., Kavukcuoglu, K., Hassabis, D., and Riedmiller,
M. A. Magnetic Control of Tokamak Plasmas through
Lambrechts, G., Bolland, A., and Ernst, D. Informed POMDP: Leveraging Additional Information in Model- Based RL. Reinforcement Learning Journal, 2024.
Deep Reinforcement Learning. Nature, 2022.
Dong, S., Roy, B. V., and Zhou, Z. Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent States. Journal of Machine Learning Research, 2022.
Lee, A. X., Nagabandi, A., Abbeel, P., and Levine, S. Stochastic Latent Actor-Critic: Deep Reinforcement Learning with Latent Variable Model. Advances in Neural Information Processing Systems, 2020.
Gregor, K., Rezende, D. J., Besse, F., Wu, Y., Merzie, H., and den Oord, A. Shaping Belief States with Gener- ative Environment Models for RL. Advances in Neural Information Processing Systems, 2019.
Levine, S., Finn, C., Darrell, T., and Abbeel, P. End-to- End Training of Deep Visuomotor Policies. Journal of Machine Learning Research, 2015,
Guo, Z. D., Azar, M. G., Piot, B., Pires, B. A., and Ré Munosmi. Neural Predictive Belief Representations. arXiv: 181 I. 1.06407, 2018.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M. A., Fidje- land, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., and Hassabis, D. Human-Level Control through Deep Reinforcement Learning, Nature, 2015.
Guo, 7. D., Pires, B. A., Piot, B., Grill, J.-B., Altché, F., Munos, R., and Azar, M. G. Bootstrap Representations for Multitask Reinforcement Learning. International Conference on Machine Learning, 2020.
Ni, T., Eysenbach, B., SeyedSalehi, E., Ma, M., Gehring, C., Mahajan, A., and Bacon, P.-L. Bridging State and His- tory Representations: Understanding Self-Predictive RL. International Conference on Learning Representations, 2024.
Han, D., Doya, K., and Tani, J. Variational Recurrent Mod- els for Solving Partially Observable Control Tasks. Inter- nal Conference on Learning Representations, 2019.
Hausknecht, M. and Stone, P. Deep Recurrent Q-learnig for Partially Observable MDPs. AAAI Fall Symposium Series, 2015.
Pinto, L.,, Andrychowicz, M., Welinder, P., Zaremba, W., and Abbeel, P. Asymmetric Actor Critic for Image-Based Robot Learning. Robotics: Science and Systems, 2018.
Heess, N., Hunt, J. J., Lillicrap, T. P., and Silver, D. Memory- Based Control with Recurrent Neural Networks. arXiv: 15 12. 04455 2015.
Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., Lillicrap, P., and Silver, D. Mastering

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
Atari, Go, Chess and Shogi by Planning with Learned Model. Nature, 2020.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust Region Policy Optimization. International Con- ference on Machine Learning, 2015.
Shalev-Shwarzz, S. and Ben-David, S. Understanding Ma- chine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Sinha, A. and Mahajan, A. Asymmetric Actor-Critic with Approximate Information State. IEEE Conference on Decision and Control, 2023.
Sinha, A. and Mahajan, A. Agent-State Based Poli- cies in POMDPs: Beyond Belief-State MDPs. arXiv: 2409.15703, 2024.
Subramanian, J.. Sinha, A., Seraj, R., and Mahajan, A. Ap- proximate Information State for Approximate Planning and Reinforcement Learning in Partially Observed Sys- tems. Journal of Machine Learning Research, 2022.
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy Gradient Methods for Reinforcement Learning with Function Approximation. Advances in Neural Infor- mation Processing Systems, 1999.
Vasco, M., Seno, T., Kawamoto, K., Subramanian, K., Wur- man, P. R., and Stone, P. A Super-Human Human Vision-Based Reinforcement Learning Agent for Autonomous Racing in Gran Turismo. Reinforcement Learning Journal, 2024.
Wang, A., Li, A. C., Klassen, T. Q., Icarte, T., and Mcll- raith, S. A. Learning Belief Representations for Partially Observable Deep RL. International Conference on Ma- chine Learning, 2023.
Warrington, A., Lavington, J. W., Scibior, A., Schmidt, M., and Wood, F. Robust Asymmetric Learning in POMDPs. International Conference Machine Learning, 2021.
Wierstra, D., Förster, A., Peters, J., and Schmidhuber, Solving Deep Memory POMDPs with Recurrent Policy Gradients. International Conference Artificial Neural Networks, 2007.
Zhang, M., McCarthy, Z., Finn, C., Levine, S., and Abbeel, Learning Deep Neural Network Policies with Continu- ous Memory States. IEEE International Conference Robotics and Automation, 2016.
Zhu, P., Li, X., Poupart, P., and Miao, G. On Improv- ing Deep Reinforcement Learning for POMDPs. arXiv: 1704.07978 2017.
10

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
A. Agent State Aliasing
In this section, we provide an example of aliased agent state, and discuss the corresponding aliasing bias. For this purpose, we introduce slightly modified version of the Tiger POMDP (Kaelbling et al., 1998), see Figure 1. In this POMDP, there two doors: opening on room with treasure on the left, and another opening room with tiger on the right. There are four states for this POMDP: being in the treasure room (Treasure), being in the tiger room (Tiger), being in front of the treasure door (Left) or being in front of the tiger door (Right). The rooms are labeled outside (Leff or Right), but inside it completely dark (Dark), such that do not observe which room are. When outside of the rooms, the agent can switch the other door (Swap) it can open the door and enter the room (Enter). Once in room (Treasure or Tiger), the agent stays locked forever, and gets a positive reward (+1) if it in the treasure room (Treasure) whatever the action taken (Swap or Enter). We consider the agent state to be simply the last observation (Left, Right, or Dark). Notice that the optimal agent-state policy conditioned on this agent state also an optimal cistory-dependers policy. other words, the current observation is sufficient statistic for optimal control in this POMDP. We consider a uniform initial distributions over the four states.
Swap/Enter (+1)
Swap/Enter (+0)
Treasure (Dark)
Tiger (Dark)
Enter (+0)
Enter (+0)
Swap (+0)
Left (Left)
Right
(Right)
Figure Aliased Tiger POMDP.
For given agent state (Dark), there exist two differrntt underlying states (Treasure or Tiger). We call this phenomenon aliasing. Now, let us consider simple policy that always takes the same action (Enter). It is clear that the sym- metric value function defined according to equation (6) given by V (== Dark)= = ク(ー V* Left) 12g- and (= Right)=
However, when considering the unique fixed point the aliased Bellman operator of equation (7) We refer to the distance between V and V or similarly Q and Q7, as the aliasing bias. In the analysis of this paper, this distance appears the weighted f2-norm IQ" Q* I|a where d(s,2,a) d= (s, =) (a|2). In the analysis, we also define the aliasing term Ealias as upper bound on this aliasing bias, see Lemma D.I for detailed definition.
with m m=1 1, we have instead // (= Dark) セリ- V (2 Left) = -パー and / (2 -iiht) = शリー
B. Proof of the Natural Policy Gradients
In this section, we prove that the natural policy gradient is the minimizer of analogous asymmetric and symmetric losses.
B.1. Proof the Asymmetric Natural Policy Gradient
In this section, we prove that the natural policy gradient is the minimizer of an asymmetric loss. Theorem (Asymmetric natural policy gradient). For any POMDP and any agent-state policy ae E [T.. we have,
- (1-7) Ft, VoJ(FO) aargmin L(w), wERds
(21)
with,
((w) - ( (VV)))_((VVV (NN) A5,,),,,))))
(22)
Proof. Let note that,
Vw[(w)=23 =2 1
(s
(48)
Therefore, for any wh Rd minimizing L(w), we have V Vw = such that,
E 6
(A (A/Z)) w
(49)
= - (VVloggT Volog ग. (A [!"]
(50)
pd' (ologgT & Volog (A (A w
(51)

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
= w
(52)
which follows from the definition of the Fisher information matrix F., in equation (20). Now, let us define the policy N (A|S, ((05s2)))<(AA()) (A)2,) which ignores the state S. From there, we have,
Fu _ Ed' [V Vologma Te (4,4)
(53)
= =E>
Volog [ollgm,((1.,,2) (415,2)4(5,2.44)
(54)
E
( V(S,
(55)
E
Volog (A1.))221A E4
[Volog qh (AIS,
(56)
Ed'd
[olog ETd
V(S, 2)
TØ (a (a 2V Volog (a|S
(57)
aEA
(AS2 Ed
V(S, Z)
V PTT (a)S,2)
(58)
aEA
Ed o (115)371 Ed'"
V(8,Z)V, Σ T (a/S,2)
(59)
aeA
Ed' (A15 - [V(5
(60)
E
(A|S, 2) (AIS, 2),
(61)
Using the policy gradient theorem (Sutton et al., 1999) and equation (61),
Fa w
-7) (o
(62)
From there, we obtain using the definition of के.
Fr, wT = (1 -1 (o
(63)
= Vo-
(64)
This concludes the proof.
B.2. Proof of the Symmetric Natural Policy Gradient
In this section, we prove that the natural policy gradient is the minimizer of an asymmetric loss. Theorem 2 (Symmetrie natural policy gradient). For any POMDP P and any agent-state policy na E II, have,
= (1 - F (TJ( arg min L(w),
(24)
wER
with,
L(w) [w))=Er ((Voll' [(0==="(((VVOO5TAAAAA)
(25)
Proof. Similarly to the asymmetric setting, for any wi minimizing L(w), we have V (w = 0, such that,
[Volog To (A(2))
E (
(65)
E (Volog Vo To (A [
(66)
[Volog mo ( V log (A 2)) w.
(67)
F TT
(68)
12

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
which follows from the definition of the Fisher information matrix Pr in equation (20). From there, have,
Fx w E T
V To (A12))
(69)
F W.TH E
Volog nn (A)
[A(S,
(70)
2xy Ed
Ed VV n (S, A)|2,
(71)
Fx, w E
0
VV [olog
(72)
which follows from the law of total probability. From there, by following the same steps as in the asymmetric case (see Subsection B.1), we obtain,
Fx, u0 =
(73)
This concludes the proof.
C. Proof of the Finite-Timi Bound for the Asymmetric Critic
In this section, we prove Theorem 3, that is recalled below.
Theorem (Finite-time bound for asymmetric m-step temporal difference learning). For any agent-state policy æ E M..s and any m E N, we have for Algorithm with
I and arbitrary B > 0,
VK
Q - @-1
Sd + Eapp + Eshift:
(29)
where the temporal difference learning, function approximation, and distribution shift terms are given by,
4B2 ( [- +2B
Ed
(30)
2VK(1 (m)
+ m
Epp
min
||ʃ 2 lla
(31)
mm FEF
( V 1-am Vlldm. dlltv:
2mm
Eshift
B
(32)
with = dd (al=) the sampling distribution, and dm (,, = (s, ()) the bootstrapping distribution.
Proof. To simplify notation, we drop the dependence æ and 9 and use a shorthand for Q Q" as shorthand for Q Q as a shorthand for @a and O as a shorthand for 2% where the subscripts and superscripts remain implicit are assumed clear from context. When evaluating the Q-functions, go one step further by using Qx,i denote Q(Sk, Zk. Ak,i). Qi. to denote (Z,,,, Ak,s) or Ộx.i to denote (Sk,,, ZR., Ak,s), and dies to denote ΦSSr.i, Zk,i, Ag,). In addition, we define d as a shorthand for d @ m, such that d(s, 2, = dl (a(z)) and dm as shorthand for d 8 I, such that dm (s, (s,2,a) = (s. (a|2).
First, let define A as,
|| o e 2.113]
A
E
= E [1000) (3x, (1))
(74)
Using the linearity of Q in B 8K 1, the triangle inequality, the subadditivity of the square root, and Jensen's 's inequality, we have,
K-1
27
E e
01
E
2(-)
Σ Bk p(-)
(75)
K
13

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
E
(Q(+) (5x.
(76)
K
E
(2(+) (()))
(77)
K
k=0
E
12()) (3 (6)))
(78)
K
k=0
E
[10()) - (3xx 0(-))1))
(79)
K2
k=
A
(80)
K=U
Σ
(81)
K
A
(82)
K
K-
Σ
(Ax +)
(83)
K
k=
1 K-1
Σ
(As - 11
+1
(84)
K K=0
K-1
Σ
(Ak -1)2+1, +1,
(85)
K k=0
where is arbitrary.
Now, consider the Lyapounov function L(3)= = -1,3, -3112 in order to find bound on Ek=1 (Ax 1)
Since
B. E (0, B), with B2(0, B) convex subset of Rdd, and the projection T'c is non-expansive for closed and convex C, we have for all k 2 0,
[(3x+1) = 1|, 3 11
(86)
< ||3. 3r+ 112
(87)
||.. (Bx ogki
(88)
= II(3. Bb)) agk 11
(89)
((3. - 3&4) agk: (3, - 344 agk)
(90)
(B. - Bv, B. Ba) - -2a -Bx.g + +
(91)
-((8k) 20(8. 3k.gk) +a² 119h
(92)
= =[(3k) 23 -3. + + 11
(93)
Let us consider the Lyapounov drift [([(3x+1) C(8))) and exploit the fact that environments samples used to k.j m) and
compute gk are independent and identically distributed. Formally, we define B = o Je o Z4.0, Ak,)), where :X;;i denotes the o-algebra generated by collection (X;: i IE of random
14

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
variables. We can write, using the law of total expectation,
E [[ [[3)]] =B [ (C(Bk+1) C(3x) 6k-1]]
(94)
- 2alB [ - Do. / Bk x-x=1) 1I] + 2E
E
1
6k-1
B
(95)
Let us focus on the first term of equation (95) with E [o - B.) 1). First, since V = -.... the semi-gradient Ih is given by (see equation (13)),
m- 7² R + 7 Qkim 2x.0 0k.0
9k
(96)
By conditioning on the sigma-fields Ck-1 and SR. we have,
m
E E - f..gk) Gk-11]
E
Y R + 7m Q
Sk. 6k-1
2x.0 (Be (Be-B.. -k.0
(97)
E
RR. + 7 2k.m 82. Bk-1
2x.o (ou. -7h0)
(98)
Note that according to the Bellman operator (5) we have,
m
E
7" RR, 3k: 0k-1
24.0 - 1I Bk. 1R-
(99)
By substituting equation (99) in equation (98), we obtain,
E(ee - B.,gk) Bk. (:-1)
E
m
7 Rk,
Jk. G
"
+ "E
@ 3k. 6k-1
Ec.0 -Q,, (Q., - (Q.o)
(100)
Q..0 - 7 " 12 BRg Bk- 1] T
② 2i.m
Bk, BB-1
2n.0) (Ān.0 - 2i.0)
(101)
((Ox. -2.00 - 7 E 2k 2p.m Bk. (x-1)
((ê,.0- -4.0) + +QN.
22.01)
(102)
-O(2k, 22.0)² (2k,n
2k,0)
+ +T "E xx.m 2k.m 32. 6
(Qx. - Ck.o) + @a.. - Qx.m Bk. 8x (Qx.0 - E2.o).
(103)
Let us now take the expectation of (103) over &2 given G for each term separately,
For the first term, we have,
- (Quu 2n.0)/00 = 0-- 2
(104)
For the second term, we have, using the Cauchy-Schwarz inequallti.
E [QL. (R. 2i.0) GA- | Qu)(e-
(105)
$ 5 2. -0
(106)
Before proceeding to the third and fourth terms, let notice that,
E Qu.m
2a.m B = Σ dm 28,
(107)
8.2.a
15

---

A Theoretical Justification for Asymmetric Actor-Critte Algorithms
2, + dm dd(s, - (1ll,,
(108)
Remembering that sup,,,,0 (x, B and sup,, Q(s,2,a) 1- have,
E (@r.m 2x.)) [6--
(d(s,2,a) ( (2.(s,))))
(2u(5,2,0)- -
(109)
2 +
Σ
(2, 2((,
(110)
8,2,a
< 6x 0
2
+ Ildm dl sup
-2x(s,2,a)
(111)
5,5,0
0 2
2
+ l|dm - dll
2 B B BB+T--)
(112)
where (B+ is an upper bound on sup 8,2,0 tivity of the square root, we have,
() - 2(3,2,a) Now, using Jensen's inequality and the subaddi-
E
Ōx.m
2k.m
6k-1
SE V @kkm - 22 Bk-1
(113)
S/ V (0am - -2kmm)mmmm 6k-1
(114)
Øx e|1 + B (B+I=)) Ildm - dl
+(BB
++B+
(115)
With this, we proceed to the third and fourth terms (without the multiplier "m and show the following.
For the third term, we have by upper bounding 12x,a Qk.ol by B 1-7"
E @@ ( 2k.0) Gh (x
|
s Ōx -x =
B (++1-))
1
v V
(116)
For the fourth term, we have by upper bounding
Qk.0 Lx,l by
1 1- B,
2 o - + B (D+
E [Q -
(x- 2x 2
Vlldm Vildm- dlltv.
(117)
By taking expectation over B5-1 of the four terms and using the previous upper bounds, we obtain,
[3x Bu
E
E
1 - -_,9hh)
(118)
5 5- 7 E
Q d
- 2
(1
+ m E [| 1x 2 - o
+ m
B + 1-
V
|1dm dllTV
(119)
1 )² V /lldm dlllv (120) B (B+1_a)
2
= =-(1-"") A + (1 ) 0 - -e123 + 2
Let us now focus on the second term of equation (95) with E
11 6 Since sup,,2.e || 2, a) < and || - B and Tk, I 1 for all A > and for all < m - 1, the norm of the gradient (96) bounded as follows,
for all &
1- m
sup 9 2 < k20
+ (1+>")
1-7 +BB
(121)
1-7
16

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
We obtain, for the second term of equation (95),
11
= E
E
||9
2 2B
8
1
(122)
(123)
By substituting equations (120) and (123) into the Lyapounov drift of equation (95), we obtain,
[[C(8++1)- - - -""">>
-a(11-7"
2a(1 +> ê- -
el1 +a²
+
2B
1 1-7
+ +00
B+ (B+
V Imm -dlTv-
dllTv.
(124)
By setting / = mm min JEF! ||ʃ 21 we can write,
1+y
1
2
E -((3)) -2 (43 -21xa) +a²
1- 2B
B+ (+t1-m) V |m dllTv
+
(125)
=-20 - --mh(
21 + +12) + - +
+ 2B
1-
B++ 1 1-7/ )
1 (++111
2
+4a7
V ||dm dl
(126)
1
=aaa - - - 1)2 + 20(11 -1 + +a²
2B
1-
2
+ +
B+ 1--) / /ldm - dll
(127)
By summing all Lyapounov drifts B(L(3k+1) ({((e)(( [(Bx)), we get,
K
(1_ + 2B
E - m)
(Ax 2x=K=KK(1-" t2K 11
k=
+ 4aaKym
B + 1-7) (+--1)
)
V 11mm - -dlTv-
(128)
By rearranging and dividing by 2aK(1- - we obtain after neglecting L(3x) >0,
1 K
Σ
( 1)35 B[C(S)) [(3x)]
+12
1
+
2B
2
2aK(1 )m)
2m
1 1-7
k=
+ 2nth
B +
1 1-7)
VIldm dllTv
(129)
mm
|1 11.12
2(1 2(1 (1_, 1-7 +2B
2
<
+ +
a
2aK (1 mm
2 m
B+ )
V /lldm -dllav.
(130)
7m
17

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
The bound obtained through this Lyapounov drift summation can be used to further develop equation (85), using the subadditivity of the square root,
K-1
O
(A: - 1)2 +1
(131)
K K=
11:00
Boll2
+
+ 2B
20 ((1K(11 -
2(1 -m
2
V /lidm dllrv
B 1-7)
(132)
1 1-7
1180 Boll2
+ 7m
1
min ||ʃ - 221 V 2(1 - 7m)
2B
V 22 (1 )
7m
JEFE
1-7
B 1--)) V 1- Vlldm dllrv.
2
(133)
By setting a
and upper bounding 1130 - 3.1l by 2B, we get,
JK
E
- 213
2B
1 7
min |l Qlla
11-7 2B
1
2v 12/(1 -mm)
- 7m
SEF
22v ((1 7m)
27m
B+ 1 1-7) V 1 1-
Vlldm dllTv
(134)
4B² + 1 + +BB
+ 1 7
min |lʃ - O1l SEFF
2 M((11 -
ym
B+ 1-7/ )
27m
Vlld d|lTv.
(135)
1 1-am
This concludes the proof.
D. Proof of the Sinite-Time Bound for the Symmetric Critic
between the Q-function QT and the fixed point Q Lemma D.1 (Upper bound on the aliasing bias (Cayci et al., 2024)). For any agent-state policy IT,, and any N, have,
Let us first find an upper bound on the distance Q
रx 2
|00- - ~-
-
1 m
E
km
|Bee
bkom
Zo
(136)
k=
Proof. The proof is similar to the one of Cayci et al. (2024). Let us first define the expected m-step return,
mm11
Fm (s, 2. = E
* R S. = Zo A. = =a
(137)
Using the expected m-step return and the definition of the belief b in equation (33) and approximate belief in equation (34), it can be noted that,
=
n
kmm
bkem (5) Hmm ) F Zkm Akm) Zo 22= =
(138)
SES
18

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
(2,,a) TM
Σ #ES
bkm (5) Zkm ) (8, 7km, Akm) Zo - Ao
(139)
Indeed, bootstrapping at timestep m based on the agent state only is equivalent to considering the distribution future states be 6, (m12m) instead bm (-|Hm). As consequence, we have,
Q" (2,a)
E"
Amm
(bom (s) bro (8) 7km)) ) Fr (8, Zkmm Akm) 7o = Ao
(140)
km
sup bko (s) (lmmm)) BR. Zkm) sup sES
I'mm (s, Zkm A
Zo =2 =a
(141)
Zo = 2, Ao 7
ET
7
Am sup #ES
bom Hkmm)) - bum (8) 4km)
(142)
7 E
km sup SES
deon (s) HKm) bren 7km)
70= - 2, Ao =
(143)
1
7
ET
km
bem (-|Hkm) - Ba (.12km)
2o = 2, Ao =0
(144)
TV
E
km
bkm
Bkm
Tv
Zo = 2, A0
=
(145)
k=
where we use bkm and bkm to denote the random variables bem (-) and bamm (:) (17kk)), respectively. It illustrates that the aliasing bias can be bounded proportionally to the distance between the true belief and the approximate belief the bootstrapping timesteps. Then, we obtain,
-0-
11.
1 7m
km bbom
bkom
ITV
Zo =.
(146)
1
This concludes the proof.
Using Lemma D.I, we can prove Theorem 4, that recalled below. Note that some notations used in Appendix will be reused with another meaning.
Theorem 4 (Finite-time bound for symmetric m-step temporal difference learning (Cayci al., 2024)). For any agent-state /K' and arbitrary B 0,
policy E M., and any m E N, we have for Algorithm with
E || - -
1-1 S Edd + Eapp + Eshift + Ealias
(35)
where the temporal difference learning, function approximation, distribution shift, and aliasing terms are given by,
4B2 + ( + +B
Ed
(36)
2v ((1 7mm)
m
Eupp
min ||ʃ - Q² lla
(37)
m
FEFA
V 1-7 vildm. - dllrv
2
Eshill
B+
(38)
Ealias
E
|bem bko 1 II
Zu =
(39)
1
with -c..))-eesh d (=((,)))((a))) the sampling distribution, and dm (2) = di (s,2))((a2)) the bootstrapping distribution.
19

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
as shorthand for Q", Q' shorthand for Q as shorthand for Q" Q shorthand for Q" and QE shorthand for Q3 where the subscripts and superseripts remain implicit but assumed clear from context. When evaluating the Q-functions, to denote Q AR.i). . Ti. denote Q' (Z Ax,z). Qk. to denote Q Zz,,, Ak,i) and Qx.i to denote Qx Ag.s). and XR i to denote X AR. In addition, we define d shorthand for d' @ n, such that d(z, a) = d (2)= and dm as shorthand for dm @ such that (2,2,00 a) d (2) ( (a]2). Using the triangle inequality and the subadditivity of the square root, we have,
Proof. To ease notation for the proof of Theorem 3 in Appendix C,
go step further by using Qu
E -
S
E
11
+E
1
(147)
110 ]|[3
E
+ E
(148)
< - ब||
+
E
(149)
We can bound the second term in equation (149) using similar steps as the proof for the asymmetric finite-time bound (see Appendix C). We obtain,
K-1
E
②
|
S
Σ (As
+1
(150)
K
where I is arbitrary, and A is defined as,
2c 2u113
-
- x(xx
A
E
(151)
Similarly to the usymmetric case (see Appendix C), we consider the Lyapounov function C(3) = ||3,- - -9112 in order to find bound on k EK-1 (A, - 1)². We define G₁ o Zi.j Ar, k,j S m) and 3x o oZZk,o Ak.o). As in the asymmetric case (see Appendix C), we obtain, using to the law of total expectation,
E ([(++))) ((+)) [ - gx) Bx 11] +
E
1 6 6-11]]
(152)
Let us focus on the first term of equation (152) with [[ - -0.0BB.)))))) 1x- 1]. By conditioning on the sigma-fields 6 and Sx. we have,
m-1
E KG - B.,gk)) Bx-1] =
E
Σ
*2 Rg + 7 Q BR. Gx-1
Qn.o)
(QnD-QQi))
(153)
Note that, according to the Bellman operator (7), we have,
m 1
E
Σ
7 Rk.t
6x-1 10.007700
@ BR. B
(154)
It differs from the asymmetric case (see Appendix C) in that do not necessarily have Q= Q= here. By substituting equation (154) in equation (153), we obtain,
) [Rx, E [[Bx 3r,gk)
Bx-1]
E
m
Σ t=
B2. Bk-1 + *
@ J2, Ga-1 - (Φn.o -Qio)
2n.0
(155)
20

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
= (Qu. ""E @kim BR. 6x-1
+>" Qk.m
Q4.00 -xx00) (Qa. - 02.0) Bk, Gk.
(156)
= (Qe,0 -- @Tam - Qk. BR. 0k-1 Q0,0) (21,0- - + Q1.DD Qi.1)
(157)
(10x.0 - -Qx,0) 7"" ( @k.m - Qu.m Br. BR- 1) (1Qu.0- - Qn.0) + +Quu, Q2100)
(158)
= =-(Qu.o - -Qv,0)2 + - QQ 2k,o)
+y" @Qc. @k.m
BR. B (Qx.0 1Qx.0-QQx Qk.o) + + Qk... - -ia. 8k. Gx [0m-][@k.0 - - Qk.o).
(159)
We now follow the same technique in the asymmetric case (see Appendix C) for each of the four terms. By taking the expectation over 8G. we get the following.
For the first term, we have,
E
- -Qk,,0 -ho))
= - 2x
(160)
For the second term, we have,
E
(161)
For the third term, we have,
E - = -0( B+ )
² v Vllm -dl
(162)
For the fourth term, we have,
@+1,+(((tt (+(Bt112)) (1+ B 1 Ildd -dl (163)
E [Qk..
Qu.m (Qk, 21.0) (20))61111 $ - - -
By taking expectation over G of the four terms and using the previous upper bounds, we obtain,
[ B..ge gx>) - (1 -11- (1- + +>>))>>> o -
+ @1ll++21 27
B+ 1 1 Vldm - dlli
(164)
The second term in equation (152) is treated similarly to the asymmetric case (see Appendix C), which yields,
<1- + 2B
1
E |
S
(165)
By substituting equations (164) and (165) into the Lyapounov drift of equation (152), we obtain,
2
- -20
- -m
22(1 + ) --- Q +
+ 2B
1-
+ 4 B (+111) V |mm - dlyv
(166)
We can upper bound -
@ as follows,
-0--Q11 < 1000 -01, Q Q
(167)
21

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
- we can write, following a similar strategy as in the asymmetric case By setting = 2(1-7m)
1
(see Appendix C),
( 1 1- + 2B
2
E (((( - - -mm) (Ax -1)² -a +
B 1 1-7) )
2
+ +
V |dm - ddllv
(168)
By summing all drifts, rearranging, and dividing by 2aK(1 - ) we obtain after neglecting [(3x) > 20,
K-1
11:0 B=112
2
Σ (Ax
1)35
+ 12
2(1 - mmm) 1-7 + 2B
K
2a (1 - ym)
k=
27mh m
1
1 2
+ 1 7m
B
1-7)
||m dllTv.
(169)
The bound obtained through this Lyapounov drift summation can be used to further develop equation (150), using the subadditivity of the square root,
K (A: -)² +1
E
|
-
S
(170)
K k=0
1130 Bell2
a
21 +
+ 2B
V 2a0K11 (1 -mm)
V
2(1 m)
1
m
B +
|mm -dlliv
(171)
1- V
7m
1130 -Bu112
+
+ 2B
V 2arK11
mm
2(1 - 7m)
B 1
th
1- V |mm dllTv-
(172)
Plugging equation (172) into equation (149), and substituting back 1, we finally have,
E
Q
2
<
1130 Ball2
+
1 7m
(10-- 110 -10e-)@l)) *V 2(1 mm) 1-7
α
+ 2B
2aK (1 )
1 7m
2
Vlldm. all
110-0))
+ B 1 1-
(173)
V 1 --
1130- Ball2
1 7
( @0l= 2(1 pm)
+ 2B
/ 12K (1 m-
1- mm
+ B + V 1 1-
27m
Vlldmn dllTv + 1-am
2
Q - Q 1
(174)
Using Lemma D.I, we finally obtain,
E 11e - 2118
5
118o Ball2
1m m
1 -0-
a
+ 2B
22.K K( - m)
1 - mm
2(1 - mm)
1-
I I- )
2mm
Vlldm - dllTv
+
B +
1- gum
m
+
E
km
Bxm
bkm
Zo =
(175)
1 1-
1
TV
22

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
1180
Bell2
7
min
|| - 2lla
a
1-77 + 2B
2aK(1
ym)
1 ym
SEF
2(1 mm)
+
B
+
1-7m v Vlld dllTv
2
1
+ 1-ア
2
Am
[bem
bkmm 1
Zo =
(176)
By setting a= /R
and upper bounding 11:3 B.1l by 2B, we get,
4B2 +
- 1- + +2B
E 11e
1 7 min
|l 11l
2v 2vK(1 K(1
mm)
1-7mh SEFE
2mym
+ B+
ym v Vlldm - dllTv
+ 1
E
km
|0am brm
Zo =
(177)
This concludes the proof.
E. Proof of the Finite-Time Bound for the Natural Actor-Critic
Let us first give the performance difference lemma for POMDP proved by Cayci al. (2024). Note that this proof is completely agnostic about the critic used compute æ1, T2 IIM and is thus applicable both the asymmetric setting and the symmetric setting.
Lemma E.1 (Performance difference (Cayci et al., 2024)). For any two agent-state polices TI. E M.
(=0) y V=I(=))
(=o) -
Ed
(Z, = zo] + 1-7
inf (z0),
(178)
where,
1 (20) E T2
b
bk
Zo
(179)
k=0
Proof. The proof is similar the one of Cayci et al. (2024). First, let decompose the performance difference in the following terms,
TT (20) - V= (20) = =E T2
R
Zo
-V*((z))
(180)
1=0
E T2
(Ry - -. (2i) + V" (Z:))
2. = 2g
V" (20)
(181)
1=0
E T2
(R. - (R.-V*
/. (2,) + - (Ze-1)) 2o =
(182)
E n2
(R. + 7 (S 7+11) V (Zx)) 7o
+ T
Σ 2 (7 (TV=)(2+1)) ~ ( 2)+1) =
(183)
23

---

A Theoretical Justification for Asymmetric Actor-Critie Algorithms
E n2
? Re +0-=m (5441, (2e) 7o = 20
+ E ma
++1 (V (2++) (2++1) - (2++1) (S++1, Ze 2++1)) =0= 20+1))
(184)
Let us focus bounding the first term in equation (184). We have, for any T 0,
2
7 (R4 (4th < (1 (1-
< 00.
(185)
2=
By Lebesgue's dominated convergence, have,
T2
? (S+11.222)) (0.4))-vi((2 (Z,) Zu = 20
Σ E 2 + (6++) (2,)
20).
(186)
Then, by the law of total expectation, we have at any timestep 2,
E n2 [R, + 77/" (S++1, Ze+1) - V (2x) 2n = =0]
E
22
R4 + + (S++1,
Ze+1 (S)4,
1 Zz] - (2)) Zo = =0]
(187)
And, have,
E
+ -/ 2c]
Σ (10)))))) (s6,
(188)
$1,01
T2(a: 2+) (2), + Σ (
Σ =ma(aa==00'1a (2),
(189)
Σ Te(a, 2 (T + Σ (0
Σ (1
(190)
Se,
Tz (a (z),ai) + Σ - ((6l22))) TZ (")
(191)
By noting that sups,;
Da n2 (2(a)))
(s, 2) sups,z,a Q (8,2, - obtain,
E RR + Tr (S Ze+1 he, Zi =z]
=2(0 (z,, + 1-7 (e(-)he) ba b.(-1ze)
1
(192)
Finally, the expectation at time 2 can be written as,
Ta
Re + 7 R (St+1, 7 V (2))2
E
E T2 R + 777 (St+1, Z
H He, - V (2,) Zo = =2u
(193)
1
QTI (Zz, A,) +
|2((-11) - b.(.12))
- .. (Z+) Zo =o
(194)
1-7
1
= mm
A ATI (2,,
((H.))H))
6.(1
Zo = 2g
(195)
1 1-
24

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
Now, by using Lebesgue's dominated theorem in the reverse direction, we have,
E
2
(Re + 7V (5+1,
V (2:))
Zo 20
E 2
7 (A Ar)
Zo = 20
+
92
[6.
by
Zo = 20
(196)
TV
t=0
7 A (2, A,)
20 = 50
+
lat (zo)
(197)
t=
Now, let focus on bounding the second term in equation (184). We have, for any T>
2
(VT V (S
(1 71- 6.00
(198)
t=0
Using Lebesgue dominated convergence theorem, we can write,
T
1+1 (V ( Zo=
++ 22 [
(St+1, (S+1,, = zo]
(199)
By the law of total expectation, have at any timestep t 2 0,
E T V (Z--1) - (S Z Zo zol
E [ (1++1) - E - (S 1111)) 14 zo].
(200)
And, we have,
E (TT (S.41, He+1 = h Zo+1 = 2141,]
Σ beil (8 1 T (8
(201)
-V* +
Σ 1 V (2(41)
(202)
8141
-V (*++1+ +
Σ (044100411124411 (944)) - ((44))))))))))))))))))))))
(8441,2441
(203)
S++1
86t2
= =**1 +
Σ (8t+ b (st11
(0+ y (8441,2411)
(204)
From there, by noting that sup,,
7 (8,2)] S 1-7, we obtain,
E 22
(S++1, 24+ H++1 h4t1, Zet1 21+1,] 4Ta (2++1) - - - TV
(205)
Finally, the expectation at time t can be written as,
E Th [
(z+1) - y (S Z41)
[ (Zz+1) T2 - (S Z 20t1 =0]]
(206)
1
E
yT (Z(+1) - - 1 1
b+ He+1)) -b4-)))--22---
2o 20
(207)
25

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
| (+IH(()))41))) by (- (-12z+1)
|TV Zo
(208)
Now, by using Lebesgue's dominated theorem in the reverse direction, we have,
E R2
(V*: (Ze+1) - 2. ( 2(1)) Zo 20
66- (- - bl+1 1 (-12e+1) || Zo= 20
(209)
|oc( H1)) b,(() I.v - |bb(((EEb) - Zo)
Zo 20
(210)
| (1)) - (x(2)2))
Zo 20
TV
1
E
bo
Ho) bu (-1 (-1 || Zo 20
(211)
Tai (20)
E n2
bo(-1H6) 3o (-
||
Zo 20
(212)
Tmi (zo).
(213)
Finally, by substituting the upper bound (197) on the first term and the upper bound (213) on the second term into equation (184), we obtain,
2
(20 - V (20) E T
A (Ze, A1)
Zo = 20
+
c (20)
(214)
1-7
Eddaa [A (2, Ko =0 +
T2
(20).
(215)
1
inf
This concludes the proof.
Using Lemma E.I, can prove Theorem 5, that is recalled below. The proof from Cayci et al. (2024) is generalized the asymmetric setting.
Theorem (Finite-time bound for asymmetric and symmetric natural actor-critic algorithm). For any agent-state process M = (Z,U), have for Algorithm 2 with J C Bv1-1
n J and arbitrary B >>> 0,
V2N
(1-7) min [[J(=*)) (TT)] S Sna 25int + Coo Eactor 2c grad 2v6 ost<T
Te
(41)
where the different terms may differ for asymmetric and symmetric critics,
B3 + 2 2lg [A]
Enac
(42)
2VT
(2 BB
Eactor
(43)
(1-7)VN
EjuLasym
(44)
20
Einf,sym
bx
bx
(45)
TV
k=U
Egrad.asym
sup 0St<T
min Li (w)
(46)
26

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
E ggrdd.ymm
sup 0st<T
min (r(w), m
(47)
and critic is given in Theorem and Theorem 4.
Proof. The proof is based on Lyapounov drift result using the following I Lyapounov function,
A(T)= = Σ d (=)KL( (12)
(216)
2EZ
The Lyapounov drift is given by.
d= (2) Σ x (alz) Te(a|z) T011(a
A(T+41)- - A(Ti) = Σ
(217)
#E2
oEA
Te(aa))
Σ dh (z,a)log
(218)
(at1()lz)*
Since supz,a (1)(2,))222 I 1, we have that log (a)2)) is 1-smooth (Agarwal al., 2021), which implies,
1
log (a|=) S log ne, (a|z) + Vologmo, (a|z), 01) + 2 1 01112.
(219)
By selecting 02 0, and 01 -0+1 and noting that 0p+1 02 - - - En=o Wh,n obtain,
(al=) log
2
1 17 V log ग. (cl2),
(220)
(a
Now, we separately bound the Lyapounov drift for the asymmetric and symmetric settings. In the following, some notations are overloaded across both setting when their meaning is clear from context. For the asymmetric setting, we have,
A(Te+1) A(Te) Σ d=' (z,a) log (a(a)) Te+ 1 (a|z)
(221)
2
|0
1) Σ (z.o\Tologm(aaa))..)
(222)
2
2,4
2 2
B
Σ
d (s,,,, - Ed'
En
11
(223)
1
2
Σ
d= d= (s,2,))
+n) Σ dt (s,2,a) ((Vologm((a))).0) - as,
2
8,2,a
2,0
(224)
For the symmetric setting, we observe instead,
( Σ d (z,a)log <x(a/2) T (a/z)
(225)
2
< B² 2
Σ d=
d" (z,a)y ([Volog A (2,a))?
(226)
2,0
2,a
Now, let 5t denote the sigma field of all samples used in the computation of ग. (which excludes the samples used for computing wy), along with all the samples used in the computation Q=, We define the ideal and approximate loss functions, both in the asymmetric and the symmetric setting,
(w) [(VV log TI (oglll/mmm()))....)
4tt (S, 5.
(227)
27

---

A Theoretical Justification for Asymmetric Actor-Critti Algorithms
[,(w) = E
(No 2 83.
(228)
(w)) = E (x)
5.
(229)
(,w)) = E - -)) [/]
(230)
Because E. ||
-
1h 1|
51
< B O Q* 1 {5
the error between the asymmetric advantage A and its ap-
proximation A upper bounded by,
E (S, 2. -5.24)))44((S..2. (S.
E
|| A 11 57c
(231)
EE
|1 Dire Q + V5r 11:
(232)
E
11 Q + +.+ - Di 1 1.5
(233)
E
|1 - -
11
+ || - Dive l|
5),
(234)
|
-
Q
|1
54 +
E
[||
Do.
11
50
(235)
25 critic.asym
(236)
where Th the symmetric advantage and its approximation Á is upper bounded by.
criticassm u.aaym aappassm + + shiflasym is given by the upper bound (29) in Theorem 3. Similarly, the error between
-.
E
(2, - A3 [2, A))²
5.
< 26 21 criticsym"
(237)
where - Syritic.sym =td.sym + _T spp.ym
+ T
shift.sym
Ealias,sym
is given by the upper bound (35) in Theorem 4. By using the
inequality (ar + y)² S 2x 2n²
C, (w) E ((V log n. (AIZ), - [5:]
(238)
E ((Volog (A| A5..AA))) + (4
(239)
2E ((V ((VologTi (A -A" [. + 2E (S,
5.
(240)
<DC, ()) + 2(2 nt ceiiccasym)
(241)
Similarly, we obtain in the symmetric case,
(u(w) S (w,(w) + 2t cyic. )
(242)
Starting from the ideal objective and following a similar technique, we also obtain,
(w) (2,( 2 L,(w) < (w) + 2(2 cyilicaym )²
critic asym) )²
(243)
(244)
By using Theorem 14.8 in "Shalev-Shward & Ben-Da 2014) with step size - wy under the asymmetric loss and symmetric loss, respectively,
BV-
we obtain for the average iterate
V2N
(w,)) S S + min [(w)
(245)
L, (w.) < Sector
min Lc(w),
(246)
2
28

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
where 22
(2-n) B
On expectation, for the ideal asymmetric objective Lt, we obtain,
2(1 2(1-7)vN'
B 2. + 2 ( critic.asym )
(247)
2 +2
min [w) - 2 critic.symm
)
(248)
1|w|| B
< 2:2 actor
+ 2 min C((w) + 2(25 _t 1
critic.ssm )2
+ 2 2 critic
(249)
26 2o + 4 min (w( 6(2 arimic 11rll25B
(250)
2
25 2
4
The grddasssm
6 6(2 cntii 2
(251)
where we define the actor gradient fuunction approximation error as,
the grad.asym
min L(w)). 1
(252)
Similarly, we obtain on expectation for the ideal symmetric objective Lt.
E
< 22
+ +4 ( grad.sym
{
+ 16(2Eritic.syn
(253)
where we define the actor gradient function approximation error as,
) min L((w). 1wll
St grad.sym
(254)
Now, let us go back to the asymmetric and symmetric Lyapounov drift functions of equation (224) and (226). First, assume that there exists 3o < do such that sup120 [[C;) S Co with,
d= (s,z) (a|z)
C sup
(255)
a (s, 2 To (alz)
Second, we leverage the performance difference lemma to bound the advantage. For the asymmetric setting, the performance difference lemma for MDP (Kakade & Langford, 2002) holds because of the Markovianity of Ze).
(1 (1-7)( 7) (VT (so. =0) - V (80, 20)) (80,
= EAd [AT (S,2,A))So = 80, Zo 2o).
(256)
We note that E. [V** Zo) V (So, [=((==) ( )], such that,
-Ed" (S, = - 7) (1+) + Eif.asym:
(257)
=](1-)
(258)
where Emfasy 0. For the symmetric setting, using Lemma E. with T2 π² and क Te, we note that,
(1 1-7)((=+ (zo) VTL v=T(())) < E"d (Z,)(2) =o] + 2e (zo);
(259)
which implies.
(20) - v= + 26 (20). Edd " [AT (Z, = = (1-1) (20)
(260)
We note that E | (Zo) - V* (2o) = =[(((T)) - J(T)) and we denote E | (Zo) with Eint,sym so that,
Eill.yym = E
E"
* by
by
Zo = Zo
(261)
29

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
E
bE
(262)
TV
By rearranging, we have,
Edd [ATt =1 [[(e]]] + 26.nssym-
(263)
Note that Ex,,, d (s, = s,,aa (3,50)))))
d (3,2,0)
d 2s) (8) ( SC d (8,, for positive
f. Taking expectation over the asymmetric Lyapounov drift of equation (224), we obtain using equation (255),
1 B² D
[(((T)1) - A(TT)1
d' (2,0)4
2
2,a
Σ d" (s,2,a) (VVolo)a( - 2,)
+ 1)
(264)
,,2,a
11 B² 7(1 ( E [J(TT)] [ + 27
2
n 2 + - (grnd.sssm)
2 + + critic.ssm )
(265)
11 B² - (1)1- ( + 2
2
+ (V2enctor + 26 grad,asym + +2V6E TT
anitic,ssm)
(266)
Similarly, taking expectation over the symmetric drift of equation (226), we obtain similar expression,
722 B
((A(T44))A(gs A(TT)]
Σ d= (2,0)A=((,aa)
2
17
Σ dx (z,a)y ([Vplogz((a)2)).. A AT (2,a))²
(267)
2,a
2
B² ([] -((r)) 21jeinfssy
2
+ 00 (V2cacurr + 25 grad.sym
2v 2 (ieii..symm
(268)
Given the similarity of equation (266) and equation (268), in the following denote the denote the upper bounds using End "grad and ciitic irrespectively of the setting (i.e., asymmetric or symmetric).
By summing all Laypounov drifts, we obtain,
2 E[A(Tr) A(To)) < T B² 10mmn11-- -1) 7) Σ
- Tn Ent
1=0
+ 1) Σ 0oc (vee + 25 + 2 6E at
(269)
grad
critie
<T" 2
7-1
B²-
11(1 (1117)
Σ B[J(x*) [[T])] + Ten
2
t=0
T-1
T-1 Σe 1=0
+ 00
VVTT' Exctor + 2
gnd + +266
E
(270)
1=0
Since To is initialized at the uniform policy with 0 Po:=0, 0, we have,
A(TO)= =
(moo=Ea d= (--L=(=((-=)) m=(+)))
(271)
2E2
30

---

A Theoretical Justification for Asymmetric Actor-Critic Algorithms
Σ
d= (2)
Σ
n"
Σ aEA
x (al3)
(272)
*E2
DEd
Σ #E2
d (z)
Σ
x [al=))lo - Σ x (a|2)
1
(273)
[AA
aEd
aEA
Σ EE2
d (=)
Σ
T" log (a|z) + log [A]
(274)
aad
Σ d
(2)
(log Al H (+1=))
(275)
xE2
Σ 2EZ
d
(z) |
(276)
log |A|
(277)
where denotes the Shannon entropy. Rearranging and dividing by n/', we obtain after neglecting [(Tr)
1 (1 (1-2) (1-1) Σ
-
S
log Lgg
nTT + B² + 2m
(V2emourr
T-1
T-1
+ 0o
+
2 grad +
+2V6
tr critic
(278)
T 1=
T t=0
It can also be noted that mingserr [x,] 7 21= 22, which implies that,
(1 7) min
-(())))-[(T)]] J(T))
log |Al
"" B² + 22
0st<T
r/T
2
(2eaauor + 2
1
Σ
+ 2v6
1
Σ
Te
(279)
T
grad
T
1=0
1=0
Let us define the worse actor gradient function approximation error,
Egrad
TTe sup 0st<T
grad
(280)
sup 0
min Lww,,
(281)
||
and let us note that,
Tee gndd
< grad
(282)
By setting 7 vT we obtain,
log |A
B²
(1 min 0stST
E[J(x*) J(m,)]
+
+ 20inl
VT
2vT
T-1
T-1
+ C
(VDemoor
2
T
1
Σ
Ji
grad
+
2v6
Σ
citii
(283)
B² 2log |Al
+2E
α Σ
16 by lall
2VT
(v
(2-7))
T
+ +Co0
+ 28 grad + 226
Σ
Tee critic
(284)
(1-7)VN
T
t=0
This concludes the proof.
31


Reviews:
[{"review_id": "RictYibI4E", "reviewer": "Reviewer_VgVc", "summary": "This paper provides a finite-time analysis of asymmetric AC approach in POMDPs, showing that leveraging privileged state information during training eliminates uncertainty errors inherent in symmetric critics. Theoretically, it compares convergence bounds for asymmetric/symmetric critics, proving that asymmetric critics remove the so called aliasing term which comes form the uncertainty inherent in symmetric critics.", "questions": "", "limitations": "", "rating": 3, "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": "Dear Reviewer,\n\nThank you for your review. We are glad that you found the results interesting and the paper clear. Please find our answers below.\n\n**Aliasing.** We acknowledge a confusion in our paper about the definition of aliasing. We agree that aliasing could refer to the fact that an history $h$ corresponds to the different environment states $s$. However, it would not pose any problem since $h$ is the Markovian state of an equivalent MDP: the \"history MDP\". We instead think that (perceptual) aliasing should be understood as the fact that an observation $o$ (or an agent state $z$) corresponds to different $h$. This is a direct consequence of $o$ (or $z$) being non Markovian. As a consequence of aliasing, the fixed point $\\tilde{Q}(z,a)$ is not equal to $Q(z,a)$. We also referred to this as aliasing, but we agree that we should call this the aliasing bias. Then, Lemma C.1 highlights in (139) that the aliasing bias $\\lVert\\tilde{Q}-Q\\rVert$ is given by the difference in distribution of $s$ at the bootstrapping timestep $m$, depending on whether we condition on $z_m$ or $h_m$. This bias is then upper bounded by the TV between these distributions times the maximum rewards. We call this term the aliasing term.  Cayci et al. (2024) try to mitigate this bias using multistep TD learning, while we show that the problem disappear when considering asymmetric learning. **We propose to revise the paper by fixing the naming convention for these three aspects (aliasing, aliasing bias, aliasing term), and by better discussing the origin of aliasing.**\n\n**Variance effect.** We agree that, with the law of total variance, for any $\\Pr(S,Z)$, any $z\\in\\mathcal{Z}$ and any $a\\in\\mathcal{A}$, we have $\\mathbb{E}[\\mathbb{V}[\\sum_t\\gamma^tR_t|S_0=S,Z_0=z,A_0=a]]\\leq\\mathbb{V}[\\sum_t\\gamma^tR_t|Z_0=z,A_0=a]$. It could suggest that using $Q(s,z,a)$ instead of $Q(z,a)$ in the PG will provide less variance. However, this neglects the variance of the estimator $\\hat{Q}(s,z,a)$ that may have a higher variance than $\\hat{Q}(z,a)$, since it is learned on fewer samples. In conclusion, it not clear what will be the effect of the variance of the target value functions, and we consider this study out of the scope of this paper. We also highlight that the claims on the effect of variance from Baisero & Amato (2022) differ from these from Sinha & Mahajan (2023), which further motivate an empirical study. Anyway, our bound is given on average over the complete learning process, whatever the variance of the learning targets. It thus still gives an indication on the worse case average performance of asymmetric learning compared to symmetric learning, even if there is more/less variance in the targets. **We can expand the discussion in the paper if you find it will be useful.**\n\n**Learning the update.** The analysis perfectly holds for an agent state process $\\mathcal{M}$ learned through RL. By (i) extending the action space $\\mathcal{A}$ with the agent state space $\\mathcal{Z}$: $a^+=(a,z')$, (ii) extending the agent state $\\mathcal{Z}$ with the observation space $\\mathcal{O}$: $z^+=(z,o)$, and (iii) considering an update $U$ that transition to the selected agent state: $z^{+'}=(z',o')=U(z^+,a^+,o')$ where $a^+ = (a,z')$, we can explicitly learn an update by selecting both the environment action and the next agent state $a^+=(a,z')\\sim \\pi^+(·|z,o)$. In the conclusion, we discuss a more general version of this where the agent can learn a stochastic update. In both cases, the analysis goes through, we are just selecting a particular POMDP and update $U$. **If you feel that this is not clear, we can discuss this further in the paper.** We acknowledge that this is different from the usual way of learning $U_\\psi$ with an RNN and BPTT. However, even when using an RNN, we always consider a fixed $\\mathcal{M}$ to learn from (usually a window, on which we do BPTT). The analysis for a learned $\\mathcal{M}$ can thus be cast as the problem of learning nonlinear features of the window $z$, where the nonlinear feature $\\psi(z,a)$ is an RNN. **We propose to add this discussion in the paper.**\n\n**Toy experiment.** We agree that an empirical validation of the findings of this paper could be interesting. However, given the short rebuttal period, it will probably not be possible to obtain these results on time. We hope that you will still consider the results interesting and worthy of publication.\n\n**Nonlinear approximators.** This is an interesting future work. Moreover, as discussed above, this analysis could also embed the analysis of a learnable RNN, by considering a fixed window as the fixed agent state process. This follow-up work could perhaps build on the analysis proposed by Cayci & Eryilmaz (2024a, 2024b). **We propose to adapt the discussion about future works to make that more clear in the paper.**\n\nWe hope that these discussions will have answered your questions. Please do not hesitate to ask us to develop further if something was not clear.", "claims_and_evidence": "The claim of uncertainty error of the symmetric critic is well supported and provided with formal proof.", "methods_and_evaluation_criteria": "This paper do not propose methods or included evalution.", "theoretical_claims": "I checked for the correctness of the theoretical claims, the proofs seem well-established, well-organized and error-free.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This work is a relatively small patch on the popular AC method, turning what's previously floating intuition into solid terms, this work have the potential for summoning further theoretical works on asymmetric AC.", "essential_references_not_discussed": "It seems that the paper is citing all the prominent related works.", "other_strengths_and_weaknesses": "I appreciate that fact that the paper is highly well-written, the presentation is logically structured, with well-defined notation with a very focused narrative. The finite-time bounds (Theorems 3–5) are derived meticulously, extending prior NAC analyses (e.g., Cayci et al.) to asymmetric settings loosely following the style of Baisero et al.. The connection between aliasing and critic bias is clearly formalized.\n\nNevertheless, I would like to comment that aliasing in POMDPs may be usually understood as aliasing multiple histories into one state, emphasizing on a many-to-one relationship as suppose to differences in belief distributions; hence I consider the term to be a bit abused in this paper. The core idea—using privileged state information to mitigate aliasing—echoes Baisero & Amato, who used h instead of z; while the analysis is novel, the conceptual leap is modest. Now, moving to the theoretical results, although we understand that we are short of one error term, one is to be uncertain whether the difference in error can be made up by less variance in learning targets, and there are no further discussion or tests on such fronts.", "other_comments_or_suggestions": "How would the bounds change if the agent state process M is learned (e.g., via RNNs) rather than fixed?\nI would suggest including toy domains as a sanity check, could simple synthetic POMDPs (e.g., darkroom) illustrate the impact of the uncertainly error?", "questions_for_authors": "Could the analysis be extended to non-linear function approximators (which is common), where aliasing might interact with approximation errors differently, at least include a few sentence of discussion?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "zy6keSQYiD", "reviewer": "Reviewer_Y2Go", "summary": "This paper provides a theoretical justification for the empirical success of asymmetric actor-critic algorithms in partially observable environments. Using finite-time convergence analysis, the authors prove that asymmetric critic methods (which leverage additional state information during training) eliminate an \"aliasing error\" term that appears in symmetric methods. This error term arises from the difference between the true belief distribution (given history) and the approximate belief distribution (given agent state). The mathematical analysis demonstrates that this is the only difference in the error bounds between asymmetric and symmetric approaches, providing a clear theoretical explanation for why asymmetric methods often converge faster and perform better in practice.", "questions": "", "limitations": "", "rating": 4, "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": "Dear Reviewer,\n\nThank you for your review. We are happy to read that you appreciated our manuscript and that you considered that we addressed an important gap in the theoretical understanding of these methods. Please find our answers below.\n\n**Toy experiment.** We agree that an empirical validation of the findings of this paper could be interesting. However, given the short rebuttal period, it will probably not be possible to obtain these results on time. We hope that you will still consider the results interesting and worthy of publication.\n\n**Clarity.** After proofreading Lemma C.1, we completely agree that some things needed to be improved to help the reader understand the philosophy of the proof, and the origin of aliasing. In particular, we think it would be useful to justify the initial expression of $Q$ and $\\tilde{Q}$, which would help understanding that the bias comes from the difference in distribution at the bootstrapping timestep $m$, when we condition on $z_m$ versus $h_m$. **We propose to add this discussion in the proof of the Lemma.**\n\n**Related Works.** We are not sure what papers you wanted to refer exactly. We found papers with the same titles but different bibliographic data. Could it be that you wanted to refer the papers \"Information Asymmetric in KL-Regularized RL\" (Galashov et al., ICLR 2019) and the paper \"Learning with Privileged Information for Eﬃcient Image Super-Resolution\" (Lee et al., ECCV 2020)? **We definitely think that the first paper would be worth mentioning in the introduction.** Regarding the second one, we feel like discussing this vision paper may not be that much relevant. Please note that we already mentioned seminal \"teacher-student\" approaches in RL in our introduction (Choudhury et al., 2018; Warrington et al., 2019).\n\n**Nonlinear approximators.** This is an interesting future work. Moreover, as discussed above, this analysis could also embed the analysis of a learnable RNN, by considering a fixed window as the fixed agent state process. This follow-up work could perhaps build on the analysis proposed by Cayci & Eryilmaz (2024a, 2024b). **We propose to adapt the discussion about future works to make that more clear in the paper.**\n\n**Aliasing.** We acknowledge a confusion in our paper about the definition of aliasing. We think that (perceptual) aliasing should be understood as the fact that an observation $o$ (or an agent state $z$) corresponds to different  $h$. This is a direct consequence of $o$ (or $z$) being non Markovian. As a consequence of aliasing, the fixed point $\\tilde{Q}(z,a)$ is not equal to $Q(z,a)$. We also referred to this as aliasing, but we agree that we should call this the aliasing bias. Then, Lemma C.1 highlights in (139) that the aliasing bias $\\lVert\\tilde{Q}-Q\\rVert$ is given by the difference in distribution of $s$ at the bootstrapping timestep $m$, depending on whether we condition on $z_m$ or $h_m$. This bias is then upper bounded by the TV between these distributions times the maximum rewards. We call this term the aliasing term. **We propose to revise the paper by fixing the naming convention for these three aspects (aliasing, aliasing bias, aliasing term), and by better discussing the origin of aliasing.** In addition, we agree that some other key concepts could be better introduced in the background. **We propose to improve the background to better explain and illustrate with examples what could be typical observations, agent states, environment states update functions, and what would be aliasing in this context.** We could notably use the example discussed in our response to Reviewer UL7j.\n\nWe hope that these explanations will have answered all your questions. Please do not hesitate if you want us to further elaborate on something that was unclear.", "claims_and_evidence": "The paper claims that asymmetric actor-critic algorithms eliminate an error term due to aliasing, leading to improved convergence compared to symmetric algorithms. It also claims that the theoretical bounds hold for finite state policies and linear function approximators.\n\nThe claims are supported by mathematical analysis:\n1. Formalize both symmetric and asymmetric actor-critic algorithms\n2. Derive finite-time bounds for both approaches\n3. Identify the specific error term (aliasing error) that exists in symmetric but not asymmetric methods\n4. Show that this is the only difference between the error bounds\n\nThe paper lacks empirical validation.", "methods_and_evaluation_criteria": "**Methods:** The theoretical approach is sound for analyzing the problem. The authors adapt existing convergence analysis techniques to both symmetric and asymmetric settings, enabling direct comparison. The mathematical framework correctly models partially observable environments and agent behavior.\n\n**Evaluation Criteria:** The evaluation is purely theoretical, with no empirical experiments. While the theoretical bounds are well-justified, the lack of empirical evaluation limits the practical relevance of the results.", "theoretical_claims": "I verified the key theoretical claims, particularly:\n\n1. **Theorems 1 and 2 (Natural Policy Gradients)**: The proofs correctly show that both symmetric and asymmetric approaches optimize similar objectives. \n2. **Theorem 3 and 4 (Finite-time bounds)**\n3. **Lemma C.1 (Upper bound on aliasing)**: The derivation connecting aliasing error to total variation distance between belief distributions is mathematically sound.\nThe mathematical analysis is rigorous, though some proof steps could benefit from additional explanation for clarity.", "experimental_designs_or_analyses": "The paper does not include experimental validation, which is a significant limitation.", "relation_to_broader_scientific_literature": "This work connects to several research directions:\n\n1. **Asymmetric learning paradigms**: Builds on prior work by Pinto et al. (2018) and Baisero & Amato (2022), providing theoretical justification for previously heuristic methods.\n2. **POMDP solving**: Relates to approaches for partially observable environments, complementing techniques like recurrent neural networks and belief state modeling.\n3. **Convergence analysis**: Extends finite-time bounds from Cayci et al. (2024) to the asymmetric setting.\n4. **State representations**: Has implications for representation learning in POMDPs and the benefits of leveraging privileged information.", "essential_references_not_discussed": "The paper covers the most relevant literature, but could benefit from discussing:\n\n1. **Information-theoretic approaches to POMDPs**: The paper by Eysenbach et al. (2023) \"Information Asymmetry in KL-Regularized RL\" (NeurIPS 2023) directly addresses quantifying and mitigating observation aliasing through an information-theoretic lens, showing how information asymmetry creates similar benefits to the asymmetric actor-critic approach. This work provides complementary theoretical insights about the same underlying issue.\n\n2. Chen et al. (2020) \"Learning with Privileged Information for Efficient Image Super-Resolution\" (ECCV 2020) employs a teacher-student framework with privileged information during training that closely parallels the asymmetric actor-critic approach. Their theoretical analysis of knowledge distillation in asymmetric settings could provide useful insights for reinforcement learning.\n\nBoth works approach the problem of leveraging privileged information during training from different angles and could strengthen the contextual understanding of asymmetric learning approaches.", "other_strengths_and_weaknesses": "**Strengths:**\n- Clear identification of the specific mathematical advantage of asymmetric methods\n- Rigorous theoretical analysis with well-defined bounds\n- Addresses an important gap between empirical success and theoretical understanding\n\n**Weaknesses:**\n- Restricted to linear function approximation and finite state policies, limiting applicability to deep RL\n- Lacks empirical validation even in simple environments", "other_comments_or_suggestions": "### Suggestions for Empirical Validation\nThe theory could be empirically validated with a simple, specific POMDP grid world environment:\n\n#### **Setup**:\n- **Environment**: 5×5 grid with deterministic movements.\n- **True State**: Full (x, y) position of the agent.\n- **Observation**: Limited 3×3 visual field centered on the agent, showing wall/path/goal.\n- **Controlled Aliasing**: Multiple visually identical room patterns are deliberately placed in different positions (e.g., hallway segments that look identical but lead to different rewards).\n- **Precise Aliasing Mechanism**: The environment uses a fixed set of 3×3 templates that repeat in different locations, creating true state aliasing.\n\n#### **Control Parameter**:\n- Vary the template repetition frequency (e.g., 10%, 30%, 50% of states share identical observations with at least one other state).\n\n#### **Experiment**:\n1. Compare symmetric critic (using only observations) vs. asymmetric critic (with access to true x,y position)\n2. Measure learning curves, final performance, and sample efficiency\n3. Calculate belief state entropy at each position to quantify the actual impact of aliasing \n\nThis controlled environment would directly test whether the performance gap between methods increases proportionally with aliasing severity, as predicted by the theoretical bounds in **Theorems 3 and 4**.\n\n---\n\n### Suggestions for Improving Accessibility\n\nProvide more intuitive explanations of key concepts, such as aliasing, to make the paper more accessible to a broader audience.", "questions_for_authors": "1. Could you provide empirical validation of your theoretical findings in a simple environment with controllable degrees of aliasing? This would help verify that the performance gap between symmetric and asymmetric methods increases with aliasing severity as predicted by the theory.\n\n2. How do your theoretical results extend to non-linear function approximation as commonly used in deep RL? The current analysis is limited to linear approximators.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "azsTGBeCao", "reviewer": "Reviewer_UL7j", "summary": "This paper analyzes two different versions of a natural actor-critic method for learning policies in finite POMDPs. The first version is \"symmetric\": both actor and critic depend only on the internal agent state. The second version is \"asymmetric\". Here, the critic depends also on the underlying environment state, a privileged information that is often available during training. The authors prove convergence bounds for both methods, and show that the asymmetric method has an edge over the symmetric one.", "questions": "", "limitations": "", "rating": 4, "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": "Dear Reviewer,\n\nThank you for you review. We are happy that you found the paper convincing and accessible. Please find our answers below.\n\n**Minor remarks.** All your remarks and typos were valid. The set needs to be closed, we can assume it strictly convex to ensure the uniqueness of the projection. We consider distributions with full support, which is reasonable regarding the policy parametrization (no action has a zero probability). Log-linear policies indeed denote policies whose logarithm is not linear in $\\theta$. In Thm. 5, $R$ should be $B$ in the definition of $\\zeta$. Finally, $b_k$ and $\\hat{b}_k$ are not related to the subroutine, but are well-defined random variables. **We will clarify all this.**\n\n**Aliasing Bias.** An example where $Q^\\pi(z,a)$ is not equal to $\\tilde{Q}^\\pi(z,a)$ is the following POMDP with $z_t=o_t$. There are two starting states (L or R), that are observed perfectly. Any action taken from these states always yields a zero reward. The agent can switch to the other starting state, or go to the corresponding absorbing state (G or P). In the absorbing states, he stays there forever with the corresponding reward (±1). The policy is $\\pi(a|z)=go,\\forall z\\in\\mathcal{Z}$. It gives $Q^{\\pi}(o=L,a=down)=\\frac{\\gamma}{1-\\gamma}$ and $\\tilde{Q}^\\pi(o=L,a=down)=0$ because $\\tilde{Q}^\\pi(o=D,a=\\cdot)=0$. **If you think this example would be worth being added to the paper, we would be happy to do so.**\n- $O(L|L)=O(R|R)=1$\n- $O(D|G)=O(D|P)=1$\n- $R(+1|G,:)=R(-1|P,:)=1$\n- $R(0|L, :)=R(0|R,:)=1$\n- $A=\\\\{swap, go\\\\}$\n\n**IID samples.** We tried deriving the proof for correlated samples (with the usual assumption that we have reached a stationary distribution) following similar steps as [Bhandari et al. (2018)](https://arxiv.org/abs/1806.02450). While it is feasible to derive this proof for the asymmetric critic, the symmetric setting seemed more subtle and we did not succeed. It would thus have prevented a direct comparison. We can cite a concurrent work [(Cai et al., 2024)](https://arxiv.org/abs/2412.00985) that does not make the IID assumption. However, it uses an explicit belief approximation, which makes the comparison with standard asymmetric AC difficult. **Despite not required by the concurrent work policy of ICML, we propose to discuss this reference, because we believe it is an interesting related work.** Please note that Thm. 3-4 could be straightforwardly adapted to any distribution instead of $d$, provided that we still sample IID.\n\n**NPG Objective.** The NPG $w_\\*^{\\pi_\\theta}$ is considered a good choice, motivated in the literature from a long time [(Kakade, 2001)](https://papers.nips.cc/paper/2073-a-natural-policy-gradient). It can be seen as a standard PG, but where we select an appropriate metric for the parameter space. However, since computing the Fisher information matrix is not trivial, we prefer to minimize these simple convex losses ($\\mathcal{L}$ and $L$), which are both proven to be minimized by the NPG $w_\\*^{\\pi_\\theta}$. **We propose to better explain the NPG in the paper, to make things more clear for the reader.**\n\n**Concentrability coefficient.** Eq. (39) shows a concentrability coefficient, assumed to upper bound the ratio of probabilities between the optimal policy and any policy $\\pi_t$. It roughly states that the policy should be stochastic enough so as to visit all state-action pairs from the optimal policy with nonzero probability throughout the learning process. Thm. 5 states that the lower this concentrability coefficient, the lower the upper bound on the suboptimality. It notably motivates the initialization of the policy to the max-entropy policy. **We propose to add a better explanation of this hypothesis in the paper.**\n\n**Insensitivity to aliasing.** Given the current analysis, you are totally right, we overlooked the $\\epsilon_\\text{inf}$ term and the claim was too strong. However, after double checking, you pointed out something interesting: this term can be removed in the asymmetric case. Indeed, we could stop at equation (222) instead of (223) so that we keep $A^\\pi(S,Z,A)$ instead of using $A^\\pi(Z,A)$. Then, in (256-258) we can use the MDP version of Lemma D.1 with $A^{\\pi^+}(S,Z,A)$ instead of $A^\\pi(Z,A)$, where $\\pi^+$ is defined as in Appendix A.1, which does not have the $\\epsilon_\\text{inf}$ term [(Kakade & Langford, 2002)](https://homes.cs.washington.edu/~sham/papers/rl/aoarl.pdf). Finally, when substituting back (258) in (260), it would make this term disappear from the final result. **While the previous proof was valid, this result is even stronger, and we could add this improvement to the paper.** We also agree that we should not claim that asymmetric learning is insensitive to aliasing, but that we have an *upper bound* that is not dependent on the level of aliasing. **We will fix that in the paper.**\n\nWe hope that these discussions will have answered your questions. Please do not hesitate to request additional explanations.", "claims_and_evidence": "All claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "This is a purely theoretical paper.", "theoretical_claims": "I checked the results for obvious flaws, but did not read the proofs in detail.", "experimental_designs_or_analyses": "This is a purely theoretical paper.", "relation_to_broader_scientific_literature": "The authors clearly position their work within the context of the existing literature.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "The paper is very well written. I had no problem following despite not being very familiar with the prior works. Additionally, the result is interesting and seems very relevant.", "other_comments_or_suggestions": "### Minor comments\n- Section 3 (nitpicking): I assume that the set $\\mathcal C$ closed and convex, such that the projection is properly defined? Also, do you assume that $\\mu$ has full support? Otherwise $\\lVert\\cdot\\rVert_\\mu$ is technically a seminorm (not sure if this is relevant).\n- Section 3.1: I don't think you defined the distribution $d$ in the expressions $\\lVert\\cdot\\rVert_d$. Is it simply $d(s, z, a) = d^\\pi(s, z)\\pi(a | z)$?\n- Section 3.2: I suppose now $d(z, a) = \\sum_{s \\in \\mathcal S} d^\\pi(s, z)\\pi(a | z)$?\n- Eq. 16: Typo: $\\mathcal F^B_\\chi$\n- Eq. 19: Why is $\\pi_\\theta$ \"log-linear\"? Specifically, is $\\log \\pi_\\theta$ really a linear function of $\\theta$, even though it includes a log-sum-exp term?\n- Section 4.1/4.2: Typo: the errors of the Q-function should be measured by a seminorm weighted over not just states and agent states, but also actions, (e.g. the norm $d^\\pi(s, z)\\pi(a | z)$). The equations here (e.g. Eq. 28) just use $d^\\pi$.\n- Regarding the aliasing error (Eq. 38), does the expected distance between the beliefs depend on $k$? If not, the expression inside the weighted norm could be simplified as $\\frac{1}{1 - \\gamma^m}\\mathbb E^\\pi[\\lVert\\hat b_{0, m} - b_{0, m}\\rVert]$\n- Eq. 39: I assume that $\\pi_t \\doteq \\pi_{\\theta_t}$?\n- Theorem 5: What is $R$ in the definition of $\\zeta$? (Is it the maximum reward?)\n- In $\\varepsilon_{\\mathrm{inf}}$, what are $\\hat b_k$ and $b_k$? (Does it refer to the subroutine Algorithm 1 inside Algorithm 2?)", "questions_for_authors": "- Line 163 (left column): This is an interesting point. Are you saying that the symmetric Q-function $Q^\\pi$ generally does not satisfy the $m$-step symmetric Bellman equation? Is there a counterexample?\n- Algorithms 1 and 2 assume i.i.d. sampling from $d^\\pi$. In a more realistic setting, the samples are generated from online interaction with the environment. Did you consider this setting as well?\n- What is the motivation for the \"asymmetric obective\", Eq. 22? If I understand correctly, you want to justify why $w_*^{\\pi_\\theta}$ is a good parameter update (\"it minimizes this loss\"). Or are you introducing the loss function $\\mathcal L$ for another reason, namely that $w_*^{\\pi_\\theta}$ is a minimizer of $\\mathcal L$ and $\\mathcal L$ can be more easily optimized than solving equation (20)?\n- Can you give some intuition about the assumption Eq. 39?\n- Line 356 (left column). What do you mean by \"asymmetric learning is insensitive to aliasing in the agent state\"? Clearly also asymmetric learning is impacted by the error that comes from incomplete state information. (For example, $\\varepsilon_{\\mathrm{inf}}$ captures some of this error). Additionally, this sentence sounds a bit as though you prove that asymmetric learning is better than symmetric learning. However, the paper presents only upper bounds on the risk, meaning that no such conclusion can be drawn (this would require lower bounds). Could you comment on this, and how much you think this conclusion (\"asymmetric is better than symmetric\") to depend on the specific algorithm?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YYV1yj9yEc", "reviewer": "Reviewer_rwhu", "summary": "This paper investigates reinforcement learning in partially observable environments. The authors present finite sample analysis for neural actor-critic methods, comparing both asymmetric and symmetric critics. Their findings elucidate the relationship between the use of an asymmetric critic and the reduction of aliasing errors in the agent state.", "questions": "", "limitations": "", "rating": 4, "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": "Dear Reviewer,\n\nThank you for your review and for hihglighting that we attain state-of-the-art convergence rate. Below, we answer to your remarks.\n\n**Environment and agent states.** We agree that some other key concepts could be better introduced in the background. The environment state is typically inaccessible to the agent, which is provided with a stream of observations instead. From these observations, the agent maintain a state, updated recurrently after each action and new observation, that we call the agent state. This is the state accessible to the policy. In the asymmetric learning paradigm, we assume that in addition to the agent state, the agent is provided with the environment state *at training time only*. **We propose to improve the background to better explain and illustrate with examples what could be typical observations, environment states, agent states, update functions, and what would be aliasing in this context.** We could notably use the example discussed in our response to Reviewer UL7j.\n\n**Update function and policy.** In a sense, the update function simply implements the processing of the history that is done before passing the (stochastic) feature $z$ of the history $h$ to the policy $\\pi$. Together, the update function $U$ and the policy $\\pi$ thus implement the history-dependent function that controls the POMDP. Only the policy $\\pi$ is considered learnable, and common examples for the update function $U$ are a window of past observations, the belief/Kalman filter (if the latter is known), etc. **We propose to clarify this distinction and to give some examples to help readers outside of the field to better understand this.** Please note that we also discuss in the conclusion the fact that the proof straightforwardly adapts to an agent state process $U$ that is learned through RL.\n\n**Finite states.** All state spaces ($\\mathcal{S}$, $\\mathcal{A}$, $\\mathcal{O}$ and $\\mathcal{Z}$) are considered finite in this analysis. **It is indicated in Subsection 2.1, but if you feel that we do not insist enough on that in the introduction or anywhere else in the main text, please let us know and we would be happy to address this.**\n\n**Initial sampling distribution.** Concerning the temporal difference learning algorithm (Algorithm~1) and the finite-time bound for the critics (Theorem 3 and Theorem 4), any initial distribution $p(s,z,a)$ could have been chosen, and the bound would have been obtained with norm $\\lVert\\cdot\\rVert_p$ instead of $\\lVert\\cdot\\rVert_d$. However, since we need to take samples from the discounted visitation measure $d = d^\\pi \\otimes \\pi$ for the policy-gradient (as is standard for on-policy policy-gradient), the performance bound is expressed in terms of expectation under that distribution. As a consequence, we thus need to know a bound on the critic error under that norm $\\lVert\\cdot\\rVert_d$, which explains why the temporal difference algorithm was studied under that sampling distribution. **We propose to add a note in our paper to clearly state that the analysis of Theorem 3 and Theorem 4 can be straightforwardly adapted to any sampling distribution $p(s,z,a)$.**\n\n**Sampling algorithm.** The algorithm implicitly assumes that we have an oracle allowing to sample from this distribution $d = d^\\pi \\otimes \\pi$, as is standard in prior works. **We will clarify this in the algorithm.** In any case, there exists a tractable algorithm for sampling from this distribution. This algorithm samples an initial timestep $t_0 \\sim \\text{Geom}(1-\\gamma)$ from a geometric distribution with success rate $1 - \\gamma$, and then the current policy would be used to take $t_0 - 1$ actions in the environments, and would then sample a last action. The environment state $s_{t_0}$, agent state $z_{t_0}$ and action $a_{t_0}$ constitute a sample from this distribution $d$.\n\nWe hope that you will find these adaptations pertinent to improve the overall accessibility of the document, and please do not hesitate if you need us to clarify something further.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "Yes", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths: \nThe paper presents a finite sample analysis for neural actor-critic methods, comparing both asymmetric and symmetric critics. The convergence rate achieved, $O(1/\\sqrt{T} + 1/\\sqrt{N} + 1/\\sqrt{K})$, aligns well with state-of-the-art analyses in the field. The authors demonstrate that the actor-critic method using a symmetric critic may introduce aliasing errors, which does not arise with asymmetric critics.\n\nWeakness:\nPlease refer to Question section.", "other_comments_or_suggestions": "Please refer to Question section.", "questions_for_authors": "1. As I am not an expert in reinforcement learning within the POMDP setting, I found the background section somewhat confusing. Specifically, I would like clarification on the state space and agent state space: which one represents the state space accessible to the agent, and which one corresponds to the underlying true state space? Additionally, what is the distinction between $U$ and the policy $\\pi$? Clearer definitions would greatly aid readers who may not have extensive knowledge of POMDPs.\n\n2. In the definition of POMDPs, do both $|S|$ and $|A|$ need to be finite? I believe both are assumed to be finite in [1].\n\n3. In Algorithms 1 and 2, the initial state-action pairs are required to be sampled from a discounted visitation distribution. Why can’t the starting point be chosen arbitrarily from the state-action space? Additionally, how is the starting point sampled from the discounted visitation distribution?\n\nReference:\n\n[1] Cayci, Semih, Niao He, and R. Srikant. \"Finite-time analysis of natural actor-critic for pomdps.\" SIAM Journal on Mathematics of Data Science 6.4 (2024): 869-896.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides a theoretical analysis of asymmetric actor-critic in POMDPs, where the critic, Q-function, uses the state information during learning. The key result is that, based on the analysis in [1], this asymmetric critic can remove one "aliasing" error term due to the use of agent state in the finite-time error bound, compared to the symmetric case. The problem being considered is important and of practical relevance, the insight regarding this aliasing term is new, and the manuscript is generally well written. However, there were some concerns regarding the assumptions being made: e.g., the use of i.i.d. sampling oracles, and boundedness of the concentrability coefficient, the proper use of the terminology "aliasing", etc. 

During the discussion phase, some concern has come to my attention (based on the authors' responses), regarding whether $\epsilon_{grad}^{asym}$ would dominate $\epsilon_{grad}^{sym}$, especially in the tabular case, where the compatible error for the symmetric case could be made zero under tabular softmax parameterization, while the compatible error for the asymmetric one could not. This weakens the claims of "provable benefits" of asymmetric critic learning. One could argue, though, that when (linear) function approximation is used, these two terms might not be directly comparable. But again, this may weaken the overall claim of the provable benefit of asymmetric learning, by only looking at the removal of the “aliasing terms” (i.e., other error terms, since they are different, may matter as well). I suggest that the authors add these important remarks in the camera-ready version.

Also, during the discussion phase, one important related work [2] was brought to our attention, which was published in NeurIPS 2024 and appeared on OpenReview in Sept., 2024 (more than 4-months before ICML submission deadline), and also studied the provable benefit of asymmetric actor-critic with privileged state information, but was not mentioned in the submission. [2] addressed the more challenging setting with online exploration (and thus without the assumption on the boundedness of the concentrability coefficient, nor i.i.d. sampling), with finite-sample and computational complexity results, with benefits compared to the setting without privileged information. Some claims in the submission thus may need to be properly changed, e.g., those regarding the "lack of theoretical justification" on the "potential benefit of asymmetric learning". 

That said, the focused settings and the types of results in these two works are different -- the submission focused on the in-expectation, finite-time-error bound, with linear function approximation, as in [1], and thus the analysis techniques are fundamentally different from [2] as well. 

Overall, the submission still has some merit as a contribution to ICML, with new perspectives that may further our understanding of asymmetric actor-critic, especially through the explicit comparison with the symmetric counterpart. I suggest the authors incorporate the feedback from the reviews and discussions in preparing their camera-ready version.


[1] Cayci, S., He, N., and Srikant, R. Finite-Time Analysis of Natural Actor-Critic for POMDPs. SIAM Journal on Mathematics of Data Science, 2024.

[2] Cai, Y., Liu, X., Oikonomou, A., and Zhang, K. Provable partially observable reinforcement learning with privileged information. NeurIPS, 2024.
Decision: Accept (poster)