Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization
Authors: Chenbei Lu
Laixi Shi
Zaiwei Chen
Chenye Wu
Adam Wierman
Venue: ICML 2025 poster (2025)
Keywords: reinforcement learning
sample complexity
q-learning
approximate factorization
Primary area: theory->reinforcement_learning_and_planning
TL;DR: Improve factored MDPs in terms of 1) factorizibility, 2) applicability to model-free algorithms, and 3) sample complexity guarantees

Abstract: Factored Markov Decision Processes (FMDPs) offer a promising framework for overcoming the curse of dimensionality in reinforcement learning (RL) by decomposing high-dimensional MDPs into smaller and independently evolving components. Despite their potential, existing studies on FMDPs face three key limitations: reliance on perfectly factorizable models, suboptimal sample complexity guarantees for model-based algorithms, and the absence of model-free algorithms. To address these challenges, we introduce approximate factorization, which extends FMDPs to handle imperfectly factored models. Moreover, we develop a model-based algorithm and a model-free algorithm (in the form of variance-reduced Q-learning), both achieving the first near-minimax sample complexity guarantees for FMDPs. A key novelty in the design of these two algorithms is the development of a graph-coloring-based optimal synchronous sampling strategy. Numerical simulations based on the wind farm storage control problem corroborate our theoretical findings.

Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization
Chenbei Lu
Laixi Shi
Zaiwei Chen
Chenye Wu Adam Wierman
Abstract
Specifically, the size of the state and action spaces grows exponentially with the dimension of the RL problem, mak- ing it difficult-if not impossible-to efficiently represent, learn, and optimize policies in high- high-dimensional settings.
Factored Markov Decision Processes (FMDPs) offer promising framework for overcoming the curse of dimensionality in reinforcement learning (RL) by decomposing high-dimensional MDPs into smaller and independently evolving compo- nents. Despite their potential, existing studies on FMDPs face three key limitations: reliance on perfectly factorizable models, suboptimal sam- ple complexity guarantees for model-based algo- rithms, and the absence of model-free algorithms. To address these challenges, we introduce approx- imate factorization, which extends FMDPs to han- dle imperfectly factored models. Moreover, we develop a model-based algorithm and a model- free algorithm (in the form of variance-reduced Q-learning). both achieving the first near-minimax sample complexity guarantees for FMDPs. A key novelty in the design of these two algorithms is the development of graph-coloring-bain bbaso opti- mal synchronous sampling strategy. Numerical simulations based on the wind farm storage con- trol problem corroborate our theoretical findings.
To mitigate the curse of dimensionality, a common practical approach is to employ function approximation to approxi- mate the solution of an RL problem within a prespecified function class, such neural networks. While effective in certain applications, these methods often lack strong the- oretical guarantees, with most existing work focusing on linear function approximation (Tsitsiklis & Van Roy, 1996; Bhandari et al., 2018; Srikant Ying, 2019; Chen et al., 2023) and some extensions nonlinear methods, which typically rely on strong assumptions (Fan et al., 2020; Xu & Gu, 2020). Consequently, achieving provable sample effi- ciency for large-scale sequential decision-making remains a significant challenge in RL.
Fortunately, many real-world applications, when modeled as Markov Decision Processes (MDPs), exhibit structured transition probabilities and reward functions that can be leveraged to design algorithms with improved sample com- plexity. For instance, in robotic control, high-dimensional state spaces often consist of substates that evolve indepen- dently or depend on a low-dimensional subset of the previ- ous state. Specifically, consider a warehouse with multiple mobile robots transporting goods, each robot typically plans and moves based on its own position and objective, largely independent of the internal states of other robots unless they are highly close. These problems can be modeled using the factored MDP (FMDP) framework (Osband & Van Roy, 2014), which decomposes the original MDP into smaller and independently evolving MDPs. In this framework, the sam- ple complexity scales with the sum, rather than the product, of the individual state- acteon space sizes, thereby offering a potential solution the curse of dimensionality.
1. Introduction
Reinforcement learning (RL) (Sutton & Barto, 2018) has become an increasingly popular framework for solving se- quential decision-making problems in recent years (Kober et al., 2013; Haydari & Yılmaz, 2020; Chen et al., 2022: Charpentier et al., 2021). However, despite its promising potential, RL still faces significant challenges, in partic- ular the curse of dimensionality (Sutton & Barto, 2018).
'Institute for Interdisciplinary Information Sciences, Tsinghua University 'Department of Electrical and Computer Engincering, Johns Hopkins University 'Edwardson School of Industrial Engi- neering, Purdue University "School of Science and Engineering, The Chinese University of Hong Kong. Shenzhen CComputing & Mathematical Sciences Department, Caltech. Correspondence to: Chenye Wu <wuchenye cuhk.cdu.cn?.
While promising, the FMDP framework has several major limitations: (1) it assumes that the original MDP can be perfectly decomposed into smaller MDPs; (2) for model- based algorithms, a significant gap remains between the best-known sample complexity and the theoretical lower bound (Chen et al., 2020; Xu & Tewari, 2020); and (3) no provable model-free free algorithms currently exist for FMDPs.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Addressing these challenges is essential for improving RL efficiency in large-scale problems.
finite action space, P the unknown transition kernel, with P(s' 8, denoting the transition probability from state to s' given action a, r S x A + [0, 1] is the unknown reward function, and E (0, 1) is the discount factor. Given a policy π : S - (AA) (where A (AA) denotes the set of probability distributions supported on A), its Q-function
1.1. Contributions
The main contributions of our work are threefold.
Q" E R (llA) is defined as
Approximate Factorization of MDP and Efficient Sam- pling. We propose an approximate factorization scheme that flexibly decomposes any MDP into low-dimensional components, while allowing for imperfect factorization. To facilitate algorithm design, we introduce a multi-component factorized synchronous sampling approach, formulated as cost-optimal graph coloring problem. Unlike previous FMDP methods, which estimate transitions for single component per sample, our approach enables simultane- ous sampling of multiple components from single sam- ple, significantly reducing the sample complexity for both model-based and model-free algorithms.
(" = EE,
Σn'r(se oz) s, 0,
for all (s, a). where Px, denotes the expectation over trajectories generated by the transition kernel P and the policy π. With the Q-function defined above, the agent's goal is find an optimal policy x² such that its associated Q-function is uniformly maximized over all state-action pairs. It has been shown that such an optimal policy always exists (Puterman, 2014).
At the heart of solving an MDP is the Bellman equation, which states that the optimal Q-function, denoted by Q", is the unique solution to the fixed-point equation
Model-Based Algorithm. We propose a novel model-based RL algorithm that uses synchronous sampling exploit low-dimensional structures from approximate factorization. The algorithm achieves provable problem-dependeni sam- ple complexity (cf. Theorem 5.1). outperforming existing minimax-optimal bounds for standard MDPs (Azar et al., 2012). For the special case of FMDPs, improves the best- known sample complexity (Chen et al., 2020) by up to a factor equal to the number of components and matches the instance- lower bound (Xu & Tewari, 2020).
Q H(Q),
where H RISIIA - RRSS|-A|| is the Bellman optimality operator defined as
[H(Q))(s,, = (E + + max Q(s aa)]
d'EA
for all (s, Once Q" is obtained, an optimal policy can be computed by choosing actions greedily based on Q"
Model-Free Algorithm. We introduce model-free al- gorithm, Variance-Reducee Q-Learning with Approximate Factorization (VRQL-AF)) which also builds on the syn- chronous sampling method. VRQL-AF achieves the same problem-dependen sample complexity guarantees (cf. The- orem 6.1) as our model-based algorithm, up to logarithmic factors, and outperforms existing minimax-optime algo- rithms for standard MDPs (Wainwright, 2019b). In the special case of FMDPs, VRQL-AF is, to the best of our knowledge, the first provable model-free algorithm with near-optimal sample complexity guarantees. This improve- ment enabled by tailored factored empirical Bellman op- erator induced by synchronous sampling, combined with variance-reduction technique that minimizes variance across factored components.
Suppose that the model parameters of the MDP are known. Then, we can efficiently compute Q' through the value it- eration method: Qk+1 H(Qu). Since the operator H(-) is contraction mapping (Sutton & Barto, 2018), the value iteration method converges geometrically to Q' (Banach, 1922). However, in RL, the agent does not know the model parameters of the underlying MDP, making direct value it- eration infeasible. A common solution is the model-based approach, which estimates the model parameters through empirical sampling and then applies value iteration to the estimated model. Alternatively, model-free methods, such as Q-learning (Watkins & Dayan, 1992), bypass model es- timation by directly solving the Bellman equation using stochastic approximation (Robbins & Monro, 1951).
Throughout this paper, we work under a widely used sam- pling mechanism setting - the generative model (Kearns et al., 2002; Kakade, 2003). This model allows us to query any state-action pair (s, a) to obtain random sample of the next state s' and the immediate reward r(s. a) accord- ing to the underlying transition kernel and reward function. While not explored in this work, extending our results to the Markov sampling setting- provided setting-provided the behavior policy induces a uniformly ergodic Markov chain- -is a promising direction for future research.
To support the above contributions, we include a detailed literature review in Appendix A and comprehensive experi- ments in Appendix H, covering both synthetic FMDPs and a real-world wind farm storage control application.
2. Model and Background
We consider an infinite-horizon discounted MDP M =
(S, A, P, P,r,7) where S is the finite state space, A is the
2

---

An approximate factorization is characterized by tuple w = (w" ,)"), which specifies how both the transition ker- nel and the reward function are factorized. In the following, Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
3. Approximate Factorization of MDPs
our approximate factorization scheme, we first consider the special case where the transition kernel P is perfectly factor- izable with respect to wf' That is, for all = (5,a) E X,
In this section, we introduce the concept of approximate factorization. Assume without loss of generality that each state s can be represented as an n-dimensional vector. Ac- cordingly, the overall state space S can be written as S = [l= S, where S; C IR for all i E [n] := (1, .... Similarly, assume without loss of generality that each ac- tion is an m-dimennsooal vector and A = = I As. where A, S R for all; j E [m]] Throughout this paper, each com- ponent 8(1] E S; of state & E IR" is called a substate. A subaction is defined analogously. The following definitions of scope, scope set and scope variable, will be useful for introducing approximate factorization.
s' E S, and k E [Ka], we have
P(s' 1x) II Pa x| D.
(1)
where Po | xz(2')) is valid probability distribution for all x x|2[1 E x[2z]. Eq. (1) implies that the transitions of s' [Zg]] for different & are conditionally independent and each depends only on the corresponding substate-subaction pair in x[zz)) An MDP that admits both perfect transition and reward decompositions (cf. Section 3.2) is called an FMDP (Oshand & Van Roy, 2014). In this case, one only needs to solve K smaller MDPs rather than the original high- -igh-niimnsional one, thereby significantly reducing the complexity of finding an optimal policy.
Definition 3.1. Consider a factored d-dimensional set X = I Xr where X₂ S R for all i E [d]. For any Z C [d] (which we call a scope), the corresponding scope set x is defined as x[Z] = Ilezz X;. Any element x [2] E X|z] (which is a |/l-dimensional vector) is called a scope variable. When Z contains only one element, i.e., Z - { for some i E [d]. we denote z[1] x [[]]]]
As discussed in Section 1, while the FMDP framework of- fers a promising way to address the curse of dimensionality, the assumption of perfect factorization is relatively restric- tive. To overcome this, we propose more general scheme of approximate factorization, which allows deviations from the exact structure in Eq. (I). Specifically, to develop an approximate factorization scheme (i.e., to get an estimate of the "marginal" transition probabilities P(s P(s|[z]] | |x =[Z[()
we elaborate on the definitions of wP and R in detail.
in Eq. (1)), we define the set of feasible marginal transition probabilities in the following. For any [Kw]. let
3.1. Approximate Factorization of the Transition Kernel
A factorization scheme w of the transition kernel is char- acterized by a tuple
Pk- PR (RERINZE))
BEED XI
Va 128
= (Kw, 12 S [m] k E [Kw],,
x <>6l
E x(
s.t. (A
x x<(2]))
[2 C [n+ + ml k E [Kw])),
Σ dx'l- P(s [ x1-2f11
1 1, 2
x
where
where we use Ed to denote the d-dimensional probability simplex. Then, we choose P& E Pa arbitrarily for all e [. As we will see in later sections, the development of our theoretical results does not rely on the specific choice of Pk Pa. To understand the definition of Pk. again consider the perfectly factorizable setting, in which case P(s) 2 x||z|| 1 z'(- = [[,) x|Z]") = for any r'1- "f""""""-"2"" E x z because the transition of s' s'[2,] does not depend on the substate-subaction pairs in x1 As result, Ps a singleton set for all k, which is consistent with Eq. (I). Coming back to the case where the underlying MDP is not perfectly factorizable, choosing Ps from Pa can be viewed as a way of approximating the "marginal" transition probabilitics.
Ku E [n] denotes the number of components into which we partition the transition kernel;
{ | k E [K,]] is a collection of scopes over the n- dimensional state space S. This collection forms a parti- tion of [m]. i.e.. U - = [m| and 25, n 2 for any bı * kg. For each scope _ C [n]. the associated subspace is denoted by Si
( | k E [K,]} is a collection of scopes over the joint state-action space X := A. For example, in an MDP with a 3-dimensional state space and 2-dimensional action space, if zí {1, 2, 4), then the associated scope
set is x S x S₂ x Ai.
Given an approximation scheme wP, we define the approxi- mation error with respect to the transition kernel as
For simplicity of notation, we use - -= : [n] 2 to denote the complement of z with respect to [n]. The fac- torization scheme w characterizes the component-wis wise de- pendency structure within the transition kernel. To motivate
A P
sup PIEP PK. ERR S'ES,rE
max
P(s
| ())
3

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
II K.
- [
(2)
sum of their reward functions is equal the original reward function, we have A 0.
To understand Ah see that for any s' E S and x E X, we have the following:
For further illustration of our approximate factorization scheme, see Appendix B for an example.
K= II 1=
4. Factorized Multi-Component Synchronous Sampling
P(s' 2)
Pu(
| = A1 + +
where
To introduce our model- basee and model-free algorithms, we first present an efficient sampling algorithm that exploits the factorization structure. Consider classical model-based RL, which typically involves two steps: (1) estimating the transition kernel and reward function through empirical sam- pling, and (2) applying value iteration or policy iteration to the estimated model. The curse of dimensionality arises primarily in the first step, where each state-action pair must be sampled multiple times, resulting in sample complexity proportional to [S|[Is By leveraging approximate factor- ization, we significantly reduce this burden. For clarity, we focus here on estimating the transition kernel; the same approach applies to the reward function.
K= II (x( Ix)
A P(8 (z)
1=1
K II Pa
K= II Pa
22
2)
x z1Z,1).
The first term A₁ represents the error due to ignoring the correlation between the transitions of s' | for different k. and vanishes if the transitions of substates from different scope sets are independent. The second term A₂ arises due to ignoring the dependence of the transitions of s' s'[zğ] from a zF). Note that when the MDP is perfectly factorizable, we have A 0 (ef. Eq. (I)).
The goal is to construct an approximation P of the original transition kernel P. We do this by estimating a collection of low-dimensional transition kernels (Px l E [Kw] computing P according to
and
3.2. Approximate Factorization of the Reward Function
For the reward function, the factorization is characterized by the tuple
((511z)= = II K= PA
x x|
(4)
w (ew, (Z E [n + m] Lie [(.)),,
for all s' E S and x E S A. Instead of sampling ex- haustively from the global state-action space, we sample full transitions and extract the relevant substate-subaction dimensions, as is standard in factored MDPs (Osband & Van Roy, 2014).
where
tu is a positive integer representing the number of com- ponents into which we decompose the reward function;
To estimate Pa( x x((fl) for any h E [Ka], we define the restricted sampling set X as:
{ | E [w]] a set of scopes with respect to the joint state-action space X.
X (x x x1 1
default | 2 2f,13
(5)
Under this factorization scheme, the global reward function r(x) is approximated by the sum of "local" reward functions from (r. : x|zz, [0, 1]) where each r; depends only on the scope variable x x[ Similarly, given an ap- proximation scheme R. for the reward function, we define its approximation error as
where x default E X' is an arbitrary but fixed reference point. Sampling from X!" allows us to estimate the k-th factorized component without needing to cover the full state-action space. For each x E X we sample the next state N times, obtaining samples { The empirical transition kernel Ps is then computed as
R max ((x) - E 11() ZER
1 1
N 1=1
11s [ = s'(z,1) (6)
which is a measurement of the deviation from our approx- imation to the true reward function. The approximation error A arises due to the fact that the reward function r(z) may depend on cubstate-subaction pairs outside the scope set ] In the special case where the underlying MDP can be perfectly factorized into several small MDPs and the
for all s' s' E S and x E Xf. The overall estimate P is then obtained via Eq, (4).
Using this approach, the total number of required samples is K | Since the total substate-subaction space
4

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
size, Σk= [[ is typically much smaller, often ex- ponentially smaller, than the size of the full state-action space |||||] [A], the overall sample complexity is significantly reduced compared to classical model- RL.
where D = ( [x(z]])), and [2, de- notes the i-th element in a fixed ordering of x The modulo operation ensures that we eycle through all possible values of each component's 'ss state-action space. By sam- pling from each x E X N times, we obtain samples (s2, (5,,))= which are used to estimate the transition probabil- ities for both components according to Eq. (6). Appendix provides an example of synchronous sampling with disjoint scopes. This strategy improves sample efficiency by redue- ing the total number of samples compared to sampling each component independently.
This also explains why the best-known sample complexity depends on Σ [x[z)""| (Chen et al., 2020). To improve this to the lower bound of max; |x we show that the key is leverage structural properties of factored MDPs and to design synchronous sampling strategies that allow multiple factors to be sampled simultaneously.
4.1. Structure-Aware Sample Reuse Strategies
4.2. Cost-Optimal Synchronous Sampling Strategy
The sampling method described above can be further op- timized by exploiting the structure of the factorization scheme to improve sample efficiency. Previously, the sam- ples (s Ne(N) were used solely to estimate [x
Building on the aforementioned two key strategies, we next present our sampling approach. Recall that we have Kw components associated with scope sets ZP: .z...... ZR_.. For each & E [Km]] we define its corresponding sampling cost as the size of the scope set X[Zz]) Using the inclusive scope property, we first eliminate components whose scope sets are subsets of others. Let denote the set of remaining components defined as
a ( for component k. However, these samples may also be reused to estimate other low-dimensional transition ker- nels, depending on the relationships among their associated scopes. To formalize this idea, we introduce two key strate- gies that leverage the structural relationships between the scope sets of different components.
K {kk E [Ku] Aky # l such that z & Z }-
Synchronous Sampling with Inclusive Scopes. For any k1, K2 E [Ku] such that zr, S Zkg- the samples used to estimate the transition kernel of component k2 can be reused to estimate that of component k,. Specifically, consider the sampling set
Next, to use the exclusive scope property, divide K into subsets (Gihsss (where Kp denotes the total number of subsets) such that within each subset Gt, the components have disjoint scopes, i.e., zF, n 2 = 0 for all k k2 E Gi. This enables us to apply the strategy of synchronous sam- pling with exclusive scopes within each subset. Specifically, for each subset Ga of K we construct the joint sampling sets as
x = fx x|- ZPI x defooult 1 -ZP.)
for component k22 where ( [2,]]] is fixed, arbitrary element from
By sampling from each æ E Xx- we obtain samples of the next state (s"))ee))) Since Zł, C ZR,, these samples inherently contain information about the transitions of component kj. Therefore, we can estimate the transition probabilities for component kn ac- cording to Eq. (6) with = k1 using the same samples, where the sampling set XE, is defined based on XP as
X-. = [[x|Zz]) Ih mod 1x127114D))Ess
gdeeluul (- (Ujes, (u')l i [Dmaxxk]]
where Diaax = maxjes, [x12|1 ensures that all scope sets associated with this subset are sampled. Therefore, the cost of sampling a joint sampling set is determined by the largest scope sets in the group
X = (+ E XL a
default 2 Z
Ck (Gx) = D Dmax, max |X|2
This reuse of samples improves overall sample efficiency by avoiding redundant sampling for component k1.
jESt
Synchronous Sampling with Exclusive Scopes. For any ki,k2 E [K,) such that their associated scopes are dis- joint, i.c., 2 nz = 0. we can estimate the transitions for both components simultaneously using shared samples. Specifically, define the joint sampling set Xf, x2 as
Our objective is to minimize the total sampling cost across all groups defined as
Σ K=z Ca (9t))
min Gi....
min
XP - {(x| [(imod 1x[22,11 1112, [/ (imo [1/2,112,,)+
This problem is closely related to the Graph Coloring Prob-
lem (GCP) (Jensen & Toft, 2011; Karp, 2010). In Appendix G, we detailedly elaborate on the connection between our
defoult ((tp, U (zb))) ))) 1 E [Dmaa)]
5

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
cost-optimal sampling problem and the GCP. The solution yields the optimal number of groups Kip [Kw] and the division scheme (eeg)l Notably, Kip corresponds to the chromatic number (Erdös & Hajnal, 1966) (the minimal number of colors required) in GCP, which is often much smaller than the number of nodes in the graph (Khot, 2001; Sopena, 1997; Goddard & Xu, 2012). This result translates to Kp < K. in our context, leading to substantial sampling cost reductions. The detailed discussion on Kip can refer to Section 5.2.
performing Q-value iteration on the estimated model.
Algorithm 2 ModellBased Q-Value Iteration with Approxi-
mate Factorization
Input: Positive integer T and initialization Qo(s,a) 0 for all (s, a) S A.
Compute empirical transition kernel P and the reward function F through synchronous sampling Algorithm I
and Eqs. (7) and (8). do do
3: for 1. = 1,2,
4: Qs(s,a)
E Bx-P(r)aa ((s,
+
4.3. MDP Model Estimation
? maxx Qr-1(s',a)) a')) for all a).
Given (E(x)) and the joint sampling sets {XE, keln,) we are ready to sample and estimate the transition kernel. Specifically, for each state r E X we perform N sam- pling trials to obtain next-state samples based on the genera- tive model. Specifically, we generate N samples { by sampling from P(- x) as detailed in Algorithm For each component j E Ga and s' s'[zø] E S(zØ",, we compute the empirical transition kernel according to
5: end for
6: Output: Estimated Q-value function 2% = Qr-
The first step involves estimating the transition kernel and the reward function (see Algorithm 2, Line 2). Specifically, in Section 4, we explained how to estimate the transition probabilities Ps for each component E [Kw]. For any s' E S and I E X. the overall transition probability P(s') | x) is computed by combining the individual component estimates as follows:
IN
x | = N E EMEI 125) = s'izii).
P (a) II Pe(''1z]1 | ((
(7)
Algorithm Cost-Optimal Factorized Synchronous Sam- pling Algorithm
Similarly, for the reward function, we aggregate the esti- mated rewards i; for each component E [ to obtain the overall reward function
Input:
Approximate factorization w = (w ".
2: Solve the optimal division scheme represented by
{Kpp {Gx {G*)*el<,)) )=
E Fw 1=1 F((1121))
3: Construct the sampling sets (XG))kEin)))
F(x)
(8)
4: for k ===1. 1, Kpp do
5: Sample from each state-action pair E XL for N
The second step is to apply the value iteration method using these estimated model parameters (see Algorithm 2, Lines 3-5). In particular, Line 4 of Algorithm 2 represents the empirical version of the Bellman iteration. Through value iteration, we can compute the desired optimal-Q-vatue func- tion and derive the corresponding greedy policy as the final solution to the RL problem.
times to obtain (st,llexgg..eeM
6: end for
7: Output: Samples {s beinlleeee ME())
To estimate the reward function components, we employ similar inclusive and exclusive scope strategies. By con- structing sampling set tailored to these strategies, we can then proceed with learning the reward function.
5.2. Sample Complexity Guarantees
We now present the sample complexity guarantees of Algo- rithm 2: the proof can be found in Appendix D. Before proceeding, without loss of generality, we assume that | |x[z]]]
5. Model-Based RL with Approximate Factorization
2 |x[ZR_]1 and |2[z1|| 2 [ 2 ... ....2 |x[ i.e., the component scope sets are ordered descending order based on their cardinality.
In this section, we focus on model-based RL and propose the model-based Q-value iteration with approximate factor- ization algorithm, which offers improved sample complexity guarantees.
Theorem 5.1. Given any approximate factorization scheme w. let Ewg (117))>>A? + (1-7)-1 - For any confi- dence level 8 > 0 and the desired accuracy level E (0, 1), with probability at least 6, the output Q-function Qz from Algorithm 2 after T T2 log(c- --)-- -1) itera- tions satisfies 11Ộ- - 10 S c En provided that the
5.1. Algorithm Design
The algorithm is summarized in Algorithm 2, which con- sists of two steps: estimating the model parameters and
6

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
total number of samples, denoted by Dun satisfies
E [x(z,(]) for FMDPs from (Chen al., 2020) 1 our result O
|x(2,11) of- fers strictly better sample complexity, where Kip E [K_] and Kr E [[w] are instance-dependent parameters. Indeed, Kip reflects the sparsity of the dependence structure in the MDP. In many real- weal-world applications such as UAV swarm control (Campion et al., 2018) and power system economic dispatch (Chen et al., 2022; Lu et al., 2023), the dynamics of different UAVs or different power generators are highly independent, then Kip < Kw and can he small constant if the dependence structure is sparse. Also, by connecting it to the Graph Coloring Problem, Kip < K_ is provable under mild condi- tions (can refer to the discussion in Section 4.2). As a result, it indicates our sample complexity can improve the prior arts in FMDPs by a factor of up to ((K)). Similarly, Kyr can be significantly smaller than E. if the reward function components have such sparse dependence.
Cu (EKE(pp) [x(2,11 log (cr ( (2,)
Dw 2-
<²(1 - 7)3
Eie(ro) |x[2,-11
where Ky E Kul and Kir E [0, Cwl are problem- dependent parameters, and Co. 21 22 are absolute constants.
Now we discuss further implications of our results.
Model Misspecification Bias. The parameter & is called the model misspecification bias, which consists of two terms: (1--))=AA- and (1-7)-1 A. both of which are linearly dependent on the approximation errors of the transition kernel and reward function, respectively. This bias arises from the inaccuracies introduced by the factorization of the transition kernel and reward function. If the factorization were accurate, these approximation errors would vanish, and e would reduce to zero, as in the FMDP case, which is discussed below.
The sample complexity lower bound for FMDPs is Ommxx [x ((11 - -3)-3 + max; [x( which is established in (Xu & Tewari, 2020; Chen al., 2020). It worth noting that, our algorithm is the first to match this lower bound in iestance-dependent manner when Ki, Kir (1)) demonstrating that we not only improve upon existing upper bounds but also achieve the theoretical minimum sample complexity under certain conditions.
Sample Complexity Implications and Comparison to Prior Works. For a fair comparison, we consider our results using a factorization scheme w that is perfect with the bias En = 0. In this case, our sample complexity required to achieve an e-optimal policy is of the following order:
Trade-Off Between Sample Complexity and Model Mis- specification Bias. The approximate factorization scheme w can be viewed as a tunable hyperparameter. In general, when the number of components K., increases, we get finer decomposition of P and the size of each component decays exponentially with K.,, which significantly reduces the sample complexity Dw. However, the drawback of increasing K2 arbitrarily is that may result in a larger mis- specification bias E due to model mismatch. To illustrate this trade-off, consider the example depicted in Figure 1, where we decompose an MDP into three components by dis- regarding certain weak dependencies. If the induced error E. is smaller than the desired accuracy level e, this imper- fect factorization is sufficient to achieve the target solution. When we require higher accuracy (smaller e), a more care- ful factorization scheme with generally fewer components should be chosen. For instance, grouping W, and p. within single component will reduce the bias E.,, though at the cost of increased sample requirements. This trade-off will be revisited again in our numerical simulations in Section H. As a final note, when K., = 1. this theorem recovers the classical sample complexity result (without decomposition) established in (Azar et al., 2012).
Σ RE((p)
-1
+ vE[[,]]
1x12
Compared with the minimax-optimal sample complexity of (((S]AA|E=> (1--== -3)) (Azar et al., 2012) for solving stan- dard MDPs, we have identical dependence on ō, e, and the effective horizon 1 1/(1-)) The key improvement lies in the dependence on the size of the state-action space, where we improve the minimax (((S)IAA)) dependence (Azar et al., 2012) to [mpp] (x(2 S Ö(K,, max; [x[2["]). Notably, Ō(K,, max (x is a sample complexity - almost proportional to the sample complexity of solving the largest individual component among the factorized parts of the entire transition kernel, which is exponentially smaller than |S||. due to reduced dimensionality. For example, consider an approximate fac- torization scheme that decomposes an MDP into 10 disjoint components with identical cardinalities. The corresponding sample complexity becomes ([[5))-A1]))) achieving an exponential reduction in sample complexity relative to the number of factorized components.
We translate their results to our setting for easy understanding and clear comparison.
In addition, when the bias E,, = 0, the MDPs with ap- proximate factorization reduce to the well-known setting of FMDPs. Compared to the best-known sample com- plexity upper bound Km= |x[2[]|c-2( - 7) +
7

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
6. Model-Free RL with Approximate Factorization
Algorithm 4 Variance-Reduced Q-Learning with Approxi-
mate Factorization (VRQL-AF)
Input: Number of epochs T'; Epoch length M; Reference
In this section, we focus the model-free setting and intro- duce the Factorization (VRQL-AF) algorithm with sample complex- ity guarantees.
sample size N, (T I T); Learning rate πІ-
Q-Learning with Approximate
Output: e-accurate Q Function estimation 2M with 1 - 8
probability;
Initialize Qu a) = 0 for all s and a;
2: for epoch = 2.., do
6.1. Algorithm Design
3: Generate N, factored empirical Bellman operators
In classical Q-learning (Watkins & Dayan, 1992), the Q- function estimate Q₂ is updated using a -tell-stepsize vari- ant of the empirical Q-value iteration as follows:
[B:),=1,,....,,, though Algorithm 3; 4: Calculate the reference Bellman operator
(Q,-)) = N. EE (Q.-)):
1
Initialize Qo - Q--1i
Qu+1 = =Q + no mo (Q.) -Q().
6:
for iteration 0, .... M - do
7:
Generate factored empirical Bellman operator Hi:
where n7 E (0, 1) is the learning rate, (Q) is the empiri- cal Bellman operator satisfying [He(Q)] (s, a) = =r(s, a) + y max, (s) a), a') for all (s, a) and Q [|SIAA,, and ss( a) denotes the next state sampled from P(- a.)..
through Algorithm 3;
8:
Compute the variance-reduced update:
Q++1 Q + T/e (H)((Q)) - Hi,
+H-((---))QQ) (11)
Compared with classical Q-learning, our VRQL-AF algo- rithm consists of two key modifications: (1) factored em- pirical Bellman operator design and (2) variance-reduced Q-iteration. The factored Bellman operator is designed to replace the standard empirical Bellman operator in order to enhance sampling efficiency by leveraging the structure. Its construction is outlined in Algorithm 3. Specifically, in vanilla Q-learning, we need to sample all state-action pairs to generate single empirical Bellman operator, which requires | samples and is highly inefficient. Our ap- proach aims to reduce the number of required samples by exploiting the problem structure through a factorization scheme, thus enabling the repeated use of the same samples.
9: end for
10:
Q Q
11: end for
12: Output: Qr:
samples { [ee), Ae(x,)] These samples are sufficient
to construct the factored empirical Bellman operator (i) Specifically, for any == (s, a) E S A, the corresponding entry [H(Q))(ss, a) of P((() satisfies
[f.())(ss =7 max Q( (1 + +r(s,a),
K.
Algorithm 3 Empirical Factored Bellman Operator Genera-
(10)
tion
1:
Input: Factorization scheme w = (wP, R).
where for each j E [Kw], 8yy is the sample containing the correct transition of component j satisfying
2: Solve the optimal Synchronous sampling scheme repre- sented by {Kpp [9x
3: Construct the sampling sets (X hkE(N=);
S/5 ( 5 E X =[ = *|,
4: for k= 1, 1,2 2...,,...,, Kp do
5: Sample the transition from each state-action pair x E X8" once, and obtain the next state by {s [shlkl
This ensures that the samples from different components are used to compute the transitions for all dimensions of the Bellman operator. By using synchronous sampling, we cover the transitions for all components, allowing us to estimate the entire factored Bellman operator efficiently. Note that, Eq. (10) simply extracts the relevant dimensions from each sample to update the corresponding factors, which makes the implementation straightforward and efficient.
6: end for
7: Get empirical Bellman operator Fl (for any Q) follow-
ing Eq. (10);
8: Output: Empirical Bellman operator Hi
Specifically, we adopt the synchronous sampling scheme {Kpp {GA (G discussed in Section 4, and then obtain the corresponding Kp sampling sets {X E, k For each [kp]) we sample over each entry from the set XyF once, obtaining the next state S randomly generated based on transition and corresponding reward. This gives us the
The variance reduction technique aims to reduce the vari- ance in the update process, thereby accelerating the con- vergence (Sidford et al., 2018; 2023; Wainwright, 2019b). Armed with both schemes, our proposed VRQL-AF is sum- marized in Algorithm 4. Specifically, the algorithm employs
8

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
two-loop structure. In each outer epoch T, a new reference is constructed, followed by inner loop that iteratively updates the Q-value estimate using both the reference and real-time empirical Bellman operators.
which achieves the same order our model-based algo- rithm. This indicates that our proposed model-free VRQL- AF can also address the persistent curse of dimensionality in standard RL, as already discussed for our model-based algorithm. For more details, please refer to Section 5.2.
In particular, in each outer loop т, we first compute a ref- erence Bellman operator H(Q+-1), which is an average of N2 factored empirical Bellman operators B, generated through sampling process applied to the fixed Q-value function Q (obtained from previous steps). This refer- ence Bellman operator provides a low-variance estimate of the Q-value function.
Importantly, VRQL-AF is the first near-optimal model-free algorithm for our approximate factorization framework (in- cluding FMDPs), which breaks the curse of dimensionality by combining tailored factored empirical Bellman opera- tor, synchronous sampling scheme, and advanced variance reduction. The improved sample complexity is achieved by a refined dinsesiimensoona variance analysis on the conver- gence process with factored empirical Bellman operators.
Next, in each inner loop t, new factored empirical Bellman operator H4 is generated from fresh samples, and the Q- function is updated by combining a high-variance unbiased operator (Qt) with a reference- baaee variance-reduction term Hes (Q.-1) IQ.
Note that for the factored MDP setting (Osband & Van Roy, 2014) with perfect factorization, our result can potentially be extended to the Markov- behavior policy л, provided that induces, on each factor with a sampling set, a uniformly ergodic Markov chain. The analysis can following techniques like (Li et al., 2020b). A fully rigorous treatment of this extension is left to future work.
regime under fixed
6.2. Sample Complexity Guarantees
We now provide bound on the sample complexity of Algo- rithm 4; the proof is provided in Appendix E:
Theorem 6.1. Given any approximate factoriza- tion scheme w. a confidence level 8 > O, and the E (0.1). Let the bias - + (1-7) 7) "B, the number the epoch length
7. Conclusion
desired accuracy level
Ew = 7(1 - 7)= P
Our work introduces a framework for approximate factor- ization in MDPs to address the curse of dimensionality in large-scale RL problems. By decomposing MDPs into smaller factorized components, we propose a synchronous sampling method optimize component sampling and model-based RI. algorithm that leverages the factoriza- tion structure. Additionally, we design variance-reduced Q-learning algorithms with factored empirical Bellman operator for efficient online learning. Our theoretical re- sults show significant improvements in sample complexity, outperforming existing bounds for both vanilla and FMDPs.
of epochs T = ei log ((1 - (1)-
k=1 1 -2)- 10)0))-)(1-))11 (1-7)8 M = =cylog (uT, Kn
the reference sample
size N=
co47log 6T 6TT 2 (1 - 7) and the learn- ing rate 1/: = (1+ (1 + 11 With probability at least 1 8, 8, the output Q-function Q from Algorithm VRQL-AF satisfies IIQ @w1 S < Ews. provided that the total number of samples, denoted by Dwn satisfies the following:
co CO(ENN)))) (x1211) log / 2 (1-770
log (1-
A Acknowledgements
Dw 2
(1 73
We sincerely thank the anonymous area chair and reviewers for their insightful feedback. We are grateful to Hongyu Yi for proofreading the paper and to Kishan Panaganti for helpful discussions.
Σ Eveln.) 11
where co, 02 0 are universal constants.
This work was supported in part by Tsinghua University during C. Lu's visit to the California Institute of Technology. L. Shi acknowledges support from the Resnick Institute and the Computing, Data, and Society Postdoctoral Fellowship at Caltech. C. Wu's work was supported in part by the National Natural Science Foundation of China under Grant 7227 1213, the Shenzhen Science and Technology Program A. Wierman's
In evaluating the performance of VRQL-AF, we note that the estimation bias& E, is the same as in our model-based algorithm in Theorem 5.1.
Therefore, we focus our discussion on the sample com- plexity, in the case of perfect factorization & 0 for fair comparisons. In this case, our sample complexity required to achieve an c-optimal policy is of the following order:
under Grant 1TTX202210080922220 work was supported in part by NSF grants CNS-214681 44, CPS-2136197, CNS-2106403, and NGSDI-2105648.
δ Eke(e,) |8(2,11
ExEn) km))
(212.91)
(12)
(1
9

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Impact Statement
Chen, X., Hu, J., Li, L.,, and Wang. L. Efficient reinforce- ment learning in factored MDPs with application to con- strained RL. In International Conference on Learning Representations, 2020.
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.
Chen, X., Qu, G., Tang, Y., Low, S., and Li, N. Reinforce- ment learning for selective key applications in power systems: Recent advances and future challenges. IEEE Transactions on Smart Grid, 13(4):2935-2 2958, 2022.
References
Agarwal, A., Jiang, N., Kakade, S. M., and Sun, W. Rein- forcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32, 2019.
Chen, Z., Clarke, J.-P., and Maguluri, S. T. Target network and truncation overcome the deadly triad in Q-learning. SIAM Journal on Mathematics of Data Science, 5(4): 1078-1101, 2023.
Agarwal, A., Kakade, S., and Yang, L. F. Model-based rein- forcement learning with a generative model minimax optimal. In Conference on Learning Theory, pp. 67-83. PMLR, 2020.
Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. A Lyapunov theory for finite-sample guarantees of Markovian stochastic approximation. Operations Re- search, 72(4):1352-136 2024a.
Azar, M. G., Munos, R., and Kappen, H. J. On the sample complexity of reinforcement learning with a generative model. In Proceedings of the 29th International Cofer- ence on International Conference on Machine Learning, pp. 1707-1714, 2012.
Chen, Z., Zhang, K., Mazumdar, E., Ozdaglar, A., and Wierman, A. Two-timescale Q-learning with function approximation in zero-sum stochastic games. The 25th ACM Conference on Economics and Computation, 2024b.
Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. International Con- ference on Machine Learning, pp. 263-272. PMLR, 2017.
Dai, B., Shaw, A., Li, L.,, Xiao, L., He, N., Liu, Z., Chen, J., and Song, L. Sbeed: Convergent reinforcement learn- ing with nonlinear function approximation. In Interna- tional Conference on Machine Learning, pp. 1125-1134. PMLR, 2018.
Banach, S. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fund. Math, 3(1):133-181, 1922.
Dokeroglu, T. and Sevinc, E. Memetic teaching- -eaching-learning- based optimization algorithms for large graph coloring problems. Engineering Applications of Artificial Intelli- gence, 102:104283 2021.
Bhandari, J., Russo, D., and Singal, R. A finite time anal- ysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, pp- 1691-1692. PMIRR, 2018.
Erdós, P. and Hajnal, A. On chromatic number of graphs and set-systems. Acta Math, Acad. Sci. Hungar, 17(61-99):,, 1966.
Boutilier, C., Dearden, R., Goldszmidt, M., et al. Exploiting structure in policy construction. In IJCAI, volume 14, pp- 1104-1113, 1995.
Even-Dar, Dar, E., Mansour, Y., and Bartlett, P. Learning rates for Q-learning. Journal of Machine Learning Research, 5(1), 2003.
Boutilier, C., Dean, T., and Hanks, S. Decision-theoretie planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:
Fan, J., Wang, Z., Xie, Y., and Yang, Z. A theoretical analysis of deep Q-learning. In Learning for Dynamics and Control, pp. 486-489, PMLR, 2020.
1-94, 1999.
California ISO. Electricity Price Data. https://wwwt energyonlire com/ com/Dataa / 2021. Online; ac- cessed on 20 December 2022.
Gary, M. R. and Johnson, D. S. Computers and intractability: A guide to the theory of np-completeness, 1979.
Gheshlaghi Azar, M., Munos, R., and Kappen, H. J. Mini- max PAC bounds on the sample complexity of reinforce- ment learning with a generative model. Machine Learn- ing, 91:325-349, 2013.
Campion, M., Ranganathan, P., and Faruque, S. Uav swarm communication and control architectures: a review. Jour- nal of Unmanned Vehicle Systems, 7(2):93-106, 2018
Charpentier, A., Elie, R., and Remlinger, C. Reinforce- ment learning in economics and finance. Computational Economics, pp. 1-38, 2021.
Goddard, W. and Xu, H. The s-packing chromatic number a graph. Discussiones Mathematicae Graph Theory, 32(():795 806, 2012.
10

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Guestrin, C., Koller, D., Parr, R., and Venkataraman, S. Efficient solution algorithms for factored MDPs. Journal of Artificial Intelligence Research, 19:399-468, 2003.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. Advances in Neural Information Processing Systems, 33:7031-7000 2020b.
Haydari, A. and Yilmaz, Y. Deep reinforcement learning for intelligent transportation systems: A survey. IEEE Transactions on Intelligent Transportation Systems, 23 (1):11-32, 2020.
Li, G., Shi, L., Chen, Y., and Chi, Y. Breaking the sample complexity barrier to regret-optimal model-free reinforce- ment learning. Information and Inference: A Journal of the IMA, 12(2)969-1043, 2023.
Jaakkola, T., Jordan, M.. and Singh, S. Convergence of stochastic iterative dynamie programming algorithms. Advances in Neural Information Processing Systems, 6, 1993.
Li, G., Cai, C., Chen, Y., Wei, Y., and Chi, Y. Is Q-learning minimax optimal? a tight sample complexity analysis. Operations Research, 72(1)222--236 2024a.
Jensen, T. R. and Toft, B. Graph Coloring Problems. John Wiley & Sons, 2011.
Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 52(1):233 2600 2024b.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. Provably efficient reinforcement learning with linear function ap- proximation. In Conference on Learning Theory, pp- 2137-2143. PMLR, 2020.
Lin, S. Computer solutions of the traveling salesman prob- lem. Bell System Technical Journal, 44(10)):245-2266) 1965.
Kakade, S. M. On the sample complexity of reinforcement learning. University of London, University College Lon- don (United Kingdom), 2003.
Lu, C., Gu, N., Jiang, W., and Wu, C. Sample-adaptive robust economic dispatch with statistically feasible guar- antees. IEEE Transactions on Power Systems, 39(1): 779-793, 2023.
Karp, R. M. Reducibility among Combinatorial Problems. Springer, 2010.
Lu, C., Yi, H., Zhang, J., and Wu, C. Self-improving online storage control for stable wind power commitment. IEEE Transactions on Smart Grid, 15(4):3666-366 -3800, 2024.
Kearns, M. and Singh, S. Finite-sample convergence rates for Q-learning and indirect algorithms. Advances in Neu- ral Information Processing Systems, 11, 1998.
Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidje- land, A. K., Ostrovski, G., et al. Human-level control through deep reinforcement learning. Nature, 518(7540): 529-533, 2015.
Kearns, M., Mansour, Y., and Ng, A. Y. A sparse sampling algorithm for near-optimal planning in large Markov de- cision processes. Machine Learning, 49:193-200 2083-208,0000 2002.
Kellerer, H., Pferschy. U., Pisinger, D., Kellerer, H., Pfer- schy, U., and Pisinger, D. Multidimensional Knapsack Problems. Springer, 2004.
Osband, I. and Van Roy, B. Near-optimal reinforcement learning in factored MDPs. Advances in Neural Informa- tion Processing Systems, 27, 2014.
Khot, S. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 600-609. IEEE, 2001.
Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
Kober, J., Bagnell, J. A., and Peters, J. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research,
Robbins, H. and Monro, S. A stochastic approximation method. The Annals of Mathematical Statistics, pp. 400- 407, 1951.
2013.
Langley, P. Crafting papers on machine learning. In Langley, P. (ed.), Proceedings of the 17th International Conference on Machine Learning 2000). pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Schaefer, J. The complexity of satisfiability problems. Proceedings of the tenth annual ACM symposium on Theory of Computing, pp. 216-226, 1978.
Shen, Y., Sun, Y., Li, X., Eberhard, A., and Ernst, A. En- hancing column generation by machine-learning leniine-larninn-bbseed -baed pricing heuristic for graph coloring. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 9926-9934. 2022.
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in Neural In- formation Processing Systems, 33:12861- 0e:12881-1277 2020a.

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Shi, L., Li, G., Wei, Y., Chen, Y., and Chi, Y. Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. In International Conference on Machine Learning, pp. 19967-20023 PMLR, 2022.
Wainwright, M. Variance-reduuced Q-learning minimax
optimal. Preprint 190. 040.00 2019b.
Wang. R., Salakhutdinov, R. R., and Yang. L. Reinforce- ment learning with general value function approxima- tion: Provably efficient approach via bounded Eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6133 2020.
Shi, L., Li, G., Wei, Y., Chen, Y., Geist, M., and Chi, Y. The curious price of distributional robustness in reinforcement learning with a generative model. Advances in Neural Information Processing Systems, 36, 2024.
Watkins, C. J. and Dayan, P. Q-learning. Machine Learning, 8:279-292, 1992.
Sidford, A.,
Wang, M., Wu, X., Yang. L.., and Ye, Y. Near- optimal time and sample complexities for solving Markov decision processes with a generative model. Advances in Neural Information Processing Systems, 31, 2018.
Woo, J., Shi, L., Joshi, G., and Chi, Y. Federated offline reinforcement learning: Collaborative pagle-policy cov- erage suffices. In International Conference on Muchine Learning, pp. 53165-53201. PMLR, 2024.
Sidford, A., Wang, M., Wu, X., and Ye, Y. Variance reduced value iteration and faster algorithms for solving Markov decision processes. Naval Research Logistics (NRL). 70 (5):423-444) 2023.
Xu, G., Shi, J., Wu, J., Lu, C., Wu, C., Wang, D., and Han, Z. An optimal solutions- gunndd deep reinforcement learn- ing approach for online energy storage control. Applied Energy, 361:122915, 2024.
Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, I.,, Lai, M., Bolton, A., et al. Mastering the game of go without human knowledge. Nature, 550(766))37777 359, 2017.
Xu, P. and Gu, Q. A finite-time analysis of Q-learning with neural network function approximation. In Inter- national Conference on Machine Learning, pp. 10555- 10565. PMLR, 2020.
Sopena, E. The chromatic number of oriented graphs. Jour- nal of Graph Theory, 25(3):191-205, 1997.
Xu, Z. and Tewari, A. Reinforcement learning in factored MDPs: Oracle-efficient algorithms and tighter regret bounds for the non-episodic setting. Advances Neural Information Processing Systems, 13:18226-18223 2020.
Srikant, R. and Ying. L. Finite-time error bounds for linear stochastic approximation and TD- TD-leamning In Conference on Learning Theory, pp. 2803-2830. PMLR, 2019.
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT press, 2018.
Szepesvári, C. The asymptotic convergence-rate Q- learning. Advances in Neural Information Processing Systems, 10, 1997.
Tian, Y., Qian, J., and Sra, S. Towards minimax optimal rein- forcement learning factored Markov decision processes. Advances in Neural Information Processing Systems, 33: 19896-19907, 2020.
Tsitsiklis, J. and Van Roy, B. Analysis of temporal- diffference learning with function approximation. Ad- vances in Neural Information Processing Systems, 9, 1996.
Tsitsiklis, N. Asynchronous stochastic approximation and Q-learning. Machine Learning, 16:185-202, 1994.
Vershynin, R. High-dimensional Probability: An Intro- duction with Applications in Data Science, volume 47. Cambridge university press. 2018.
Wainwright, M. J. Stochastic approximation with cone- contractive operators: Sharp l-infty bounds for Q- learning. arXiv preprint arXiv: 06265, 2019a.
12

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Appendices
A. Related Work
Our work contributes to a few key literatures within the RL community. We discuss each in turn below.
Finite-Sample Analysis for Model-Based Algorithms. Our proposed algorithm (ef. Algorithm 2) follows the model-based RL approach, where the learning process involves model estimation and planning. Model-based approaches have been extensively studied (Azar al., 2012; Agarwal al., 2020; Gheshlaghi Azar et al., 2013; Sidford et al., 2018; Azar et al., 2017; Jin al., 2020; Li et al., 2024b), achieving minimax-optimal sample complexity of ([ - - --)- in the generative model setting (Li et al., 2020a). This minimax-optimal bound is established by considering all possible MDPs in a worst-case manner, without leveraging any additional structure in the problem. In contrast. by leveraging the structure for algorithm design, we achieve sample complexity with exponentially reduced dependency on the size of the state and action space (cf. Theorem 5.1) when the MDP is perfectly factorizable.
Finite-Sample Analysis for Model-Free Algorithms. Our proposed algorithm also aligns with model-free RI., which does not estimate the model but directly optimize the policy (Sutton & Barto, 2018). A vast body of literature focuses on Q-learning (Tsitsiklis, 1994; Jaakkola et al., 1993; Szepesvári, 1997; Kearns & Singh, 1998; Even-Dar et al., 2003; Wainwright, 2019a; Chen et al., 2024a; Li et al., 2023; 2024a; Shi et al., 2022; Woo et al., 2024) with various sampling settings, demonstrating minimax sample complexity of ((())A - >))=). With further advancements like variance reduction, Q-learning has been shown to achieve minimax-optimat sample complexity of ((SS]|Ale (1->)-3) in the generative model setting (Wainwright, 2019b). In contrast, our work leverages the approximate factorization structure of MDPs to further enhance sample efficiency. By designing a factored empirical Bellman operator with variance reduction, we achieve exponentially reduced sample complexity with respect to the state-action space size (cf. Theorem 6.1) with matching minimax dependence on the other parameters.
Factored MDPs. Our model generalizes the framework of FMDPs (Boutilier et al., 1995; 1999), extending to account for approximation errors. Most existing work on FMDPs is set in an episodic framework and primarily analyzes regret performance (Guestrin et al., 2003; Osband & Van Roy, 2014; Xu & Tewari, 2020; Tian al., 2020; Chen et al., 2020). In particular, the state-of-the-art results translate into a sample complexity of Õ k=== |xlle-2( - 3)), where the complexity scales with the sum of the state-action space sizes [.&s] across all factored components. Building on this line of work, we propose factorized synchronous sampling technique that enables simultancous updates for multiple components using a single sample. By coupling this with refined cross- component variance analysis, we reduce the sample complexity to as low as O (max;] X c 21 - -33 in an instance-dependent manner, which only depends on the maximal component size rather than the sum. This result matches the lower bounds established in prior work (Xu & Tewari, 2020; Chen et al., 2020), up logarithmic factors. Crucially, our approach does not require the MDP exhibit perfect factorizability, allowing for broader applicability to general MDPs.
RL with Function Approximation. To make RL problem sample efficient for large-scale problems, common approach is to employ function approximation (Sutton & Barto, 2018). Intuitively, the key idea is to limit the searching space of an RL problem to a predefined function class, in which each function can be specified with a parameter that is low-dimensional. This approach has achieved significant empirical success (Mnih et al., 2015; Silver et al., 2017). However, RL with function approximation not theoretically well understood except under strong structural assumptions on the approximating function class, such as the function class being linear (Tsitsiklis & Van Roy, 1996; Bhandari et al., 2018; Srikant & Ying, 2019; Chen et al., 2023; 2024b), the Bellman completeness being satisfied (Fan et al., 2020), or others (Dai et al., 2018: 8; Wang et al., 2020). Also, the function approximation often targets to approximate the Q-values, instead of exploiting the inherent transition kernel and reward function structures. In this work, we take a different approach by leveraging approximate factorization structures instead of implementing function approximation. It is also worth noting that our approach is highly flexible and can be further extended by incorporating function approximation techniques, providing an even broader framework for tackling large-scale RI problems.
13

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
B. An Illustrative Example of Approximate Factorization
To provide intuition, we present an example applying the approximate factorization scheme in a real-world application, demonstrating that it offers additional opportunities to achieve a better balance between desired solution accuracy and sample efficiency. In particular, we consider the storage control problem (Xu al., 2024) in wind farms. The storage controller (the agent) aims to align the real-time wind power generation output (the state) with the desired prediction values by flexibly charging discharging the energy storage system.
This problem can be modeled as an MDP, where the state at time t, st = (w,, ca), captures the wind power generation Wi, electricity price pt, and the state of charge (SoC) of the storage c₁. The action dy represents the storage charging decision at time I. The transition dependence structure can be represented as a bipartite graph, as illustrated Figure ((a). In the graph, nodes on the left-hand side (LHS) represent the state and action at time t, while nodes on the right-hand side (RHS) represent the state at time + 1. A solid blue line between nodes indicates strong dependence. For instance, the electricity price Pt+1 strongly depends on the previous price Pt- While dashed blue line represents weak dependence. For example, while the wind power generation can influence the next step's s electricity price Pt+1 in the market, its impact is weaker compared to the direct influence of the previous price
Figure 1(b) illustrates an approximate factorization scheme on this MDP, where the system's 's dynamics are divided into three smaller components the dynamics of the wind power generation, electricity price, and storage levels. Strong transition dependencies are preserved within each component, but weaker dependencies, such as the influence of wind power generation electricity price, disregarded. This leads to the following approximation of the transition probability:
P(s (1, a4) = P(w++1/w)) P(p++1lP) P(c++1/cu az).
This approximation simplifies the model by factoring the transition dynamics into smaller, more manageable components while retaining key dependencies. Note that this problem does not fall under a FMDP, as the dynamics cannot be perfectly broken down into smaller components. However, our approximate factorization scheme offers a more flexible framework, allowing imperfectly factorizable transition dynamics to be divided into smaller components while maintaining sufficient model accuracy. This expands the factorization step's action space, enabling a more effective search for optimal trade-offs between solution accuracy and sample efficiency.
(St, a1))
(5++1)
(S1, a.)
(Sp=1)
wind power generation
W++1
x|Z|| w
W
Wh+
s
electricity price
Pt
P++1
x| x1Z2!1 p
Pt
Pt+1
8 s
=
SoC of storage
C₁
C++1
C
C++1
x12,7 (c,
$ =c
charging action
4₂
ag
Strong impact on transitions
Factorization e with K,,
Weak impact transitions
(a) Bipartite Graph Representation
(b) Approximate Factorization Scheme
Figure 1. Bipartite Graph Representation and Approximate Factorization.
C. Illustration of Synchronous Sampling with Exclusive Scopes
An example of synchronous sampling with exclusive scopes is illustrated in Fig. 2. Specifically, this factorization contains two components and the transition of state the first component depends on x x[Zf] = x a<(1,2)), while for the second
14

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
component, its associated state's transition depends on æ =[ZZ]] = s|[3]], where 2 Zf 0, which means the transitions of the two components don't have common dependence. The classical sampling process within the FMDPs involves sampling all possible entries from the sampling sets of both components, leading sampling cost | + [xg While equipped with the exclusive scope property, we can simultaneously sample the entries of both components in single sample. Thus, the total sampling cost equals the size of the larger sampling set, i.e., max([22] () I).
Independent Component-wise Sampling
Synchronous Component-wise Sampling
Sampling Set Component
Sampling for Component
Joint Sampling Set for Components 1&2
zfa
(1.2)
of
1
(3)
[1.2]
2
7
(3)
x[1]
x[2]
x[3]
x[4]
x[I]
x(2]
x[3]
x[4]
x[1] x[3]
x[2]
x(4]
Entry
Default
Entry
Default
Default
Entry
Defauit
Entry 2
Default
Entry
Default
Default
Entry 2
Defhult
Entry
Defuult
Entry 3
Defiult
:
Eutry|Ar/251
Default
Default
Defoult
| 1ag"
Entry Disoo
Default
Total Sampled Entries - |282 122
Total Sampled Fintries
Dmax
maxi (xx (A4''))
Joint Sampling Set Design
Figure 2. Synchronous Sampling with Exclusive Scopes.
D. Proof of Theorem 5.1
We aim to ensure the total number of samples Dw satisfies the following lower bound:
D Nentry N Dr,
(13)
where Neany denotes the number of unique state-action pairs that must be sampled, N is the sampling frequency for each pair, and D is the sample complexity required to estimate the exact reward function.
The term Nentry is directly specified in Algorithm is defined as the total number of state-action pairs across all components to be sampled. Mathematically:
Nentry Exeled maxkeg, [ Eneln | II.
where Kp is the total number of sampling sets, G3 is the set of component indices associated with the i-th sampling set, [x[2]]] denotes the size of the state-action space for component k:
For the sample complexity associated with estimating the reward function, D,, it is sufficient to sample all necessary state-action pairs once for each reward component r; obtain the exact reward values. Similar to the transition kernel sampling, the sample complexity of the reward function is bounded by:
D, & [ax
where is the minimal number of sampling sets required to estimate the reward function, and [ is the size of the state-action space for reward component T;,
Therefore, we only need to determine the required sampling frequency N. Recall that, the error ||Q - @i comes from two aspects: 1) the computation error in Algorithm 2 due to finite value function iterations, and 2) finite sample error due to inaccurate estimation of P. Since the value iteration algorithm converges exponentially fast, according to Section 5.2 in (Shi al., 2024), T' to log( (T--))) is enough guarantee the computation error O(e). Instead, focus on the estimation error due to finite samples. To do so, we decompose the estimation error of the Q-value function into two terms, the bias &
15

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
and the finite sample emrrr oN- By applying the triangle inequality the error, we get:
||Q - Qullx - 1Q - QWlloo +
Q Q loc
(14)
Bias En
Finite Sample Error
where
Q* is the optimal Q-value function induced by the actual optimal policy n², transition kernel P, and reward function
2 the estimated Q-value function based on the estimated policy Th, estimated transition kernel Pu, and estimated reward function Tw. where
Kw
Pu(('(z) = II
x af Ps
E ES, Vx EX,
k=1
(T) Σ
1=1
Q is the optimal Q-value function based on the factorization scheme which assumes the utilization of infinite samples. It is induced by the policy Tw, transition kernel P., and reward function Tw. where (s((z)) is defined as:
Pals' (z) = lim 2s
N -000
The limits exists due to the fixed sampling algorithm and the law of large numbers. DUe to the deterministic mapping between P and Q, we have limy-toc Q: = Q" with probability 1.
Thus, the finite sample error term ogy = |0% @ ol in the decomposition can be made arbitrarily small as increases. Instead, the bias & doesn't vanish due to the approximation errors from factorization.
For the bias term E., it can be bounded as follows:
Lemma D.1 (Proof Appendix F.2). Given any factorization scheme w, the following condition holds:
Al 7AP
& = 1|Q -w <
(15)
(1 7)2
Then, focus the finite sample error term aN. Using the result Lemma F.4, have:
Q t S 71 - -P= - -P -P,)
(16)
:
Q ② 2 (I [I -
(Pu -
PL)VV
(17)
=
where P E [S5S represents the transition matrix of Markov chain {(s,, 0z)} induced by policy o under transition kernel P.,, and - E [[S)||I is induced by policy # under transition kernel P...
Based on Eq. (16) and (17), the error term a, satisfies
N = || -i S max( Iloo 1oolo
(18)
Now we only need to control || and |2 We first control the absolute value of the common term (P,, Pa) for both A and Ag in Lemma D.2.
16

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Lemma D.2 (Proof in Appendix F.3). Given sample size N, then with probability least 8, the following condition holds:
2 ID)
2 K=
() Varp, (Vi)
I(P= PL)
3N(1 7)
N
where| denotes the absolute value function, Varp (V.) denotes the value finction variance with transition kernel Pa,, as defined in Definition F.I.
Using the naive bound 17(1 - -PP))-1111 - for any and combining Lemma D.2 with Eq. (16) and (17), we can show that
A 27 log (2) (2,111
2 2 (2 K- 21
(P-)) / Varp (Vi),
(19)
3.V(1 - -7)2
N
27 log (2) 2 Kw
k=1 [1
2 (0g((2,.0
Kw 2
k= (1
2
1 1+
(1 --P-" (1-- Varp, (V2).
(20)
31 - 7)
The remaining challenge is control (I P
Varp, (Vi) and (I- -1-7P=--- Varp (V:5 for A and Ag.
respectively. We first bound the term (/ - 7P " )-1 another term is analogous. Specifically,
Varp, (V&) for A1, which is slightly more complex, and bounding
(I - Varp. (Vi)
=(1 -P 1 Varp. (V3) - Varp, (V2) + Var (Vi)
=(1 7 P
PV(V2)2 (+) PV + (2LV3)² + Var (V))
=(1 y P
(PL P.)(v ((P2))) (PLV3)3) + Varp, (V2*)
<(1 P
VICeL Pa) VI(PV222 (PAV))
Var (V()
(I P
VI(P - P.) " (P.V:)) (P.V3)
Ti
38 (1 - (1-7Po
/Varp, (Vi).
T3
This splition allows us to focus on Ti, T2 and T3, which can be controlled by the following lemmas: Lemma D.3 (Proof in Appendix F.4.. With a probability at least 1 8, Ti satisfies
log
22 1.
Ti Σ (1 71
N
Lemma D.4 (Proof Appendix F.5). With a probability at least - T2 satisfies
log 22 2(11)
V2
T2 2 (1
7
N
Lemma D.5 (Proof in Appendix F.6). The term T7. can be bounded as follows:
2 2lo
k= 2F11)
47
1 1+>
T3
(1 33
N
V
(1 7)3
1.
17

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Combining Lemmas D.2-D.5 yields the bound of Ag: Lemma D.6 (Proof in Appendix F.7). With probability least 8, the estimated Q-function Q satisfies
log 2811
log (2 Rw -
A S 18
+ 6
N(1 7)3
N(1 - 7)3
Analogously, we can show that with probability at least 1- 6, |Ail also satisfies
log [ ZF
log (2) 2
A1 S 18
+ 6
N(1 3)3
N(1 - -)33
Combining the bounds on | and A2). we have that with probability at least 8,
11 201 I max([A1) 142l)
log 24 24
log 24 2
<18
+6
N(1
7)3
N(1 7)3
log( (og(24/221uff 2(1l)
Taking any e ||Q @illx S 1, we can first verify that
S Therefore,
N(1-3)3
$
K2 2 log [21 1=
S (18+6)
N(1 - 733
directly yields the bound for N with probability at least 6
576 log (24) 2X11
(21)
(1-7)38²
Substituting Eq. (21) into Eq. (13) yields:
576 (Np max [x(2(]] log (24)2(UREEKKS ( + Mr max [1|2,'1|| rE[tml
D 2
e² 73)3
Letting Co 576 and ह 24 leads our result.
E. Proof of Theorem 6.1
Proof. Similar the model-based case, we show the total amount of samples Da should satisfy:
Dw Nenty N Dr,
(22)
where Nenty denotes the number of sampled state-action pairs for generating a single empirical Bellman operator in Algorithm 3, and N denotes the number of generated empirical Bellman operators. Notation D, denotes the sample complexity of finding the exact reward function.
The term Nentry can be directly obtained in Algorithm 3, which equals the sum of numbers of all stue-action pairs in all decomposed components, satisfying:
Nentry Σ
vElepl maxked. |x|zR|| S Σ Exeroga |
18

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
where Ky is the total number of sampling sets, 93 is the of component indices associated with the i-th sampling set, [x denotes the size of the state-action space for component k.
For the sample complexity associated with estimating the reward function, D,, it is sufficient to sample all necessary state-action pairs once for each reward component r; to obtain the exact reward values. Similar to the transition kernel sampling, the sample complexity of the reward function is bounded by:
D, S
Liis.)) kE(k.)
where is the minimal number of sampling sets required to estimate the reward function, and [|[2,"]] is the size of the state-action space for reward component r;.
For the sampling times N, according to Algorithm we can conclude that:
T N N=E,a (N+ + M)
Σ T
Nr MT,
(23)
where T' is the number of epochs, N, is the sampling frequency for estimating the reference Bellman operator in the 7-th epoch, M is the number of variance-reduced updates in single epoch.
The key of the proof is to show the estimation error decays exponentially when the number of epochs increases, i.e.,
Lemma E.1 (Proof in Appendix F.8). For any ô 2 0, with probability at least - 8/T, , the Q-fimction estimate Q, after T epochs satisfies
Qullo S (1-7)27
VT #T=L,....5 I....,T
(24)
provided that the number of samples M and the number of iterations N₂ satisfy the following conditions:
6TI 1
log
(1-7)0
M = C2
(25)
(1 11-7) 7)3
log (6T|2(UK=, K. zF11)
Nr c34
(26)
7)²
whereny ni- = 1+(1-)((+1) C2 C3 > 0 are sufficiently large constants.
We first ensure the error decreases relatively small value VI-- after Ti epochs. Specifically,
T = loga (v-=))-
(27)
Using the union bound over all r S Ti in Eq. (24), we obtain that with probability at least 1 - 8:
Or:: Q7 S V1-7
Substituting N,, Tí, and M into Eq. (23), the total number of samples for this phase, denoted N(11, is bounded by:
[ 2fll
log
-log
(1-7)8
Npj S
(28)
(1 7)3
where e₁ constant depending on C2 and C3-
epochs are sufficient to reduce the We now show that from initial point Qn = Qr, an additional T2 ccoo22 (vI-T)
)
error to e, where c > 0 a constant.
We utilize the following lemma:
19

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Lemma E.2 (Proof in Appendix F.16).
Given 1o 10
and setting:
VI-!
677 2 (1-1)6
log
M 02
(29)
(1 7)3
log
67 62 Ku 11
N, = Cg 4
(30)
(1 71-
then, with probability at least 1- -:
10, - Qullo S
2 VI- VT VT 0.
The proof of Lemma E.2 follows similar routine that of Lemma E. but leverages the better initial estimate Qu- This lemma indicates that starting from an initial error of Vi-ク" the variance-reduced iteration halves the error each step.
After Ta = c' log2 vI-Te )
epochs (with c' > 0), the error reduces to The total number of samples for this phase,
denoted N12 bounded by:
log
6Ti 2!ll (1-7)6
llog (1-7)
Npp S 65
(31)
(1 (1-7) 7)
where C5 is sufficiently large constant.
Combining the samples from both phases, the total number of samples required is:
N Mnj + N(2)-
Substituting back into Eq. (22), conclude that the total sample complexity D., satisfies the desired bound:
D 2 Neary (N1) + N2a) D,-
This completes the proof.
F. Proof for Auxiliary Lemmas
F.. Preliminary Definitions and Lemmas
In the following, we provide all necessary definition, preliminary lemmas. For self-contained, we provide the proof's to the lemmas according to the notations of this work.
Definition F.1. Let (V) E IR (|||A| be the value function variance with transition kernel P, which is given by:
Varr(V)= PPV) (PV)²,
where P E x[SSSAAX(Ss is the transition kernel, and (V)² E |S| is the element-wise product of V, i.e., (V)² = V VoV. Definition F.2. We define E (8, a) as the variance of discounted reward under policy and MDP M given state and action a, i.c.,
(s,a E
Σ Yr((s, a.) - -Qi (su, ao)
So = s, ag =
where Q denotes the Q-function induced by policy æ under MDP M.
20

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization Lemma F.3. (Lemma 2.2 in (Agarwal el al., 2019)) For any policy n, it holds that:
Q Q - PVV",
where Qa and Q are O-functions induced by the policy т under transition kernels P and P, respectively, and Pr RISIIA ((SIAA) represents the transition matrix of the Markov chain ((8e, 0t)) induced by with transition kernel P.
Proof. Recall that Q is the unique solution of the Bellman equation:
-
Since - 7 7P is invertible when < < 1, we have
= =1 (1-
(32)
It follows that
Q- Q" (T p- - (I 1 p--)-
(1 7 PT) 1ap)--((( (1)))-((111111111 ( - -(1 - --pp))) -
7(I pp-) "p -
(P=
- Pn) -yP")-1
= -T - 7 P - -P-10=
71
where the fourth equality due to Eq. (32). The last equality is because PTQ" PV*
Lemma F.4. (Lemma 2.5 in (Agarwal al., 2019)) For any two optimal Q functions Q" and Q", which are induced by the same reward function r, but different transition kernels P and P. It holds that:
Q'-Q' 1 - -PP-PVV
2 Q'
Q- 26'22((
(P-
where x² and 7t are the optimal policies induced by Q-value functions Q' and Q+, The matrix par E [RISIA represents the transition matrix of the Markov chain {(S,, ar)} induced by the policy n²" under the transition kernel P. Similarly, pa | represents the transition matrix of the Markov chain {(s,, induced by the policy i** under the transition kernel P. The optimal value function V is induced by Q", which satisfies V V*(s) max, (* a for all stales S.
Proof. The two conditions can be proved using Lemma F.3. Specifically, the first inequality be proved follows:
Q @*+
Q" Q 7 - -P)v,,
where the inequality is because Q 2 Q for any policy The last equality comes from Lemma F.3.
For the second condition, we have:
Q' Q' Q=² Q
Q (T 7 ;p* 1
(1 y Pa ) - 7 )²² (1 - ) - 788 )Qa*
(I ? pa 1 - 7p" ) - (I --p"" 1)Q²"*
7(T P ) 1(p= pa )Q=
2 7(1 7 ) 1pp - QQ"
= Y(I 7 68* )
The second equality because Q" = (I - 11-pp=)111 r, and the inequality is because "0Q"" S p Q=
due to the
optimality of policy #² regarding Q-function Q"
21

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Lemma F.S. (Adapted from Lemma 5 in (Azar et al., 2012)) Given a MDP M with transition kernel P and reward function r, the following identity holds for all policy
EM = 7 -1-1-22pp7
Varp (VM)
Proof. We start with the definition of IM (s,
2 (s, = P,p Σ
0x) (1 ao) =,
Ep
7'r(st, 722 - (aaaai)-((((0000 ao) - r(50, ao) 7QM (81, a.))
80 8, 00 = a
Σ 7/r(s), - -(0
80 = 00:00=0
00
p,
(5r(,), 7Qth (1)) (0Q
(Mhr (50, ao) - r((0,, ao) - (11,
30 = 8, 40 = a
t=1
+ Ep..
(Qir (su: ao) -r(so: ao) - 7Q70 ($1, a1))
8o s, 0u =
= -P,
7 1- 1--1 "((s ax) - (1.
8u = s, 0g = -a
2
E
('r(s), ax) - (8r (1)
81,01
(80: u0)
r(s0, un) - 7Q% (81, a1)) 80 8, do
+ Ep,
(Qhr (50. 0o) -r(so: ao) - 7Q% (51, 2
30 = 8, ag = a
2
= ~73Eppa
7 (- (s1,, ax) - (31
80 = s, 5,00 =
+ EE,,
(Qh (50, ao) - -r(so: ao) - 7Q7h ($1, a1))
5,00
2
= =?3Ep,a
- -
80 = 0,000 =
+ 7 P,r
(Ree
1QM (0 (1r( 80 = 0, = a
a a1))
7 Σ (s)
$1.91
where the third equality is obtained by dividing the quadratic term; the fourth equality is derived by the law of total
expectation; the fifth equality holds due E Ex 7 (r(((),))))) (z) (s1, 81, aj] 0. The last equality is derived based on the definitions of (s, a) and Var
Lemma F6.. (Lemma 6 in (Wainwrighr, 2019b)) Given two Q-functions Q; and Q which are the induced by the same transition kernel P, but different reward functions and 7 r + Ar. It holds that,
IQ - QQ1 max { (T- Ar|, (I 7p* y A|rr]
where n² and म" denote the optimal policy induced by Q" and Q", respectively.
Proof. This lemma can be proved by showing the following two conditions:
max(Q" - -²,"0) S (T - -T--P' 7p Arl,
(33)
22

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
max(Q* Q(, (1 - Arl
(34)
For condition (33), prove the following:
Q' i r Px Q- - (r + Ar + 7 -p==''))
I Arl + PT (Q' - Q"))
< Arl + pM max - ,0,,
where the second inequality comes from p Q' S P Q²
Since the right-hand-side term is positive in all entries. Thus, have:
max - Q0" Arl + Tp= max(Q' - ,0',)).
Rearranging the inequality yields Eq. (33).
For proving Eq. (34), we follow a similar routine and get:
---Q- (r + pd Q²) - (r + 7px Q*)
< Ar| + 7p (Q' QQ")
s Arl + pa max(@" - -2" ,-,
Hence, we have:
max - .) |Ar| p max( - 0),
Rearranging the inequality yields Eq. (34). Using IQ' - Q-1 = max(maax(Q'>aa max((" -00 -Q",)) and combining Eq. (33)-(34) yields the desired result.
F.2. Proof for Lemma D.1
Proof. We first write the Bellman equation of Q" and Q as follows:
as(s,a)= Σ max
max (s',a')
(35)
((( = (s) + Σ max max
(36)
Subtracting Eq. (35) with (36) yields:
Q*(x,a) ()) = r(8,a))
- (s, + Σ m() ( max (s',a'))
Pa
= a - (s, +
(' max (s','a)))
o' + +P(('|ss,)) (s a)) max ('','
Taking absolute value on both side yields:
(s, (s a)l S - ralloo + (P -aa.mmmmmm-xxmm (2(
+ 7 Pw Pullae max (s' a')
< rulloo + > 2b + 7 P Pull max Q (s',a')
(37)
23

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
where the last inequality comes from max, (s, a) maxa QN a)l S max, (Q" a) QT( s 11Q
Due to Q (s', a') l for any state-action pair (s', a'), we have:
IQ" - Qullo - max (s, (s,aa
rwlloo + >11Q" Qullo + 1-7 - Pulloc
(38)
Standard mathematical manipulation on Eq. (38) yields:
|||- rwlloo
P| Pu loc
|| @w I
1 +
(39)
(1-7)²
Applying the definitions of approximation errors, we have:
A R
+ 3
11Q - Qu1l -
w
(40)
1 1-7 (1 71-
This concludes our proof.
F.3. Proof for Lemma D.2
Proof. We leverage the structure of the factorized transition kernel and show that the vector (Pa - Pw) contains multiple identical entries. By identifying the distinct entries, we can focus our analysis on a subset of state-action pairs.
Recall that (Pu- V [ISAA represents the difference between the actual and estimated reward vector. Due the factorized form the transition kernel Pa, the estimated transition probability P(s' x) is given by:
K
P(s
x = II (s
where each (s xx(z,)) depends only on the subset Z of the state-action pair x. As result, only the state-action components x|Z,"] for & E [K,] determine the transition probabilities. Thus, there are at most [ k=1 2f'1 distinct rows in the matrix (Pu- P.)).
We use X to denote a set of state-action pairs indicating distinct entries, satisfying:
f E E Vel x" E Xx, x' + x² + 3 [Km] such that x a'(2 xx" x=(2
X x-=
(41)
For any x E 2²", easily verify that the estimation ((s'| x>) is unbiased:
E ( x:) - P(s') |x)
He (17p) N.eG. Pa(s/ZE11 x((()) - -I nhea. Pa(3112]1 x(<"1))
P(s'lUkea, d x xlURee 2(1) IILetra P(s'UUnEe, 2 ulukea 2F1)
(m())
[[[P(s
2 xlUkeg, z|1i II P(s'[Ukeg,
| æ|UREG 2(1
=0.
The third equality is due to the independent sampling of different sampling sets, and the last equality is due to [sP(Kul z z/Ukeg, 2 = P(s'[Uneg, z r[Ukeg:Z[] within each sampling set due to the law of large numbers.
24

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Also, since 0 V < - 1, we have II(Pw Vill s - Combining with the Bernstein's inequality (Vershynin, 2018) with sample size N yields that:
1 NNrrr (Vo)(a)
P (P 2t) - 2xxp
(42)
3(1
where Varp, (z) denotes the entry of Varp, (V2) corresponding to
Letting the right-hand hind-side of Eq. (42) equal | ku I
leads the following inequality:
N² 82 Nar (V+)
2exp
X X k=1 21
3 ((1-9)
Rearranging this term yields that
2oog( (MUU 3N 11
2 2log( A(ll Varr, (Vi)(e)
t -
+1
N
Taking the union bound across all state-action pairs x E X", and using the identical entry property yields that, with probability least 1 d:
log log((IX(UU Km z Varp, (V3).
+ 2log(1 Kk= zxoll) 1.
(Pw - Vv sV
N
3N -7)
This concludes our proof.
F.4. Proof for Lemma D.3
Proof. We have that
III K
II K.
((P_-P2)VV))
(a(
|
1==1 Pa(6'12)1 x()
Following the same routine in the proof of Lemma D.2, we known (Pu 1Pu-Pal (V))) contains most | 2[') entries.
distinct
Meanwhile, for each single entry of (Pu. - (2)(( denoted by (Pu(-Ix) (V we can show the following conditions:
B((P.(+))) - -
0,
II(P - P1) & [V:3( + (P2 S 71-
With N i.i.d samples for estimating (Pu(-lx)) (=(+)= R. we apply the standard Hoeffding's inequality to
(Pu(-l<) (V))) as follows:
2N
= 2exp (- (1(1-))\Ne) Vr E X
P (()))())))P 2() < 2 2cxp
(T )2 J2.N N
2
Letting the right-hand-sice term be (with definition in Eq. (41)) yield:
و and applying the union bound across all distinct state-action pair E X
log
/2 K. [
[I(P. - P.)( 5 (1 (1-7)²
N
25

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Thus, Ti satisfies
Ti = (T -I- "V00 ((P.. - PV) - - 11 V /|(e= PL)((
2log (2 2B11)
1
5 (1 - 7)2
1.
N
This concludes our proof.
F.5. Proof for Lemma D.4
Proof. We first bound (P2) - (PuV oc as follows:
[[(P2V - (P,V 11(P2V + (PVV) P.V
- 1PPVV + P.Villooll - PuVilloo
S 22IV PC)
Applying the Hoeffding's inequality to lI(P Pu) xo yields that, with probability at least 1 6:
2 log (2
Pu) S 1-71
(43)
N
Therefore, T3 satisfies
To (I (1= V
(P2 V2)a -PPv3)1
$ [[[ - - |00 (PoV (PaV
1
$ 1 7 V211V 11 (P
Vo 1
2 /2 z
V2
$ (1 (1-7) 71
\
1.
N
F.6. Proof for Lemma D.5
Proof. We decompose T3 as follows:
T3 = - 7p )1 Varp, (V=)
(I - 7 pp )-1 Varg, (Vo. - 1. Vit
V. Ru +
< (1 )p )' Vary, (V3 (/:) + 2aa (v ) + 2 2aa
(V Vi5
< (1~ 7
Var., (V3 - V + (1 - 7 ) -1 // 2Vrr (V
Toi
Tsa
+ (T - 7 11 Var (V ,o
T3a
26

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Then, bound T31, T32 and T33 separately.
Step 1. Bounding T31:
For T31, the following condition holds:
Ts = (I- - (I->P=")- " 1/2 (V -V5+
$ 11(11 -PPa " 11 2/ Var (V= - Voo))lo0 1
< V2
V IIV3 -
-V-- 1
$ V2
VIQg Q 12
Applying Lemma F.3 yields:
11 - 11 117(1 - 7P-)) - -Pu Vil
722 (1 {1 [( 11..
Applying Eq. (43), we have that, with probability at least
8, the term || - @:i 11 satisfies
2 log 2 Rr 2
72
110 - --- 18: S (1 7)a
N
2x² log [2) zf'1
(44)
N(1 7)
Therefore, with probability least 5, T3i satisfies that:
2 k -1
27 Ta S (1 33 V
N
Step 2. Bounding T32:
Note that, (1 - (T (1=))(->p=>))) is a matrix of probability with each row being a probability distribution, For a positive vector v and distribution v, Jensen's 's inequality implies that v S vv v (inequality of expectation). This implies:
| -1- Varg, (183)
1722|l00
1 1- (1 (1= - - P Varp (V D
(I -- ) Var p. (1552)
(45)
Also, we can reformulate [I(1- )2 -2 Var p (Vo>))lo
1
ol as follows:
[I(T ([I--PP) -p Varp (V==))l>> )1100 = ||(T - - 2 --a (V 11bb
27

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
= |I(I [11--1 PP ) P Var p. (V 1
|1(1 -[(+=~)--(-~>???))) Varp. (V )1o00
- 11(T |1ml111
- x (1+"))(4->?PE* -Varp, )loo
- Var p_ "w))ll>>
Thus, we have
(U->pry- V Var p_ (Vo
1 (T - 22 Var (w
We now connect this result with the definition of E5 in Lemma F:5:
M = 71 -1- Varp P. (V=-), )
where the transition kernel of MDP M is P.. Therefore,
D 72
(I - P 1 Var Pa
S
(1 7) 1,
where the inequality comes from F22
|
ll S (I-7)3 for any policy n,, which can be easily verified according Definition
x²
| 1o
max
E
Σ 1=
r ()) Qhr Qhr ao)
50
5,00
5,
0
(8,0)
max E (8.0)
rrr(s,, az) (s0 an)
50 3,00 3.00
0
22
(1 - 7)2
Substituting this condition into Eq. (45) yields:
1 1 713
Ts2 S
1.
Step 3. Bounding Tas: The term Tas satisfies
Ta3 = (1 - )---1-1 Var p. (V V22
< 111 -
-P= ) 10 v // Var (V33 - )lo0
V2
VIREO - -13- 12 1
< 1 γ
/2
Vio:: Q lg 1.
< 7
Similar to the bound of T3 in Eq. (44), we have that with probability at least 1 - 6,
2T² log
(2) K., 2(
11 11
N(1 7)
28

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Thus, with probability at least - 6, T33 satísfies
2
22)x0 K- x- k=1 2
T33 27 (1 73
1.
N
Step 4. Combining the Results:
Combining the upper bounds for T31, T32 and T33, we can bound T3 that, with probability at least 1 - 8,
(4) ZŁIl)
2og
47 (1 733 V
1 1+7 1.
T3 5
+V (1 11-7)) 7)3
N
F.7. Proof for Lemma D.6
Proof. Taking to be 3. and applying Lemma D.2-D.5 yields:
log (12 k- 2F11)
log 12 k= 2
K~
3
/ S (1 - 7)3
(1 - 7)2 71-
N
1/2
K2 log (2)x((u===211
2
+ V (1 - 3)
(46)
N
Applying Bauchy-Schward inequality yields:
1/2
log [22
log
Kw k= (
3
2
(1 3)3
N
+
V
(1 3)3
y1-
N
log [2) 2F11)
log (12 2R11
1/2
2
(1 - 7)3
N
V (1-
N
log 12 12
K_
= =v3(1 - -
N
log [2 K- (
v3
(1 11-7) 7)2
N
Applying this condition to Eq. (46) yields:
1/2
3(1 + 3
log (12/1 ( 2
V2(1 + )3
log (12) zf11)
1 - - loo 5 (1 - 73
V(1 7)3
log 12 K. [0]x
log
/u 2
<18
+
N(1= - 7)3
N(1 - 7)3
This concludes our proof.
29

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
F.8. Proof for Lemma E.1
We prove this lemma by induction. We first show that the base case (T 1) satisfies Eq. (24), and then prove the inductive condition when 7 2 2.
Step 1. Showing Base Case with == 1:
Due to the initialization, we have Q a) Qo a) = 0 for any state-action pair (8, a). Therefore, for T = 1, both the empirical and reference Bellman operators equal to the immediate reward:
(Q, r(s,a) and
(- r(s,a), V(s,a).
Given this, the variance-reducee update in Eq. (11) simplifies to the standard Q-learning update:
Q: = - ((11-(t1))---1 + f|- (Q-=)))
= 1,..., M.
Let A Qi Q denote the estimation error at iteration t, where Qw is the unique fixed-point solution of the Bellman
equation H(Q) = Q. Then, we have:
A (1 1): - n (H: + 1 H(Q2))
(1 1}: A + //- ( (Qh + 4,-1) 1
+ H. H1-11 (QW) H((2))
(1 1/-11 + 7 (Hi-1 A--1) H,-1 + (Hi-1 H((2))
(47)
Contractive Erro:: W/ (1)1(A
Random Error:
Observe that the error iteration 4, consists of three components: the decaying term (1 - --tt-)) the contractive error term (--1-Ar1), and the random error Et-1-
The contractive error W depends on both á,1 and the empirical Bellman operator 7l, and is bounded due to the r-contractivennsss of H4-1;
[Ar ST1
(48)
The random error E is i.i.d. for different values of L. By applying the iteration in Eq. (47) and using the contraction condition in Eq. (48), we can express A fully as follows:
Lemma E.7 (Proof in Appendix F.9). For any t 2 L. the estimation error A is bounded above and below by:
A
II
-00ll +
+7
Σ
II (1 (1 (1-11-1)0)))
m 1:11.31100
+ Pt, (49)
k=0
j=i-1
(1 -1- (1 (1-))1))))) nll.P/1000
A
[1-)))))lllll -
1 + Pt,(50)
k=0
/=++1
where Pt represents a discounted sum of the random error & defined as:
0
ift 0, ift 2 1.
P.
E1-1 (ITT (1-))) mcEk)
(51)
To effectively manage the product term I (1 (1 7)m)), we apply a step size defined as 7k T+(1-9)(++}} this choice of step size, we can demonstrate that the expression 1 - (1 7) satisfies
Under
1-7
-- (1 7)
1 (1 - (k + 1)
1 1 (1 - k
1+ (1 ()
30

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
A4
Using this result, we can simplify the product-form coefficients in Eq. (49) as follows:
(-
II (1- (1-))))
7))))
7
Vt, = 1,-1,
7h-1,
(52)
k=0
Jmm1
A-1
(-1
II (1 - (1 (1-7))))
TJ
n =
17.
(53)
7/-1
-=++1
Substituting Eq. (52) and (53) into the bounds in Eq. (49) and (50), we obtain:
A I A-1ll + Mh-1 Σ
|| Pa + Pell
(54)
To complete the proof, we need to control P& for each k. The following lemma provides the necessary bound:
Lemma F88 (Proof in Appendix F.1.). Given the step size mi 1+(1-3)k for any k: 2 1, with probability at least the weighted error sum P& satisfies
5,
2 2110211 log [21x10522 25
2 P S - 311-7)(1- (1 - k) log A 21
(55)
7/
where dg the variance of each random error & satisfying as(s. a) = Var (1.))),
This lemma shows that (/ is decreasing in the iteration number Substituting the bound Pkllo into Eq. (54) yields the following results:
Lemma F9 (Proof in Appendix F.II). With probability at least the estimation error AM after M iterations in epoch
1 satisfies
x('] [2 pm
[2 Kw x[1 log(1 + (1-7)M)
3 + log
2 log
à
| 1o S
3(1 - 7)2
3(1 - MM
(2M /2MiaTu 2
6 2 Io log
(1 ++
BTI
kmj 2 (1 738
log
Let M C2
with sufficiently large c2, we have:
(1-7)a
Vilo2llo +1
1
10 2 ||Arlloo s
(56)
2
2(1 71
holds with probability at least 1 - 8 T. where the last inequality is due to basic case with 1.
1102 I (I-7).
This finishes the proof of the
Step 2. Showing the Inductive Case with 2 2:
We assume that the input Φ, in epoch 7 satisfies the bound
Vl llo
+1
10, - Qoll <
= by
2r
31

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
and our goal is show that [Q,+1 - 2o f with probability at least J
Specifically, 4r+1 is equivalent to the output Qa of running M rounds of variance-reduced Q-learning from the initialization Qo = Q, The reference Bellman operator Hr is obtained using N, empirical samples.
The variance-reduced update can be rewritten into:
1-2--Qa = (1 (Qr - Q") na -R. the
-(Q2)) H.(Q.) +H,++(Q,))
Contractive Frror: Wa(Ar)
Variance-redused Error: E.
Observe that, the update form contains three components: the decaying term (1 (-+ Q*), the contractive error term (.(A,) and the variance reduced error term &,. The only difference between the variance-reduced iteration and the vanilla iteration comes from the variance-reduced error &,, which can be further split into the following form:
Pl(1²)) - H(Q2)
++++(Q%)) -Hr+1 - + = H((+)) H(Q2) - (L,).,) + H.((U)) (Q) (Hr+)(Q + + H++1(QU)
=A,(Q") - (Q.) + Hl++(Q-)) -
H(Q))
H(QU)
E2
An important observation is that, E, depends on the empirical Bellman operator sampled in each iteration i, while E and Ee are independent of each iteration, but only dependent on the reference Bellman operator T- sampled in the begining of iteration.
We apply the result in Lemma F.7 for the bound on the error accumulation in iterative updates, and get the following bound on A, Q+ Q":
|| S Me- ncllloooloo + Mh-1 E (1) oc + 11 + (PElll)) || + 11 11
(57)
where P. Pt and Pf are the discounted sums of E,, E² and E- satisfying:
ift 0,
pa
Ei
(1 - -n)) mEr)
if 1.
(58)
if
pb-
(59)
(1- me
if 2 1.
0
if 0,
Pt
(60)
me))
ift 2 1.
To simplify, we have that || P x S
|8 lo and
|Polox
||o. Since _ا 1l and | lloo are independent of f, by
substituting 7h-1 1-(1-930* we have
Mi k=o (IE 1100 + 11x)) + I|E 1lo0 + 1
76
(1E" loc + |1)))>))
+ 1 (1 - 7//tt
2 (1E² 1100 - -12
Hence, A, satisfies
Aello S Th- A/ + 79-1
Ex |
+
+| +
_ 1mx + 11)))
2
(61)
1-
The remaining challenge is to bound the following three terms:
|E |1. || and
||]]
32

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
37 E.
Lemma E.10 (Proof Appendix F.12). In T-th iteration, with probability at least
satisfies
6 K
2
2
11 100 S by)
N,
Lemma E.11 (Proof in Appendix F.13). In T-th iteration, with probability at least 1 37 E. satisfies
22 u
2
log
(Vl02llb -1)
| 100 S 11
N
where Ej is an absolute constant.
Lemma F.12 (Proof Appendix F.14). In the 7-th iteration, with probability least
S7 it satisfies
log
6T ( 1
log(1 + (1-7)8)
log
6I 6TM
p=1 2511
8
7
PEll + | I c2b,
2t
+
(1-7) 8
where 02 is absolute constant.
Combining Lemmas F.10, F.11 and F.12 yields:
21 p- 2!11
2T| _ 2('1!
log
log
6-
Vo + +1) + +
by
Nr
Nr
| 00
1 (1
M
1 1-?
OTMINIU 2
log
log(1 + (1 M))
log
+ B2b
(1 - 7)2M
(1 8
GTIN Kw zf 71-
log
and N2, cg4 log logglo6661105555 2f'1)
Substituting C2
with large enough 02 and c3 yields that:
(1-7)3
(1-7)²
Vloo
A 1ox x
21+1
(1 - 7--)2
This concludes proof.
F.9. Proof to Lemma F.7
Proof. We will prove the result by induction. First, by applying Eq. (47), have that A satisfies
A (1 7o) 7o + no (o + An) Ho(Q2)) mo(Ho((L) -((2))
5 (1 |n0]AAAlll11
E
[1 (1 -) + E
(1 (1 7)))) Pı,
(62)
where the inequality follows from the contraction property No(Q2 + Au) Ho((2) S Aollo..
Similarly, Ai can be lower bounded as follows:
A (1 7o) Ao + no (oooo + Ao) - (o(((2)) (00 -H((2)
33

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
-1 7
707 7077 1
-11 - (1 7) 2o + AoCo
- -1 - (1 - (1-7))m)) )
Pt.
(63)
The expressions in Eq. (62) and (63) are consistent with the upper and lower bounds provided by Eq. (49) and (50) in Lemma F.7.
Now, suppose that the conditions in Eq. (49) and (50) hold for A., that is:
A f at |l A 1 + b,1 + Pt.
(64)
A, 2 a. Do al 6,1 + Pt:
(65)
where
t-1
1-1
4 II (1 - (1- -)))).
b. = 1- +7 Σ
II (1 (1 -39ss)
II
nill Polloo
A=
dl
(=++1
Applying Eq. (47), A++1 satisfies
A+1 (1 A, + n W/ nett
(1 (1) A b1 P₂) + 71 |
A co nE
(66)
(1 (1)(a; Ao 00 + b,1 + Pt) + m) m Ao + b, + || E
(67)
(1 (1-7)m | + (ymil PAll + (1-7(1) 1 + (1- Pr + n.E,
(68)
bx+1
Ps+1
where inequality (66) is obtained by applying the upper bound condition (64) and the contraction property W.(A,) S De|Ael/cc 1: Inequality (67) is obtained by using conditions (64); Equality (68) is achieved by rearranging the terms.
Following the same steps, we can establish the corresponding lower bound for A in Eq. (50). This completes the proof.
F.10. Proof to Lemma E.8
Proof. Recall the definition in Eq. (51). For any t 2 2, P. can be expressed as a weighted sum:
Pt = Σ k=u E
where ar (I1 n1)) T7k-
Denote the (s, ah entry of P. as Pi(s, a). Since all & are independent and identically distributed, we apply Bernstein's inequality (Vershynin, 2018) to (s a). This gives us the following probability bound:
2 of a) + (max (Me.: (
(((P)(ssa) 2 a)) < 2xxp
V(s,a),
where 03 a) is the variance of E(,, a). and Me(s.a) is the maximum absolute value of E(s,
Recall that P; weighted sum different Ex 's and all & are i.ddd. random variables. Each &g has at most [ 2 distinct entries due to the sampling scheme, where K= 2 represents the set of possible state-action pairs involved in the components' scopes. We denote these distinct state-action pairs by X defined in Eq. (41).
Taking the union bound over all state-action pairs x = (s, E Xt, we have:
?
P P1 a) 21
of + (max lac. | MM(a,)))
34

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
To set this probability d, let PP Ptlle 2 e1) =
Then, conclude:
2 (s, (max ar Mctea))e)) )
8 $ 2 z cxp
Taking the natural logarithm on both sides and rearranging terms gives:
7
log
2 2111
Σ
[-1
2 (s,
2
max Jac, (Me(sa) et S0.
To solve for cs, we treat this as quadratic inequality:
ct ?
2 max at. MM(s.)) log
2 K_ 21
Σ
6 2
of $0.
6
6
To simplify further:
S log
2
2
max (a,, Me(sa) + $ log 2|
2
Σ
(69)
k=0
To complete the analysis, we need to bound maxi (0,, Me(e.)) and Ekzo "i,k-
Step 1: Bounding Mg(s.a)
For any k since the empirical Bellman operator Hz(Q)) and the true Bellman operator H H(QE) are both bounded between 0
and we have:
1
Me(s.a) = sup ||E loo sup [(*m(Q)) - Hl02) S
1-7
Step 2: Bounding max; |at,al
Next, we analyze the ratio dek 0.
to find max la Recall the definition of az
II 5- (1 (m:)) m.--
n1))
0t,k
To compute 4e.k a.
we have:
0t.k
17k
0t
T]k 11 - 11kh)
Using the step size ?h 1+(19)(6+13) we can express:
0t,k
(1 m)
0t,k
Given that < 1, we have 7 1 and thus:
0t,k
2 1, Vk.
0t,k-
This means that 0r is non-decreasing with respect to k. Hence, the maximum value max; lac, occurs at le = t 1:
max (r, ar.t-1 Th-1
(1 7)
35

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Step 3: Bounding Eizo "i
We also need to bound E "i. The following lemma provides this bound:
Lemma F.13 (Proof Appendix F.15). For any 2 1, the sum Ei of satisfies
Σ
t-1
2
Li,k
1 (1-1)
k=
Combining the results from Steps 2, and now derive the bound for ct. Substituting these bounds into Eq. (69). get that with probability at least - 8:
2 2110 b0 log / z6
2 log 3(1 7) + (1-
2 k=
Pr Sa S
VI+ (1-
This concludes our proof.
F.11 Proof of Lemma F.9
Proof. Letting the upper bound of each Pa (in Eq. (55)) with k ,....,A M holds with probability 1 MI we have:
2/ 2/21l03 2 Elooo log 2M x Kw I!]l
2 2og
1 <
+
(1 7)M
3(1 -
VI+ (1 7)
2M
Kw 2
2 log
3(1 7)2
1 (1 7)
/2/iiu Nw 2
2/ 2110 fl oc log
M
1 - (1-)M
(1 7)
Note that,
M
1 + (1 - 7)8 $ $ M
log (1 (1 (1- M)
1+ (1 7)x
1 1-7
M
VI+ (1 $ $110 M
2 /11+ (1-11) -1)
2 2 1 (1 7)
Σ
dx
V1+ 7)
1-7
1 1-7
Hence, Am satisfies
Aollo
2 log
Kk ZF
2 2 ao log
(2M Zf11
8
A <
+
+
1 (1 7)M
3(1 --)
I (1-
logg
2M 2M
20 1.
log(1 + (1 - M)
4 2110 11o0 log
(2MIXTU Ko 2f
+
3(1 3M
(1 (1-7)ăM
/M 2
2 /M 2f11
3+ 2 log
log + (1 - M)
3(1
PM
3(1 3M
36

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
[2 1
6 2110211 log
(1 (1-7)&M5
This concludes our proof.
F.12. Proof Lemma F.10
Proof. Recall the definition of E which is given by:
3 = - (Q,+)(Q)))))
We first note that the expectation of the difference between the empirical Bellman operators is:
Ex B -7.-(1-))) H(Q,) - -(Q.).
Due to the 7-contraction property of both the empirical Bellman operator H and the true Bellman operator H. we have:
(1,+1(Q,). - H(Q,) H(QL) 11H,+1 H.+ (Qt) |H((,)) -H(Q%))
Since both operators are y-contractions, follows that:
(7,+1 (0+) & <r1@, - 1illoo and || H(Q2)) 1r10, - Qull
Combining these, we get:
M (Q,) - ++++(Q22) X(Q.)+ 22 Qi S 2yb,
Applying Hoeffding's 's inequality to the (s, a)-th entry E., denoted as (s, we obtain:
[_2
N,e²
E (s, a)) 2() s 2exp
eexp
4b2
2b
(-
N.c²' 262
Letting 2 exp
and taking union bound for E X", we have that:
3T Ki 2['
6TTA|-1> Kr 2f'1
2
11 S b,
N
This completes the proof.
E.13. Proof Lemma E.11
Proof. Recall that E. = ((QQ")-((()))) represents the estimation error using N, empirical Bellman operators. We know that [[[((")) = H(Q.).
Applying Bernstein's 's inequality (Vershynin, 2018) the (s, a)-th entry of E", denoted E {( we obtain:
N₂c
PP S 2exp
3(17)
37

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
We set the right-hand side probability equal UU 2E11
which gives us:
exp (T1681100 + 3/-1))
N2
6 37 / 2
Rearranging this equation for e, we get:
2 N₂ clog(67 x| 2 (116 (o =
3(1 -7 ?)
Solving this quadratic equation for e, we have:
Ing (6T M
Kw 2 (1/00
+
+ 2N-11o2llo log(67 | 2
311
9(1-7)
Nr
Simplifying further, we find:
2 2log (67 [ [u K- 100) <
21 ooo log(6T ( [' K..
(1/0)
+
3N, 7)
N,
Applying the union bound over all (s, a) E X conclude that with probability at least E oo satisfies
37. the infinity norm
2 2log(67 K- 2 20100) 3N, (1 7)
21102 loo l 2/11/0)
3 100
<
+
(70)
N
Given that N, 2 e- 4TH log(8T[x"ju 21/8)) further bounded by:
it follows that
log (2 K- 2116
for large enough c. Thus, | 11
(1-7)
N. (1-1
6T 2P11
110% log
| Im S
+1
N
6T fu Nu z(')
log
(V1l88100+1) +1).
<
N
where E is an absolute constant. This completes the proof.
F.14. Proof of Lemma E.12
Proof. The term Ph evolves in exactly the same way P/ discussed before. Hence, apply the result in Lemma F.8 and get that, with probability at least 1 37
2 2 allo log (ITMINUM z(')
2M
6T ZP1
P 0c < 3(1+ (1 ())
log
Vt.
VI+ (1+
Here Mg, and 03.m denote the maximal absolute value and variance of error E..
38

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
First, we observe that & satisfies
|ا = I1H(2.) -
- - -
< [[H(Q-)) H(Q + (1+))Q+)) - (Q
< 271 - Q0
$ 2b,.
Thus, have Me,a S 2b, and Vlož,alloo S 2b,, And || lloo then satisfies
OTM Z
GTM Kw 2["
4log
8 log
|| b0 by
3(1+ + (1 - 7))t
+ (1 - 7)t
Thus, we can control the whole term by:
6TM 2
6TMIX 2
4log
8log
-
P -o +
Pt
STR--1
Σ
bt
3(1 + (1 x)
5
1 (1 7)1
0=
1=0
62 (u 2 2!'1
62 M 2011 5
4log
8 8lg
+ bz
3(1 + (1 -7)t)
1 (1 77)
For analyzing the coefficients:
1
7
1
M
+
5
dx +
+ (1
7)
1 (1 - 7]
1+ (1 - -7)t Ju 1 (1 7)x
1 -1-
7 1 (1 -7)t
log(1 (1 + (1-
1-7
1 (1 7)6
2 2lo((1 (1 7)1)
(1-7)2t
1
1+ (1 -7)t 1'
1
M
+
dx
/ (1 7)i
VI+ (1 ()-
VI+ 71-
VI+ (1 7)t
2( + (1 - 7]1 1)
1+ (1 y)t
1-
V1+ (1
3
(1 - +
Thus, the whole term satisfies
8b, log(1 + (1 - 7)) log
6TM 2m 2f'll
6b, 2
66T MUMMIUUK Ky 2F11
M Σ L |P
(71)
3(1 - 2t
(1 - 28 2t
k=
Absorbing the constants concludes our proof.
39

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
F.15. Proof of Lemma F.13
Proof. Recall the expression for the ratio #t4=1;
at.
Gr,k-1 1 7k
(1 - (k+
k+1
dt.k
(1 7)1
(1 7k
++++
Using this, we can express dt,b- for any 1 S i < k as follows:
k k+1-j
0r 0t,k
d
0t.h-j
k +1 1
1=0
To simplify this product, note that:
k + 1 j
k+1
++1+ Vj.
k + j +
Thus, we can further bound 04,4-2 by:
k +
k+1
0r,k-i S a
+
dr,k
k+1+
j=0
Letting k = 1-1--11 1, we can now bound Σ k= di by considering the following square form:
2h
Σ k=
Li,k
1
Σ
t
k=1
We analyze this term by considering different y
Case 1: 2
This series is geometric with a ratio
< 1. The sum of a geometric series can be calculated as:
1+1
80
for |r| 1.
r
k=0
Applying this to our series:
[-1
- (1+ (1 7)22
Σ
d S
1+
2
7(2(11 - -7) + +
0=0
(
Since 7 2 2. we have:
(1 71-2
(1+ (1 (1- 7))2)
0 1+
-0,,-111 + (1 (1-7)()
(21(1 - 7) + +7)
t(1 -7)
Using d;,11 = T+(I-2]7 yields that,
Σ
2
<
1
(72)
1 71
A=
40

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Case 2: 7
We -- < 1 and 1 - 2 N/2 to obtain that:
2
2k
2-2
1
S 1
1+ [+
S 2
(1,+1(1+1))
k=1
+
I-
7
Since < 2. we have y > 2 and < 2(1 - 7) Thus
af - (1 +) a - (1 + 2(1 - 7)() 2-1,,-111 (1 -))).
Using dx,11 [+(1-)](-I] yields that,
- 1+ -
(1 71-7)26 7(2 72(122121)))))1 7/ + 7)
2
5 1 (1 7)
(73)
Combing Eq. (72) and (73) yields our result.
F.16. Proof to Lemma E.2
Proof. We proceed by induction on the epoch index т. The base case when T = 0 is straightforward, as the initial approximation Qo can satisfy the desired bound. Our focus is on the inductive step: assuming that the input Q, in epoch r satisfies
11, - Qull - 6yy
we aim to show that the output Q.+1 satisfies || - Q' S 8 with probability at least 1 5 To achieve this, we analyze the variance-reduced update rule, which can be expressed as
T
Q++1= 11-1=1111 (1-m)Q + n F, (Qt),
where (()) the veriaece-reduced Bellman operator defined by
= = - - +
++++1
Here, H, is the empirical Bellman operator based on samples at iteration L, and Hr+1 is the reference Bellman operator estimated using a larger reference dataset collected in epoch
We additionally define the refined variance-reduced Bellman operator, eliminating the randomness due sampling:
=(Q.)=H(Q)) - - + H++1(Q,),
where H is the true Bellman operator. Due to independent and identically distributed sampling, we have B[F = =F(.)) Moreover, since 7/ a yccontraction, follows that F is also a yyconntaction mapping.
We introduce a reference Q-function Q, defined as the fixed point of F:
= = = H(²)) - H((T.) + H1r+
This function Q serves as intermediary between Qu and Q", potentially closer to Qu than Q" is.
Our strategy is to bound the error I 1% by decomposing it into two components:
1|Q - 1i 5 =1 - Q11 + Q Quil
=:B,
Bg

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
The term B1 quantifies the distance between the iteratively computed QM and the reference Q. while B2 measures the distance between and the optimal Q
We aim to bound B and B2 separately. Intuitively, B1 will decrease with the number of iterations M within the epoch, and B2 will be controlled by the size of the reference dataset N,. We show they can be well bounded when N, and M are properly selected:
Lemma F.14 (Proof in Appendix F.17). In the T-th epoch, with probability at least 1 8 2T
Bi satisfies
84 + B2
B1 S
N, di 1" (oggsT 2DI (1 (1->)²
and M =d log(6T)
2111(1-)) (1-7)²
with large enough di and dz-
Lemma F.15 (Proof in Appendix F.18). In the T-th epoch, with probability at least 1 6
B2 satisfies
2T
6
B2
if N, cj 4' |og(sT)X 2f and M C2 (1->)²
1 Ky 2 (1-7)
te ?)
with large enough df and dz-
(1-7)3
By combining Lemmas F.14 and F.15, we obtain:
11 5
6B2
8/
1/ 2
1Q 2z S B1
5
This completes the inductive step and hence the proof of Lemma E.2.
F.17. Proof Lemma F.14
Proof. We aim to bound B, = 1Q - Ooo Our approach mirrors the inductive case the proof of Lemma E. with key difference in the error decomposition.
Consider the difference between the iterates Q++1 and the reference @
Q++1 - Q = - 1 +...
Subtracting and adding (QF,()), and using F(Q) = Q rewrite this
Q++1 - Q (1- (Q:
(Fi(Q)) ( + m (f(()-
The first term represents the contraction towards Q. The second is 7-contractive because
- 5> 57|10. -
which is easy handle, and the third term is an i.i.d. zero-mean random variable across iterations 6, with the magnitude can be bounded by:
- (ī) (e))lo + (TT
lo( 2211 Q.loo
Hence, the iteration of Q++1 @ mirrors the iteration in Eq. (47). Following the same routine the proof of Lemma F.9, establish that, for step sizes T+(1->)t+1)> with probability 27
1
K2 67 6T X
2I 11ē - - km
11Q - 20 @1xx <c (1--)M (1 (1- (1-2)3/2V1)
log
42

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
where e is large enough constant.
62 (
2g
Tog
730
By choosing M C2 I mo-
with sufficiently large 02, can ensure that the right-hand side is less than
(1-7)a
Observing that
11 - Q+1 S = 10 - -Qill = B2 + b;
we can conclude
Bi = 1 S - 2 - 5B2 + b,).
This establishes the desired bound on B,, completing the proof of Lemma F.14
F.18. Proof Lemma E.15
Proof. Our goal is bound the term B3 || 1o where Q the fixed point of the operator F defined as:
@ = F(²) - )())) - K(Q,) 7l+1(Q,,).
Recall that Q3 H(QW). Thus, Q can be viewed as the fixed point of Bellman operator with a perturbed reward function, where the perturbation magnitude is ((²))) + H (Q,) We seek to show that when the population size for estimating the reference Bellman operator is large enough, the term -H(Q))+ + converges to 0 and F converges the actual Bellman operator H. allowing || 20 < % Essentially, the error B2 comes from the reward function perturbation (Q,1(Q,))) H(Q,). In the first step, we bound the reward perturbation Ar -H(Q,) + (Q,)) as follows:
+ H(QZ) + 7.++(Q2)) -((Q,) Arl 77. (Q.)) 1((2)) - 17.+ +
$ 17++1 (Q,)
-(QL)) (7.++1(Q)) H(QL)I
< 2nl1Q, 10 (+++) -HQO))
The first terms can be directly bounded through Hoeffding's 's inequality. Similar to the proof of Lemma F.10, with probability at least 1
47
log(8T))\[ue(K [Uke(K / 2(11
2r11Q, 28 < 46
N,
The second term can bounded by applying the result of Eq. (70)² in Lemma F.11, we have that with probability least
1
- H(Q2) s (x ((1108) N, 77)
of log (og(8T) ( //01/0)
N,
where i a large enough constant.
Combining these conditions, derive that, with probability least 1
27
( / 1 (6,b T
log(ST)X(U 2(11/8)
Arl Se
(74)
N₂ 1)
N,
where e is a large enough constant.
TTe only difference is to applying the bound on the vector (Q.)(Q2)) H(QL)), instead of infinity norm.
43

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
Now we have already obtained the element-wise error bound of the reward function, which is the only difference for inducing Q and Q" Applying Lemma F.6 with Eq. (74), we have:
q Q I max {Ai, A2),
where
1 (8,1 + V log(87| { Z
log(8T (0(8TT(X(UA K_ 2x11/8)
[ k=
A cl -P-)
(75)
N- -)
Nr
(8g(88(125 x1 k=
Og( Kw k= , 2F11/0)
2 c(1 -1--PPp' -
11 (6,1 + +08
(76)
N₂ -7)
Nr
Bounding A1: For bounding A1, the key is to bound (I (/- ) -logg We have:
V2
[I(1 PP - 00l1o0 = - )-ao))-Vaaap Varp: (Vi))oo S
(77)
(1 71-
where the second inequality comes from Eq. (45) in Appendix F.6. By using I1(T - )P -1100 S 1-n
and Eq. (77), we
have:
( 211188)
V2
(og(STIA((U k=1 2z 21155))
A1 c
(1 7)2 1 (b', +
7) )
N₂
2" log(88) (U 2111/8)
2
XU Ke 2/11/8)
S cb'y
1,
(78)
(1
Nr
where the second inequality is obtained by using b, 2-
VI-
For bounding A2, the difference comes from bounding (1 - We define og as the variance of induced by Q function Q and policy #*. Then, we have:
Bounding A₁:
II(T- -P- -'oelll ||(T 7P--
(og -
og 0g +g)llo
11(I ) -ggll
|1(1 - a0)ll
3
11 - 0 lox
+
(79)
(1 - 7)
1 1-7
Combining Eq. (79) with Eq. (76), we have:
2" log((87 87 [u 2
2T+2
1og(8T|2((KK 2671188
Ag Sob,
1->1 V
Nr 7)
N
log (ug K- 2111/
cll 20
1.
(80)
(1-78 ,,
Combining Eq. (80) and (78), conclude that:
2 (8T X K.
k= |
2T+2
K. log(8T)
I 1--Qille lo sab',
k=
N₂ - 7
1 1-7
Nr
44

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
log(8T]A{ (
+ +cll Qulloo
(81)
(1 -1-78 7))
Using sample size N, c34"log
[6T] Kw [11) 7)- with large enough c3, can guarantee:
log (87) 1TT, k= x 21/1/
- 2
(82)
Nr
2 log( ( (1[
k=
Kw 2x.1188)
(83)
(1-7)
8'
4T+1 log(88)) (U
Kw
11))
k=
c
(1-7)2N,
(84)
Substituting condition (82)-(84) into Eq. (81) leads to 11 Qi1lo
6 4.
This concludes our proof.
G. Discussion on the Cost-Optimal Sampling Problem
G.1. Relating the Cost-Optimal Sampling Problem to Graph Coloring
The Graph Coloring Problem (GCP) is defined as follows: Given a graph G G= (V, E), where V is a set of vertices and is a set of edges, the task to assign color to each vertex such that no two adjacent vertices (i.e., vertices connected by an edge) share the same color. The objective to find the optimal coloring scheme that minimizes the number of colors used, known the chromatic number of the graph (Erdös & Hajnal, 1966).
In the Cost-Optimal Sampling Problem (COSP), components with scopes 2P,2f. 2f..... ZP must be divided into different groups, where the scopes of components in the same subset do not overlap (i.e., 2 n Z -0 for any i, j.j in the same group). This problem can be modeled variant of the GCP. Specifically, each component represents vertex in graph, and two vertices i and j are connected by an edge if their scopes overlap, i.e., 7.' n 2f * 0. Assigning color to a vertex corresponds to assigning the component to a group. Since components in the same subset must have disjoint scopes, no two connected vertices (representing components with overlapping scopes) can share the same color. The goal is to find a coloring scheme that minimizes the total costs across all groups, where the cost of each subset is determined by the scope with largest factor set space [x[z]"] in that group
G.2. Proof for NP-Completeness of the COSP
NP-completeness used to characterize a subset of problems that are computationally hard to solve. Famous NP-complete problems include the Traveling Salesman Problem (TSP) (Lin, 1965), the Knapsack Problem (Kellerer et al., 2004), the Hamiltonian Path Problem (Gary & Johnson, 1979), and the Satisfiability (SAT) Problem (Schaefer, 1978).
A problem is classified as NP-complete if it satisfies two conditions:
In NP: The problem belongs to the class NP, meaning that given a proposed solution, we can verify its feasibility in polynomial time.
Na-hard: The problem at least as hard as any other problem in NP. This means that any problem in NP can be transformed or reduced an NP-hard problem in polynomial time, then we could solve the NP-hard problem get the solution of any NP problem.
Graph coloring has been shown to be NP-complete (Karp, 2010), as it is computationally difficult to find the minimum number of colors for an arbitrary graph. We now show that the COSP is NP-complete by proving: (1) it belongs to NP, and (2) it least as hard as the NP-complete GCP.
45

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
G.2.1. THE COSP BELONGS TO NP
In the COSP, given a solution (a partition of components into groups and their associated costs), we can verify its feasibility in polynomial time by:
Verifying that the scopes within each subset are disjoint, which can be done by checking pairwise intersections within each group. This can be done in O + m)) time.
Calculating the total cost of a partition by identifying the largest scope size in each subset and summing these values, which can also be computed in polynomial time, specifically O(K)).
G.2.2. THE COSP IS NP-HARD
We prove NP-hardness by reducing the GCP to the COSP. We demonstrate that for any instance of the GCP, a corresponding instance of the COSP can be constructed, and based on the optimal solution of the COSP, we can derive the optimal solution to the GCP.
Given any instance of the GCP with a graph G = E), we construct a corresponding instance of the COSP as follows:
Step 1. Assign unique base dimensions for each vertex: Let [V] be the number of vertices, we initial [V] components with the scope for each component i E [[V]] satisfies 2," = {i). This ensures that each component starts with unique, non-overlapping dimension.
Step 2. Create shared dimensions for edges: For each edge (ni, U/) E E, we introduce a new and unique dimension di,j that will belong to both z!" and 2J". Specifically, we updates the scopes of components and j by
=2= zf= u (di.s.
This ensures that for every edge in the graph, the corresponding components have overlapping scopes, mimicking the adjacency constraint the GCP.
Step 3. Enforce disjointness for non-adjacent vertices: If there is no edge between two vertices v; and uj. the corresponding scopes should remain disjoint, i.e. Z n Zz = 0. This property is automatically maintained because shared dimensions are only introduced for pairs of vertices that are connected by an edge.
We provide an example to illustrate the construction process. Consider a small example graph G = (V, F) with three vertices V = {11, U2 3 and edges E' = {(11, (2), (12, vz)}. The construction process is:
Step I. Assign unique base dimensions for each vertex: Z = {1), ZJ = [2} and Z = [3].
Step 2. Create shared dimensions for edges: For edge (V1, 02). we introduce d1,2 = 4, so Z (1,4), =
Also, for edge (v2, va), we introduce d2,3 5. Zg8 (2, 4,,, Zi6 (3.5).
Step 3. Resulting scopes: the resulting scopes are:
-1,4, 2 = (2,4,5),
2 = (3,5).
The objective of the COSP is partition these components into disjoint groups (sets of components with no overlapping scopes) while minimizing the total sampling cost. Since the sampling cost for each component is set 1, minimizing the total sampling cost is equivalent minimizing the number of groups (colors) used, as each subset contributes I to the total cost. Therefore, solving the COSP on this constructed instance is equivalent to solving the GCP.
G.2.3. IP-COMPLETENESS
Since the GCP can be reduced to the COSP in polynomial time, and solving the COSP provides a solution to the GCP, the COSP NP-hard. Furthermore, since the COSP belongs to NP, it is NP-complete.
46

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
G.3. Computation Complexity
Intuitively, the SOSP involves grouping the factors of the MDP minimize the total sampling cost. While the problem may appear combinatorial, it is computationally efficient in our setting for two reasons: (1) the number of factors K is typically small (on the order of lo)(( (2) there exist established exact and approximate algorithms solve such problems efficiently.
Specifically, the problem can be formulated as an integer program of size O(K), solvable by modern solvers like Gurobi and CPLEX when K is moderate (c.g., K & 500). Furthermore, as discussed in calier subsections, it can be reduced to the classical weighted GCP, for which many scalable algorithms exist. In practice, even problems with thousands of nodes (e.g.. K- 5000) can be solved near-optimality within seconds (Shen et al., 2022; Dokeroglu & Sevinc, 2021).
H. Numerical Experiments
We now present numerical experiments to evaluate our proposed model-based and model-free algorithms based on approxi- mate factorization with comparisons to state-of-the-art RL algorithms. We focus on two types of tasks: (i) synthetic MDP tasks and (ii) an electricity storage control problem in power system operation.
H.1. Synthetic MDP Tasks
The two synthetic MDP tasks that we consider are distinguished by their transition kernels: one with a perfectly factorizable transition kernel and another with an imperfectly factorizable one. For the former task, we consider a thrce-dimensional state space, where each state is represented as (s[1], s +2)).{(3)) along with -ie-dimensional action a. The transitions for s[1] and s[2] are independent of other components, while s is influenced by both its state and the action a. Each substate and the action space consists of discrete elements. Both the transition kernel and the reward function are randomly generated. We conduct 50 trials to compare our model-based and model-free algorithms (VRQL-AF) with approximate factorization against traditional model-basee RL and variance-reduced Q-learnngg method without factorization. Figures. 3(a) and 3(b) illustrate the -norm of the Q-function error for both settings, respectively, as a function of the number of samples, As shown the two figures, our approximate factorization methods (depicted in red) consistently exhibit lower Q-function error across varying sample sizes compared the vanilla RL approaches (depicted in blue). This demonstrates that our approach significantly reduces sample complexity, showcasing superior sample efficiency. These findings underline the effectiveness of our factorization-bant based framework in enhancing learning efficiency for nulti-dimensional MDPs.
Vanilla Model-based
1.50
Q-Leaming with Variance Reduction
1.25
Model-based RL with AF
1.25
VRQL-AF
1.00
1.00
0.75
0.75
110
0.50
0.50
0.25
0.25
0.00
0.00
0.5
1.0
1.5
2.0
2.5
0.5
1.0
1.5
2.0
2.5
Number of Samples D2
le4
Number of Samples D2
1e4
(a) Model-based RL
(b) Model-free RL
Figure 3. Performance on Perfectly Factorizable MDPs
The second task involves MDPs with imperfectly factorizable transition kernels. Here, the state consists of substates, each taking one of 5 possible values. To investigate the trade-off between sample complexity and estimation error, evaluate three factorization schemes: (1) full factorization with K., 4, (2) partial factorization with K_, = 2, and (3) no factorization with (K., = 1). corresponding to vanilla RL. We conduct 200 trials to compare their performance with differrnnt sample amounts. As shown in Figure 4, our madel-based and model-free RL algorithms exhibit distinct convergence behaviors under these different factorization levels. The results indicate two key breaking points (D1, E and (D2, Eg) in performance trade-offs (illustrated Figure 4(b)), which inform the optimal factorization choice depending on the sample
47

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
-1.0
K,
K
-1.0
Ku =
K,
-1.5
Kg
-1.5
-2.0
-2.0
logilo
2.5
lagllo"
(D
-2.5
-3.0
-3.0
(D 82)
-3.5
0.00
0.25
1.00
1.50
2.0
Number Samples D,
le4
Number Samples D2
le4
(a) Model-based RL
(b) Model-free RL
Figure Performance on Imperfectly Factorizable MDPs
Required
Generated
Power
Power
Wt
Wt
D
Wr.
Power Supply
Vi
Power Grid
Wind Farm
V
Energy Storage System
Figure 5. Wind Farm Storage Control. (Adapted from (Lu et al., 2024))
availability. Specifically, in the small sample range with D, < D1, the full factorization scheme (K,, = 4) converges quickly but has a higher asymptotic error, making it suitable when the samples are limited or the required accuracy is not high. In the intermediate sample range with D1 < D, S D2, the partial factorization scheme (K. = 2) provides a balanced trade-off, achieving moderate convergence speed and a lower asymptotic error. This scheme advantageous when a compromise between sample efficiency and accuracy is needed. In the large sample range with D, D2, the no factorization scheme (Ka = results in the smallest asymptotic error but converges slowly. This approach is best suited when very high precision is required, and a large sample size is available. Therefore, it highlights the benefits of selecting an appropriate factorization level to match the sample size and desired accuracy. The flexibility in choosing among different factorization strategies enables the optimization of performance based on specific requirements, making our approach adaptable to various settings.
H.2. Wind Farm Storage Control Problem
We next evaluate the performance of our proposed approach on the wind farm storage control problem introduced in Section B. As depicted in Figure 5, this problem involves managing energy storage systems to mitigate mismatches between variable wind power generation and demand, thereby minimizing penalty costs.
The control actions consist of charging and discharging decisions influenced by real-time wind generation and unit penalty prices. Constraints include storage capacity limits, prohibiting simultaneous charging and discharging, and lossy energy dynamics. For detailed model description, please refer to Appendix I. The total state-action space size in this problem is 1
Figure illustrates the performance of our approach, where we decompose the MDP into three components as described carlier. Specifically, Figure 6(a) demonstrates that our approximate factorization based algorithm converges significantly faster than the vanilla mosel- approach by leveraging the model's 's structural properties. Additionally, our method
48

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
lc2
1e4
Vanilla Model-based RL
Vanilla Model-based RL.
2.5
Model-based RL with AF
Model-based with AF
2.0
Cost (S)
1.5
1.0
0.5
0.0
0.0
0.2
0.4
0.6
0.8
1.0
500
1000
1500
2000
2500
3000
Number of Samples
1e7
Time Slot
(a) Convergence Q-function Estimation
(b) Economic Performance
Figure 6. Performance on Storage Control
exhibits considerably lower variance, indicating stable performance for different sample conditions. Figure 6(b) presents the economic benefits of our algorithm using sample size of 60,000 data points (typically taking the wind farm year to collect), evaluating cumulative system penalty costs over 3,000 time slots. The results show that our approach reduces costs by 19.3% compared to the vanilla model-based method, highlighting its enhanced effectiveness in managing complex problems with large-scale state spaces.
I. Detailed Model of Wind Farm-equipped Storage Control
L1. System Model
Consider a wind farm tasked with supplying power the grid under electricity supply contract. The predetermined supply quantity of wind power at any given time / is denoted by o; This value is established based on wind power forecasts, which can be made from a minute to day in advance, either by the wind farm itself or the Independent System Operator (ISO). As time progresses, the actual wind power generation is sequentially disclosed in real-time. The wind farm is equipped with a storage system, allowing it to either store wind energy, denoted as u,"" or release stored energy, denoted as Uy into the grid at any time t. As a result, the total power delivered to the grid, represented by gt, is determined by
gt Wit
+ U2
When the mismatch exists between commitment W, and the delivered power gr. the wind farm will be charged with a penalty cost (e gt) as follows:
(w gt) - pt max wr 0) + Pt max(@, 9t, 0),
where p and p, denote the unit penalty costs for wind generation surplus and shortage at time t, respectively.
The wind farm targets minimize the accumulated mismatch penalty costs across all T time slots by reasonably controling the storage system. Mathematically, the storage control problem can be formulated as follows:
Σ
(P1)
min
1== Ce( ce(Werge))
(85)
Ve
8.1. = wt + 1i - rrt Vl.
(86)
C
SoC1 2'
(87)
SoC = SoC, + + vtt oo VI,
(88)
11" rt < <C- - -SoCi, VI,
(89)
11 "6 S SoCr, VI.
(90)
1/ S u/, Vt,
(91)
49

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
1/ 1/2 0, V4,
(92)
1/2 1 = 0, V7.
(93)
In the optimization, the decision variables at time include:
et: generated wind power which is charged to the energy storage;
of discharged energy from the storage to the grid;
And the other functions, latent variables, and parameters include:
c+()): total penalty cost at time
: committed wind power supply time t;
wyt wind power generation at time
T: total duration of storage control decisions;
p p unit grid penalty prices for power generation shortage and surplus at time t, respectively;
Ge: actual supplied energy at time t;
SoC₁: state-of-charge (SOC) of storage at time t;
C: energy storage capacity;
n -
charging and discharging efficiencies of storage;
Constraint (86) represents the delivered power, constraints (87) and (88) characterize the dynamics of storage; and constraints (89) and (90) denote the storage capacity limits. Constraint (91) and (92) show the upper and lower limits storage control actions, and constraint (93) indicates that the storage cannot be charged and discharged simultaneously.
Due to the inherent stochasticity of penalty prices and renewable energy production, impractical to obtain the optimal future storage control decisions. Therefore, in practice, often consider sequential storage control. Specifically, each time we determine the current storage control actions v U/ based on the currently available information. Consequently, we establish the following online storage control problem at time t as follows:
(P2)
min 0
a (w,, 9t) +
Σ
x -- TTc (wr,
(94)
r=1+1
s.t.
== w/ + 1i vttt
(95)
SoC.+1 SoCC + 1j " utt - 1i
(96)
" rt S C C-Sod C-SoCr:
(97)
" r S SoCte
(98)
of S wt.
(99)
v v, 2
(100)
or v 0.
(101)
L.2. Markoy Decision Process Modeling
We highlight that problem (P2) can be transformed into MDP in the following manner: Markoy Decision Process (S, P,, R.):
50

---

Overcoming the Curse of Dimensionality in Reinforcement Learning via Approximate Factorization
States S: Any state E S is composed of the penalty prices p² _p" the committed and real wind power generation w and w, and state-of-charge SoC. Formally, (x²t, ,p", .P, w. w, SoC);
Actions A: Any action a E A is composed the charge amount vt and discharge amount VT Formally, a = (vit, v
Transition probability P: P is the transiting probability matrix P. (Pr(s141 = 8'1st 8, 04 = a), Vs, 8' E E E A). which includes the probability of transiting from state s to s' with action a for all s' and o;
Reward R: R is the immediate reward (penalty in our case) after transiting from state s to state s' due to action a, i.c.
R = (r(s, a), Vs, a). Specifically, in the one-shot decision problem, the penalty r(s, a) equals the negative of the penalty, i.e.,
r(s,a) pp max(w w1 0) + p max 1 w. W,O).
We can observe that, for the storage control problem, the state space S and the action space A are known. The reward R is also known once the state s and action a are decided. The only unknown comes from the transition probability P. However, some important observations for P can simplify the problem. Specifically, we can divide the state variables (p+ p W. w, SoC) into one deterministic state and several random states. The deterministic state is SoC, which can be determined following Eq. (96) without any uncertainty. And the random states include pt pT W. w, which are fully random'.
In our numerical study, we assume p* = and observe that only A = w exists in the reward function. Therefore, the state can be rewritten as S (p, Aw, SoC). For the factorization scheme w, we use the following factorization the transition kernel:
P(pe41,A411 SoC Pe, A., SoC,, a:) Pror
I.3. Parameter Settings
In the numerical study, we utilized the California aggregate wind power generation dataset from CAISO (California ISO, 2021) containing predicted and real wind power generation data with a 5-minute resolution spanning from January 2020 to December 2020. The penalty price equals the average electricity price of CASIO (California ISO, 2021) with the matching resolution and periods. We set C' 500 kWh, 7 0.9. The discretization levels of Aw and SoC are set to be 8, 8, 50, respectively. The action set includes 3 discretized choices: charging (discharging) to satisfy 100%, 50%, and 0% of energy mismatches, respectively.
'Note that, the committed wind power & is essentially not random. However, only the generation mismatch w @ exists in problem, and such mismatch can regarded as a random variable.
51


Reviews:
[{"review_id": "EF1bUHjqJd", "reviewer": "Reviewer_TcCo", "summary": "This paper studied factorized Markov Decision Processes (MDPs) and proposed two algorithms based on a newly developed synchronous sampling methods. This method efficiently sample and estimate different component of the transitions and therefore help the algorithm to achieve less sample complexity in both model-based and model-free approach. This paper also characterize the effect of imperfect modeling, when the MDP is an approximated factorized MDP.", "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": "We would like to thank the reviewer for acknowledging our novelty and contributions and providing insightful feedback. Below, we provide detailed responses to address the reviewer's comments.\n\n**Q1: The experiments in Appendix are generally sound and valid. One potential issue is the lack of comparison to a policy-based method such as policy gradient.**\n\nThank the reviewer for acknowledging the soundlessness of our experiments. Since our work mainly focuses on leveraging approximate factorizable structures to design customized value-based algorithms, we primarily compare against the same types of value-based baselines. That being said, the proposed algorithmic framework can also be used to solve the policy evaluation subproblem (which is based on solving Bellman equations) within an actor-critic framework. This can be combined with policy gradient methods (i.e., the actor) to develop efficient policy-based algorithms that leverage the approximate factorization structure. We leave providing theoretical guarantees and conducting numerical simulations in this direction as future work.\n\n**Q2: The cost-optimal sampling problem might be hard to solve.**\n\nThank the reviewer for raising this point. Intuitively, the cost-optimal sampling problem involves grouping the $K$ factors of the MDP to minimize the total sampling cost. While the problem may appear combinatorial, it is computationally efficient in our setting for two reasons: (1) the number of factors $K$ is typically small (on the order of $\\log(|\\mathcal{S}||\\mathcal{A}|)$, where $|\\mathcal{S}||\\mathcal{A}|$ is the state-action space size), (2) there exist established exact and approximate algorithms to solve such problems efficiently.\n\n\nSpecifically, the problem can be formulated as an integer program of size $\\mathcal{O}(K)$, solvable by modern solvers like Gurobi and CPLEX when $K$ is moderate (e.g., $K\\leq 500$). Furthermore, as discussed in Appendix H, it can be reduced to the classical weighted graph coloring problem, for which many scalable algorithms exist. In practice, even problems with thousands of nodes (e.g., $K=5000$) can be solved to near-optimality within seconds [2–4].\n\nTo address the reviewer's concern, we will include a more detailed discussion in the revised version.\n\n>[1] Chen, X., Hu, J., Li, L., & Wang, L. Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL. In International Conference on Learning Representations. (2021) \n\n>[2]  Shen, Y., Sun, Y., Li, X., Eberhard, A., & Ernst, A. (2022, June). Enhancing column generation by a machine-learning-based pricing heuristic for graph coloring. In Proceedings of the AAAI conference on artificial intelligence (Vol. 36, No. 9, pp. 9926-9934).\n\n>[3] Saeed, A., Husnain, A., Zahoor, A., & Gondal, R. M. (2024). A comparative study of cat swarm algorithm for graph coloring problem: Convergence analysis and performance evaluation. International Journal of Innovative Research in Computer Science and Technology (IJIRCST), 12(4), 1-9.\n\n>[4] Dokeroglu, T., & Sevinc, E. (2021). Memetic Teaching–Learning-Based Optimization algorithms for large graph coloring problems. Engineering Applications of Artificial Intelligence, 102, 104282.\n\n**Q3: This paper studied tabular RL, where the state and action space are finite. Is it possible to consider infinite state space? Because it is most likely the case in real-world applications.**\n\n\nWe thank the reviewer for their question. While our work focuses on the tabular setting to enable a clear theoretical understanding, we believe it can potentially be extended to MDPs with infinite (or continuous) state spaces. Specifically, the core structural insight—factored transition kernels—can naturally extend to continuous domains. For example, a discrete factorization $P(s'_1, s'_2 \\mid s_1, s_2) = P(s'_1 \\mid s_1) P(s'_2 \\mid s_2)$ can be analogously expressed in terms of transition densities as $f(s'_1, s'_2 \\mid s_1, s_2) = f(s'_1 \\mid s_1) f(s'_2 \\mid s_2)$ in the continuous case. However, working with MDPs with infinite (or continuous) state spaces presents other challenges, such as the potential unboundedness of the reward function (e.g., in the LQR setting in control). In addition, certain parameterizations (i.e., function approximation) might be required to ensure that Q-functions are updated infinitely often for each state-action pair. We view this as a promising direction for future work.", "claims_and_evidence": "Yes. The claims are generally well-supported by the analysis and results.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not fully check the proof, but it seems correct to me based on the main paper.", "experimental_designs_or_analyses": "The experiments in appendix are generally sound and valid. One potential issue is the lack of comparison to a policy-based method such as policy gradient.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength: the synchronize sampling method seems interesting and novel.\n\nWeaknesses:  The cost-optimal sampling problem might be hard to solve.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "This paper studied tabular RL, where the state and action space are finite. Is it possible to consider infinite state space? Because it is most likely the case in real-world applications.", "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": "7r18L3LklV", "reviewer": "Reviewer_Curw", "summary": "The authors study Factored Markov Decision Processes (FMDPs). They extend this framework in significant ways and amend several of its shortcomings. For example, they develop a model-based RL algorithm achieving the first near-minimax sample complexity for FMDPs.", "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": "We would like to thank the reviewer for acknowledging the contributions of our work and providing insightful feedback! Below, we provide detailed responses to the reviewer's questions.\n\n**Q1: Please add some discussion on the discount factor $\\gamma$.**\n\nIn the discounted setting (which is standard in MDPs and reinforcement learning), the discount factor $\\gamma \\in [0, 1)$ determines how much weight the agent places on immediate versus future rewards. Smaller values prioritize short-term gains, while larger values emphasize long-term planning. We will include a more detailed discussion in the next version.\n\n**Q2: Should $s$ appear in the RHS of Equation (1)?**\n\nThe current state $s$ is present on the right-hand side through the variable $x=(s,a)$, which denotes the state-action pair.\n\n**Q3: Can you please elaborate on the definition captured in Equation (6)?**\n\nThank you for your constructive comment. Eq.(6) defines the **joint sampling set** used to simultaneously sample transitions for two factors $k_1$ and $k_2$, whose scopes are $Z_{k_1}$ and $Z_{k_2}$, respectively.\nHere, $x[Z_{k_1}^P]$ and $x[Z_{k_2}^P]$ enumerate the relevant input dimensions (by sampling from these dimensions, we can estimate the respective transitions of factors) for the two factors, $x^{\\text{default}}[- (Z_{k_1}^P\\cup Z_{k_2}^P)]$ assigns fixed default values for all the other irrelevant dimensions. The modulo operation ensures that the sampling cycles through all possible values within each relevant scope, and $D_{\\max} = \\max(|\\mathcal{X}[Z_{k_1}^P]|,|\\mathcal{X}[Z_{k_2}^P]|)$ ensures full coverage of both factors' input spaces. This construction enables compact and efficient joint sampling, allowing shared samples to be reused across different factors.\n\n**Q4: Can you please elaborate on $\\kappa_p\\ll K_\\omega$?**\n\nAs discussed in Sections 4.1, 5.2, and Appendix H, the relationship $\\kappa_p \\ll K_\\omega$ arises from the graph coloring perspective. We construct an undirected graph with $K_\\omega$ nodes—one per factor—and edges between dependent factors. The **chromatic number** $\\kappa_p$ is the minimum number of colors needed so that no adjacent nodes share a color, enabling efficient sampling in our setting.\n\n\nIntuitively, $\\kappa_p$ can be much smaller than $K_\\omega$, especially when the graph is sparse. For example, in a star graph with one central node connected to $K_\\omega-1$ outer nodes (which are not connected to each other), only two colors are needed: one for the center and another shared by all outer nodes. Thus, $\\kappa_p=2\\ll K_\\omega$. In practice, many FMDPs exhibit sparse interaction structures among factors, leading to graphs with low chromatic numbers. Therefore, in such settings, it is common that $\\kappa_p\\ll K_\\omega$ and even $\\kappa_p= \\mathcal{O}(1)$.\n\n**Q5: What is the main take-away from Equation (9)?**\n\nThe key takeaway is that our algorithm significantly reduces the sample complexity depending on the size of the state-action space. Specifically, our dependence is $\\sum_{k \\in [\\kappa_p]} |\\mathcal{X}[Z^P_k]|$. \n1. Compared with classical MDPs with dependence $|\\mathcal{S}||\\mathcal{A}|$, ours is much smaller because $|\\mathcal{X}[Z^P_k]|$ is the state-action space size of a single factor, which is exponentially smaller than $|\\mathcal{S}||\\mathcal{A}|$. \n2. Compared with SOTA FMDP results, which is $\\sum_{k \\in [K_\\omega]} |\\mathcal{X}[Z^P_k]|$, ours is also much smaller because we have shown $\\kappa_p\\ll K_\\omega$ before. \n3. We show that when $\\kappa_p= \\mathcal{O}(1)$, our result is minimax optimal.\n\n\n**Q6: Algorithm 3: How can we efficiently implement step 7? Not sure if Equation (10) is efficient?**\n\nThank you for the comment. Equation (10) provides a formal and rigorous definition of the empirical factored Bellman operator used in Step 7 of Algorithm 4. While the notation may seem complex, the implementation is efficient in practice.\n\nDue to the synchronous sampling design, a single sample can be reused to estimate transitions for multiple factors. Equation (10) simply extracts the relevant dimensions from each sample to update the corresponding factors. This makes the implementation straightforward and efficient.\n\nWe will include more discussions in the next version.\n\n\n\n**Q7: The parameters in Theorem 6.1 are a bit confusing :)**\n\nThank you for the comment. The parameters in Theorem 6.1 correspond to key configuration choices in the VRQL-AF algorithm, including the number of epochs, epoch length, learning rate, and others. We agree that their roles could be explained more clearly and will revise the theorem statement and surrounding text to improve clarity in the next version.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, to some extent.", "experimental_designs_or_analyses": "Yes, to some extent.", "relation_to_broader_scientific_literature": "The authors study Factored Markov Decision Processes (FMDPs). They extend this framework in significant ways and amend several of its shortcomings.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "None.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Page 2:\nPlease add some discussion on the discount factor $\\gamma$.\n\nPage 3:\nShould $s$ appear in the RHS of Equation (1)?\n\nPage 4:\nCan you please elaborate on the definition captured in Equation (6)?\n\nPage 5:\nCan you please elaborate on $\\kappa_p \\ll K_\\omega$?\n\nPage 6:\nWhat is the main take-away from Equation (9)?\n\nPage 7:\nAlgorithm 3:\nHow can we efficiently implement step 7?\nNot sure if Equation (10) is efficient?\n\nPage 8:\nThe parameters in Theorem 6.1 are a bit confusing :)", "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": "eh3t0pXUev", "reviewer": "Reviewer_rEVy", "summary": "This paper studied one key challenge of RL: curse of dimensionality related to high-dimensional state-action spaces. To address the challenges, the authors introduce approximate factorization, which extends the Factored Markov Decision Process (FMDP) framework to the imperfect misspecification case. Under a generative model, this paper studies both model-based and model-free RL algorithm and provide sample complexity bound.", "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": "We thank the reviewer for their thoughtful questions. Below, we provide point-by-point responses to the reviewer's comments.\n\n**Q1: About the claim of \" limited extensions to non-linear methods, such as neural networks, which typically rely on specific assumptions (Fan et al., 2020; Xu & Gu, 2020).\" There exists a line of research studied non-linear low-rank mdps proposed by [1], the extensions are not so \"limited\".**\n\nWe agree with the reviewer that there are some non-linear methods with different assumptions. In light of this, we will remove the term “limited” and include additional relevant references in the revised version.\n\n**Q2: This paper does not provide experiments to validate their theoretical results.**\n\nDue to space limitations, we included our experimental results in Appendices I and J (pages 46–50), which include a synthetic MDP and a real-world electricity storage task. These results demonstrate improved sample efficiency and validate our theoretical findings. We will highlight them more clearly in the main text in the next version, as suggested.\n\n**Q3: I think the biggest limitation for this paper is the assumption of generative models, which doesn't reflect the real data collection process of RL under mdps.**\n\nThank you for raising this point.\n\nThe generative model is a widely used and fundamental setting in the RL literature. It is particularly practical for applications with high-fidelity simulators (e.g., robotics). This setting is often the first step—prior to tackling more complex settings such as trajectory-based sampling—in developing a theoretical understanding of an algorithm’s behavior [1–3]. Even in this setting, the non-asymptotic analysis of (approximately) factored MDPs remains heavily understudied. Since we are the first to extend factorizability, establish model-free algorithms, and improve sample complexity guarantees for factored MDPs, we focus on the generative model setting in this work.\n\nThat being said, we believe our algorithm and theoretical results can potentially be extended to the Markovian sampling setting. Specifically, as long as the behavior policy induces a uniformly ergodic Markov chain, the algorithm should work since each substate-subaction pair is sampled infinitely often along the trajectory. Recent techniques (e.g., [4]), based on mixing times and conditioning, also provide tools to convert generative-model bounds into trajectory-based bounds. Rigorously studying this extension is a promising direction for future work.\n\n>[1] A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Machine Learning, 2002. \n\n>[2] On the Sample Complexity of Reinforcement Learning with a Generative Model. ICML 2012.\n\n>[3] Sample-efficient reinforcement learning for linearly-parameterized mdps with a generative model. NeurIPS 2021.\n\n>[4] Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. NeurIPS 2020.\n\n**Q4: This paper claims \"sample from the substate-subaction spaces\". Such a sampling is even more unnatural.**\n\nWe appreciate the reviewer’s concern. We do not assume direct access to substate-subaction transitions. Instead, we sample full transitions and then extract the components for specific dimensions, which is standard in factored MDPs.\n\nFor example, in an electricity storage control problem with state $s=(s_1,s_2)$ where $s_1$ is the storage level and $s_2$ is the electricity price. The price $s_2$ is typically externally generated, observable, and unaffected by the system's actions. Therefore, we can estimate $P(s'_2|s_2)$ from full transition samples $(s_1,s_2,a,s'_1,s'_2)$. We will clarify this in the revised version.\n\n**Q5: $P_k$ used in line 136 and line 159 are with different shapes.**\n\nThank you for pointing this out. We acknowledge the slight abuse of notation. We will revise the usage of $P_k$ in line 136 to make it consistent throughout the paper.\n\n**Q6: Why do you need to define the set of feasible marginal transition probabilities? And what are its properties at a high level?**\n\nThank you for the question. At a high level, we introduce this feasible set to capture how factorization error may arise when full transitions are aggregated into factor-level marginals when the MDP is not perfectly factorizable. It thus bounds the possible deviations from perfect factorization for error definition, which is crucial for the theoretical analysis and doesn't influence algorithm design.\n\nFor instance, for an MDP with state $s=(s_1,s_2)$ and action $a$, we aim to estimate the transition $P(s'_1 |s_1,a)$ of a factor. What we actually observe is $P(s'_1 |s_1,s_2,a)$ (because we need to sample from a full state-action pair). This is consistent across all $s_2$ in the perfectly factored case, but in the approximate case, different $s_2$ may introduce biases. The feasible set captures this variability and is used to define the factorization error. We will add more discussions in the revised version.", "claims_and_evidence": "In introduction (line 52), this paper claims that \" limited extensions to non-linear methods, such as neural networks, which\ntypically rely on specific assumptions (Fan et al., 2020; Xu & Gu, 2020).\" However, their are also a line of researches studied non-linear low-rank mdps proposed by [1], the extensions are not so \"limited\", I think the authors should do more literature reviews.\n\n[1] FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs.", "methods_and_evaluation_criteria": "The evaluation criteria sample complexity is standard for RL problem.", "theoretical_claims": "I didn't check the proof in detail.", "experimental_designs_or_analyses": "This paper does not provide experiments.", "relation_to_broader_scientific_literature": "This paper is related to function approximation in RL to deal with curse of dimensionality. However, the assumption of generative model makes it quite limited.", "essential_references_not_discussed": "Many other papers tried to deal with curse of dimensionality by function approximation including both linear and non-linear approximation (like I state in Claims And Evidence*), I think the authors should also provide a discussion on these papers.", "other_strengths_and_weaknesses": "I think the biggest limitation for this paper is the assumption of generative models, which does reflect the real data collection process of RL under mdps. \n\nMoreover, in line 200, this paper claims \"In this case, instead of sampling from the global state-action space, we only need to sample from the substate-subaction spaces, which reduces the sample complexity\". Such a sampling is even more unnatural.\n\nFinally, this paper does not provide experiment to validate their theoretical results.", "other_comments_or_suggestions": "line 136, right column, $P_k(s'[Z_k^S]|x)\\in \\mathbb{R}^{|\\mathcal{X}|\\times|\\mathcal{S}[Z_k^S]|}$, in the defintion of the set of feasible marginal transition probabilities (line 159 left column), $P_k$ is defined to be in $\\mathbb{R}^{|\\mathcal{X}[Z^P_k]|\\times|\\mathcal{S}[Z_k^S]|}$.", "questions_for_authors": "line 136, right column, why do you need to define the set of feasible marginal transition probabilities as this set? And can you explain in high level what kind of properties does this set have?", "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": "Z4GmD2Gkhq", "reviewer": "Reviewer_xjwC", "summary": "After rebuttal: Thanks for addressing my questions! I'll keep my rating.\n\n===\n\nThis paper considers FMDP and provides a powerful framework to tackle the curse of dimensionality in reinforcement learning (RL) by breaking down high-dimensional MDPs into smaller, independently evolving components, i.e., using factored MDP.\n\nTis paper introduces approximate factorization, which extends FMDPs to handle imperfectly factored models. Additionally, a graph-coloring-based optimal synchronous sampling strategy is proposed to enhance sample efficiency.\n\nA model-based and the first model-free variance-reduced Q-L algorithm for FMDP are proposed and their theoretical guarantees are shown. They both outcompete the STOA.\n\nNumerical results are provided in the appendix.", "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": "We thank the reviewer for the insightful feedback and greatly appreciate the recognition of our work's novelty and contributions! Below, we provide point-by-point responses to the questions.\n\n**Q1: It might be helpful to include a proof sketch to summarize the main techniques and novelty of the proof in the main text.**\n\n\nThank you for your constructive suggestion! We will include a \"Proof Sketch\" section in the revised version to highlight the key ideas and techniques behind our results.\n\n* **Sample Complexity of Model-based Method**.\nThe main challenge lies in handling statistical correlations introduced by factorized sampling when estimating the finite-sample errors. The analysis relies on cross-component correlation control and variance analysis with customized Bernstein concentration bounds (e.g., Lemma B.2 and B.3-B.5).\n\n* **Sample Complexity of Model-free VRQL-AF**.\nThe additional challenges for this algorithm come from the additional correlation during the two-timescale variance-reduced updates. Our improvement builds on the tailored factored empirical Bellman operator for approximately factorized MDPs, combined with a variance-reduction approach to minimize the variance of the stochastic iterative algorithm. The key idea is to show that this operator retains the non-asymptotic behavior of the standard one while achieving greater sample efficiency.\nWe develop a refined statistical analysis to tightly control estimation errors and iteration variance across multiple factored components (e.g., Lemmas G.2, G.3, G.6, G.8, G.9).\n\n**Q2: Can the algorithm be extended to the case where factorization is unknown?**\n\nThank you for the question. Yes, our algorithm works with any given factorization, even if it is not perfectly aligned with the true MDP. For each factorization, our analysis provides the corresponding sample complexity and bias guarantees. While the bias is typically unknown, the algorithm remains valid regardless.\n\nIn practice—especially in FMDPs or approximately factored MDPs—domain knowledge often reveals strong and weak dependencies (e.g., Appendix B), which enables the choice of factorizations that balance sample efficiency and bias. We will clarify this in the revised version.\n\n**Q3: Does the algorithm require factorization bias term Delta as an input? If so, is it possible to generalize to the unknown bias case?**\n\nThank you for the question. The algorithm does not require $\\Delta$ as an input. While our analysis quantifies how performance depends on the factorization bias, the algorithm itself runs without access to knowing $\\Delta$, and is fully applicable in the unknown bias case.\n\n\n\n**Q4: Can you comment on the computation complexity of the algorithms? Appendix H might be related, but it is still unclear to me.**\n\nThis is a great point. Our algorithm consists of two components: computing the cost-optimal sampling policy and executing the RL procedure. The RL component follows standard implementation, while the cost-optimal sampling problem is discussed in more detail in Appendix H.\n\nSolving the optimal sampling policy, though combinatorial in nature, is computationally efficient for two reasons: (1) the number of factors $K$ is typically small--on the order of $\\log(|\\mathcal{S}||\\mathcal{A}|)$, and (2) it can be solved efficiently using modern integer programming solvers (e.g., Gurobi, CPLEX) or established approximate algorithms.\n\n\nIn particular, the problem reduces to a standard weighted graph coloring formulation of size $\\mathcal{O}(K)$, with a lot of established solutions[1–2] that can solve near-optimal solutions within seconds even $K$ is very large (e.g., $K=5000$).\n\n>[1] Shen, Y., Sun, Y., Li, X., Eberhard, A., & Ernst, A. (2022, June). Enhancing column generation by a machine-learning-based pricing heuristic for graph coloring. AAAI.\n\n>[2] Dokeroglu, T., & Sevinc, E. (2021). Memetic Teaching–Learning-Based Optimization algorithms for large graph coloring problems. EAAI.\n\n\n\n\n\n**Q5: The variance reduction method appears to rely on the reference function. Have you considered variance-dependent bounds, similar to those in [1]?**\n\nThis is a great point. The variance-dependent bounds aim to express regret or sample complexity in terms of the instance-dependent variance of the value function[1–2]. Adapting these ideas to our setting may involve incorporating variance-related quantities into the algorithm's step-wise parameters, and avoiding the standard worst-case scaling of $V$ and $Var(V)$ as $1/(1-\\gamma)$ and $1/(1-\\gamma)^2$. We agree this is a promising direction for future work.\n\n\n>[1] Zhao, Heyang, et al. \"Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency.\" COLT (2023).\n\n>[2] Yin, Ming, and Yu-Xiang Wang. \"Towards instance-optimal offline reinforcement learning with pessimism.\" NeurIPS (2021).", "claims_and_evidence": "Yes they are", "methods_and_evaluation_criteria": "Yes they do.", "theoretical_claims": "The theoretical bounds for model-based algorithms look good to me.\n\nThe theoretical bounds for model-free algorithms look good to me.", "experimental_designs_or_analyses": "Numerical results are included in the appendix. Synthetic MDP tasks and an electricity storage control problem are considered and the STOA algorithms are compared.", "relation_to_broader_scientific_literature": "Many real-world applications feature structured transition probabilities and reward functions that can reduces the sample complexity of high-dimensional MDPs.\n\nFor example, robotic control problems can be effectively modeled using the factored MDP (FMDP) framework.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "The results are solid.\n\nBoth model-free and model-based methods are proposed.\n\nResults improve the state of the art bounds. \n\nDetailed comparison with the exact factorization case and the comparison of looseness of the bounds are discussed in the paper.", "other_comments_or_suggestions": "It might be helpful to include a proof sketch to summarize the main techniques and novelty of the proof in the main text.\n\nCan the algorithm be extended to the case where factorization is unknown?\n\nDoes the algorithm require factorization bias term Delta as an input? If so, is it possible to generalize to the unknown bias case?\n\nCan you comment on the computation complexity of the algorithms? Appendix H might be related, but it is still unclear to me.", "questions_for_authors": "The variance reduction method appears to rely on the reference function. Have you considered variance-dependent bounds, similar to those in Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency?", "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 presents a theoretical contribution to reinforcement learning in Factored Markov Decision Processes (FMDPs), introducing novel techniques aimed at improving sample efficiency and applicability. Reviewers recognized several key strengths: the development of an innovative synchronous sampling method, the formalization and handling of approximate factorizations (addressing model misspecification), and the derivation of strong theoretical results. The paper provides sample complexity bounds for both model-based and model-free algorithms (including variance reduction) that demonstrably improve upon state-of-the-art guarantees, with near-minimax rates achieved in the model-based setting. However, some weaknesses and concerns were also raised. The reliance on a generative model was noted as a potential limitation regarding practical RL scenarios by one reviewer. Another pointed out the absence of experimental validation within the main paper (though numerical results are in the appendix) and suggested a potentially incomplete discussion of related function approximation literature. Questions regarding the practical implementation (e.g., solving the sampling problem, computational complexity) and potential extensions (e.g., continuous spaces, unknown factorization) were also brought up. Despite these concerns, the overall sentiment is positive, leaning towards acceptance (2 Accepts, 2 Weak Accepts), based on the significance and solidity of the theoretical advancements for FMDPs.
Decision: Accept (poster)