Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization

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.

Q1: It might be helpful to include a proof sketch to summarize the main techniques and novelty of the proof in the main text.

Thank 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.

• Sample Complexity of Model-based Method. The 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).

• Sample Complexity of Model-free VRQL-AF. The 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. We 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).

Q2: Can the algorithm be extended to the case where factorization is unknown?

Thank 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.

In 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.

Q3: Does the algorithm require factorization bias term Delta as an input? If so, is it possible to generalize to the unknown bias case?

Thank 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.

Q4: Can you comment on the computation complexity of the algorithms? Appendix H might be related, but it is still unclear to me.

This 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.

Solving 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.

In 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$).

[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.

[2] Dokeroglu, T., & Sevinc, E. (2021). Memetic Teaching–Learning-Based Optimization algorithms for large graph coloring problems. EAAI.

Q5: The variance reduction method appears to rely on the reference function. Have you considered variance-dependent bounds, similar to those in [1]?

This 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.

[1] Zhao, Heyang, et al. "Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency." COLT (2023).

[2] Yin, Ming, and Yu-Xiang Wang. "Towards instance-optimal offline reinforcement learning with pessimism." NeurIPS (2021).

We thank the reviewer for their thoughtful questions. Below, we provide point-by-point responses to the reviewer's comments.

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".

We 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.

Q2: This paper does not provide experiments to validate their theoretical results.

Due 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.

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.

Thank you for raising this point.

The 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.

That 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.

[1] A sparse sampling algorithm for near-optimal planning in large Markov decision processes. Machine Learning, 2002.

[2] On the Sample Complexity of Reinforcement Learning with a Generative Model. ICML 2012.

[3] Sample-efficient reinforcement learning for linearly-parameterized mdps with a generative model. NeurIPS 2021.

[4] Sample complexity of asynchronous Q-learning: Sharper analysis and variance reduction. NeurIPS 2020.

Q4: This paper claims "sample from the substate-subaction spaces". Such a sampling is even more unnatural.

We 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.

For 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.

Q5: $P_k$ used in line 136 and line 159 are with different shapes.

Thank 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.

Q6: Why do you need to define the set of feasible marginal transition probabilities? And what are its properties at a high level?

Thank 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.

For 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.

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.

Q1: Please add some discussion on the discount factor $\gamma$.

In 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.

Q2: Should $s$ appear in the RHS of Equation (1)?

The current state $s$ is present on the right-hand side through the variable $x=(s,a)$, which denotes the state-action pair.

Q3: Can you please elaborate on the definition captured in Equation (6)?

Thank 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. Here, $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.

Q4: Can you please elaborate on $\kappa_p\ll K_\omega$?

As 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.

Intuitively, $\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)$.

Q5: What is the main take-away from Equation (9)?

The 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]|$.

1. 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}|$.
2. 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.
3. We show that when $\kappa_p= \mathcal{O}(1)$, our result is minimax optimal.

Q6: Algorithm 3: How can we efficiently implement step 7? Not sure if Equation (10) is efficient?

Thank 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.

Due 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.

We will include more discussions in the next version.

Q7: The parameters in Theorem 6.1 are a bit confusing :)

Thank 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.

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.

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.

Thank 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.

Q2: The cost-optimal sampling problem might be hard to solve.

Thank 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.

Specifically, 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].

To address the reviewer's concern, we will include a more detailed discussion in the revised version.

[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)

[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).

[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.

[4] Dokeroglu, T., & Sevinc, E. (2021). Memetic Teaching–Learning-Based Optimization algorithms for large graph coloring problems. Engineering Applications of Artificial Intelligence, 102, 104282.

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.

We 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.