acceptodds
Under review as a conference paper at ICLR 2027

Near-Optimal PAC Learning for Low-rank MDPs

Abstract

Low-rank Markov decision processes (MDPs) provide a general framework for reinforcement learning in large or continuous state spaces with unknown representations. However, whether near-optimal sample complexity can be achieved using only a maximum-likelihood estimation (MLE) oracle and polynomial additional computation remains unclear. In this work, we resolve this question for probably approximately correct (PAC) learning with known per-step rewards in . We propose an uncertainty marking algorithm for both time-homogeneous and time-inhomogeneous MDPs. Its exploration bonus controls the model error over a whole trajectory using the probability of at least one uncertainty mark. The algorithm uses MLE as its only optimization oracle, with bonus estimation and optimistic planning implemented in polynomial time using fitted-model evaluations and samples. We show that, with probability at least , our algorithm returns an -optimal policy using episodes in the homogeneous setting and episodes in the inhomogeneous setting, where is the horizon, is the rank, is the number of actions, and is the common finite realizable kernel class with . Moreover, we establish lower bounds that match these rates up to logarithmic factors, showing that our algorithm achieves near-optimal PAC sample complexity in both settings. Finally, we validate our algorithm through experiments on homogeneous block MDPs.

Primary area:
reinforcement learning
Keywords:
RL, Low-rank MDPs, PAC Learning, Lower bound, Sample complexity

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_HfwXOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This submission considers PAC RL with known bounded rewards in episodic low-rank MDPs w/ finite realizable transition-kernel class Θ\Theta. It introduces an uncertainty marking machinery that achieves episode sample complexity O~(H3dAlog⁡(∣Θ∣/δ)/ϵ2)\widetilde{O}(H^3 d A \log(|\Theta|/\delta)/\epsilon^2) in the time-homogeneous setting and O~(H4dAlog⁡(H∣Θ∣/δ)/ϵ2)\widetilde{O}(H^4 d A \log(H|\Theta|/\delta)/\epsilon^2) in the time-inhomogeneous setting, improving upon prior MLE-based sample complexity bounds by factors of H2H^2 and HH, respectively; at least in certain regimes. To give computationally efficient implementation principles, it provides polynomial-time subroutines for Monte Carlo Hellinger radius estimation, augmented-MDP simulation, rare-switching linear optimistic planning, and slope bisection. It also establishes lower bounds of Ω(H3dAlog⁡(∣Θ∣/δ)/ϵ2)\Omega(H^3 d A \log(|\Theta|/\delta)/\epsilon^2) in the homogeneous setting and Ω(H4dAlog⁡∣Θ∣(1+log⁡d)2ϵ2+H3dAlog⁡(1/δ)(1+log⁡d)ϵ2)\Omega\big(\frac{H^4 d A \log|\Theta|}{(1+\log d)^2\epsilon^2} + \frac{H^3 d A \log(1/\delta)}{(1+\log d)\epsilon^2}\big) in the inhomogeneous setting.

Critical strengths
  • The original, mathematically rigorous resolution of the horizon-dependence issue in the important low-rank MDPs model based on a coupling argument for the first-mark trajectory.
  • Exemplary scholarly faithfulness, precision, and transparency: This paper is a model of scholarly writing. Every inherited tool, including Ville supermartingale MLE concentration and the one-step-back inequality (Huang et al., 2026; Cheng et al., 2023), the trajectory Hellinger chain rule (Foster et al., 2024), the binary hypothesis-testing variational dual (Elkayam & Feder, 2016), and rare-switching LSVI (Gao et al., 2021), is credited with pinpoint citations at the exact step of use. Furthermore, the paper candidly documents both the high-degree polynomial sample budgets of its certified planning reduction and the exact differences between its certified oracles and the sampled-integration neural implementation in Section 6, as well as why its inhomogeneous lower-bound family does not settle the log⁡(1/δ)\log(1/\delta) coefficient in the extreme high-confidence regime.
Critical weaknesses
  • The large polynomial exponents in the certified simulation budget NSAMP=O~(d4AH13/ϵ8)N_{\mathrm{SAMP}} = \widetilde{O}(d^4 A H^{13}/\epsilon^8) in Appendix E.6 and the remaining H(1+log⁡d)H(1+\log d) gap on the explicit log⁡(1/δ)\log(1/\delta) confidence term in the time-inhomogeneous setting are transparently disclosed and analyzed in the paper, and do not detract from the primary statistical contributions.
Questions for authors
  1. Tightening the γ+=O(H2/ϵ)\gamma_+ = O(H^2/\epsilon) scaling in LINPLAN (Appendix E.3, p. 36): In LINPLAN, the simulated episode count J=O~(d3H6/ϵ4)J = \widetilde{O}(d^3 H^6 / \epsilon^4) arises because the unnormalized augmented return is bounded by H+γH + \gamma with γ≤γ+=9Hχ=O(H2/ϵ)\gamma \le \gamma_+ = \frac{9H}{\sqrt{\chi}} = O(H^2/\epsilon), so normalizing by H+γH+\gamma shrinks the target accuracy to eLH+γ=Θ(ϵ2/H2)\frac{e_L}{H+\gamma} = \Theta(\epsilon^2/H^2). Since the first-mark indicator occurs at most once per episode (so the cumulative bonus contribution along any trajectory is in [0,γ][0, \gamma] rather than [0,γH][0, \gamma H], and its expected value under the selected policy is small near the bisection threshold), is it possible to avoid paying the worst-case (H+γ+)2=O(H4/ϵ2)(H+\gamma_+)^2 = O(H^4/\epsilon^2) scaling in JJ?
  2. Inhomogeneous confidence dependence when log⁡(1/δ)≫Hlog⁡∣Θ∣\log(1/\delta) \gg H\log|\Theta| (Appendix D.4, pp. 31–32): Appendix D.4 shows that for the restricted hard family ΘL\Theta^L, the stagewise estimation errors concentrate across the LL active stages to give an O(H3dAlog⁡(1/δ)/((1+log⁡d)ϵ2))O(H^3 d A \log(1/\delta)/((1+\log d)\epsilon^2)) confidence term. For general inhomogeneous ΘH\Theta^H, do you conjecture that the H4dAlog⁡(1/δ)/ϵ2H^4 d A \log(1/\delta)/\epsilon^2 term in Theorem 4 can be improved to H3dAlog⁡(1/δ)/ϵ2H^3 d A \log(1/\delta)/\epsilon^2 by bounding empirical Hellinger errors summed across all stages h∈[H]h \in [H] under a single joint supermartingale (paying Hlog⁡∣Θ∣H \log|\Theta| from the product class ΘH\Theta^H but only 1⋅log⁡(1/δ)1 \cdot \log(1/\delta) for the confidence level), or does stagewise radius feasibility require separate per-stage log⁡(H/δ)\log(H/\delta) concentration?

Minor issue: Equation (64) (p. 29, line 1560), replace the undefined symbol TT in the numerator 4Δ2Tn2m\frac{4\Delta^2 T}{n 2^m} with the episode count NN

General question: should the machinery of Lemma A.6 and its proof be demonstrated more concretely in the main text, especially given the fact that the coupling argument in the proof of Lemma A.6 seemingly does not hinge on the low-rank structure?

4 comments
AuthorsOpenReview ↗

Response to Weakness

We thank the reviewer for careful reading and thoughtful comments. We provide detailed responses to each point below.

W1: The large polynomial exponents in the certified simulation budget NSAMP=O~(d4AH13/ϵ8)N_{\mathrm{SAMP}} = \widetilde{O}(d^4 A H^{13}/\epsilon^8) in Appendix E.6 and the remaining H(1+log⁡d)H(1+\log d) gap on the explicit log⁡(1/δ)\log(1/\delta) confidence term in the time-inhomogeneous setting are transparently disclosed and analyzed in the paper, and do not detract from the primary statistical contributions.

A1: We thank the reviewer for recognizing our primary statistical contributions and for acknowledging the computational and confidence-dependence limitations.

Regarding computational complexity, Appendix E provides a fully specified polynomial-time implementation of our exploration framework, including but not limit to, uncertainty-radius estimation, rare-switching optimistic planning (LINPLAN), and slope bisection. The large polynomial exponents in NSAMPN_{\mathrm{SAMP}} arise from the conservative accuracy. For example, LINPLAN uses a worst-case bound on the augmented return.

Our computational contribution is therefore to establish polynomial-time implementability under an approximate MLE oracle. Importantly, these simulation costs are separate from the number of interactions with the real environment. We also acknowledge the remaining H(1+log⁡d)H(1+\log d) gap between the upper and lower bounds in the explicit log⁡(1/δ)\log(1/\delta) confidence term for the time-inhomogeneous setting. Tightening this dependence and reducing the polynomial simulation costs are interesting future directions.

AuthorsOpenReview ↗

Response to Question1-2

Q1: Tightening the γ+=O(H2/ϵ)\gamma_+ = O(H^2/\epsilon) scaling in LINPLAN (Appendix E.3, p. 36): In LINPLAN, the simulated episode count J=O~(d3H6/ϵ4)J = \widetilde{O}(d^3 H^6/\epsilon^4) arises because the unnormalized augmented return is bounded by H+γH+\gamma with γ≤γ+=9Hχ=O(H2/ϵ)\gamma \leq \gamma_+ = \frac{9H}{\sqrt{\chi}} = O(H^2/\epsilon), so normalizing by H+γH+\gamma shrinks the target accuracy to ϵLH+γ=Θ(ϵ2/H2)\frac{\epsilon_L}{H+\gamma} = \Theta(\epsilon^2/H^2). Since the first-mark indicator occurs at most once per episode (so the cumulative bonus contribution along any trajectory is in [0,γ][0,\gamma] rather than [0,γH][0,\gamma H], and its expected value under the selected policy is small near the bisection threshold), is it possible to avoid paying the worst-case (H+γ+)2=O(H4/ϵ2)(H+\gamma_+)^2 = O(H^4/\epsilon^2) scaling in JJ?

A1: We thank the reviewer for this insightful suggestion. The current normalization by H+γH+\gamma already exploits the fact that the first-mark bonus is paid at most once per episode. Without this property, the worst-case augmented return could scale as H+γHH+\gamma H. Nevertheless, the one-time bonus can still have magnitude γ\gamma, so the uniform bound on the unnormalized return remains H+γH+\gamma.

We agree that the resulting dependence on γ+\gamma_+ is conservative. In particular, near the bisection threshold, the expected marking contribution may be much smaller than its worst-case magnitude. However, the LINPLAN guarantee must hold before TESTMARK determines whether the returned policy is near the threshold, so this property cannot be directly assumed in the current analysis.

A promising direction is to exploit the Bernoulli structure of the marking reward through variance-sensitive concentration or a refined analysis that treats the original reward and marking probability separately. Such an approach may reduce the dependence on γ+\gamma_+, but establishing a uniform planning guarantee with improved complexity would require additional analysis. We therefore keep the conservative bound in the present theorem.

Q2: Inhomogeneous confidence dependence when log⁡(1/δ)≫Hlog⁡∣Θ∣\log(1/\delta) \gg H\log|\Theta| (Appendix D.4, pp. 31–32): Appendix D.4 shows that for the restricted hard family ΘL\Theta^L, the stagewise estimation errors concentrate across the LL active stages to give an O(H3dAlog⁡(1/δ)/((1+log⁡d)ϵ2))O(H^3 d A \log(1/\delta)/((1+\log d)\epsilon^2)) confidence term. For general inhomogeneous ΘH\Theta^H, do you conjecture that the H4dAlog⁡(1/δ)/ϵ2H^4 d A \log(1/\delta)/\epsilon^2 term in Theorem 4 can be improved to H3dAlog⁡(1/δ)/ϵ2H^3 d A \log(1/\delta)/\epsilon^2 by bounding empirical Hellinger errors summed across all stages h∈[H]h\in[H] under a single joint supermartingale (paying Hlog⁡∣Θ∣H\log|\Theta| from the product class ΘH\Theta^H but only 1⋅log⁡(1/δ)1\cdot\log(1/\delta) for the confidence level), or does stagewise radius feasibility require separate per-stage log⁡(H/δ)\log(H/\delta) concentration?

A2: We thank the reviewer for this insightful suggestion. We agree that a joint supermartingale over the product class ΘH\Theta^H is a promising approach to improving the confidence dependence in the time-inhomogeneous setting. In principle, such an argument could incur Hlog⁡∣Θ∣H\log|\Theta| for model complexity while paying only a single log⁡(1/δ)\log(1/\delta) confidence penalty, rather than treating each stage separately.

However, joint concentration alone does not immediately yield the proposed H3dAlog⁡(1/δ)/ϵ2H^3dA\log(1/\delta)/\epsilon^2 dependence. Our current analysis relies on stagewise Hellinger-radius feasibility to certify the uncertainty estimates used by the exploration and planning subroutines. A bound on the sum of empirical Hellinger errors across stages does not directly establish these individual feasibility conditions. Thus, closing the gap may require a joint uncertainty certificate or a refined analysis that avoids enforcing separate stagewise radius constraints. We view this as an interesting future work.

AuthorsOpenReview ↗

Response to Question3-4

Q3: Equation (64) (p. 29, line 1560), replace the undefined symbol TT in the numerator 4Δ2Tn2m\frac{4\Delta^2 T}{n2^m} with the episode count NN.

A3: We thank the reviewer for catching this typo. The symbol TT in Equation (64) is undefined and should be replaced by the episode count NN. Accordingly, the term should read 4Δ2Nn2m\frac{4\Delta^2 N}{n2^m}. We will correct this in the revision.

Q4: Should the machinery of Lemma A.6 and its proof be demonstrated more concretely in the main text, especially given the fact that the coupling argument in the proof of Lemma A.6 seemingly does not hinge on the low-rank structure?

A4: We thank the reviewer for this suggestion. We agree that the core argument of Lemma A.6 is more general than the low-rank MDP setting: its coupling/convex-geometric machinery only requires a finite-dimensional linear representation of the form xk,t⊤wx_{k,t}^{\top}w, and does not itself rely on the low-rank transition factorization.

The low-rank structure is used when instantiating Lemma A.6 in our MDP analysis: it ensures that the relevant quantities admit a dd-dimensional linear representation, so that the resulting bound scales with the low-rank dimension dd rather than the size of the state space.

We will clarify this separation and give a more concrete description of the mechanism in the main text.

Thank you for your detailed feedback. I keep my positive evaluation unchanged.

Reviewer_WFS1OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies MLE in low-rank episodic MDPs with known rewards, addressing two fundamental challenges: the lack of sharp statistical lower bounds that jointly capture problem parameters and model-class complexity, and the computational reliance of prior methods on strong optimization oracles. The contributions are twofold:

1.Algorithm: The authors propose an uncertainty marking algorithm that uses only an approximate MLE oracle alongside polynomial-time evaluation and simulation of fitted models, avoiding stronger oracles such as constrained Bellman optimization or posterior sampling.

2.Theory: The paper establishes matching PAC sample complexity upper and lower bounds in both the time-homogeneous and the time-inhomogeneous settings.

Critical strengths
  1. The paper establishes both upper and lower bounds for time-homogeneous and time-inhomogeneous low-rank MDPs that match up to logarithmic factors.
  2. Unlike previous near-optimal approaches that require optimistic posterior sampling or complex constrained optimization, this method relies solely on an MLE oracle with polynomial-time bonus estimation and planning.
Critical weaknesses

1.The empirical evaluation tests an extreme combination-lock task, where standard exploration is theoretically and empirically known to fail. Comparing only against generic model-free baselines (PPO, Double DQN, Bootstrapped DQN) and an unguided MLE ablation is of limited informative value. The authors should benchmark against representative low-rank or feature-based exploration algorithms . 2. The empirical results are restricted to a single synthetic block MDP serving as a sanity check. Standard continuous-state benchmark domains are needed to demonstrate practical applicability and numerical stability beyond artificial extreme cases.

Questions for authors

1.The paper should discuss and compare against [1], which also studies sample complexity bounds (both upper and lower bounds) in linear MDP settings. How do the structural assumptions and sample complexity in [1] differ from the low-rank factorization studied here?

2.Prior work on non-stationary infinite-horizon MDPs (e.g., [2]) studies time-varying dynamics similar to the time-inhomogeneous setting here, typically bounding transitions via variation budgets. Could the authors clarify the connection and whether the theoretical results can be transferred between the two settings?

[1] Sample complexity of reinforcement learning using linearly combined model ensembles

[2] Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism

3 comments
AuthorsOpenReview ↗

Response to Weakness

We thank the reviewer for careful reading and thoughtful comments. We provide detailed responses to each point below.

W1: The empirical evaluation tests an extreme combination-lock task, where standard exploration is theoretically and empirically known to fail. Comparing only against generic model-free baselines (PPO, Double DQN, Bootstrapped DQN) and an unguided MLE ablation is of limited informative value. The authors should benchmark against representative low-rank or feature-based exploration algorithms.

A1: We thank the reviewer for this constructive suggestion. We agree that comparisons with structured exploration algorithms are important. To address this concern, we have expanded our experiments in two directions.

Synthetic block MDP (Figure 1). We add a finite-horizon adaptation of REP-UCB, a representative feature-based exploration algorithm, using the same neural transition-model architecture and matched interaction budgets. Our method achieves near-optimal final performance across all three action-space sizes (A=2,4,8A=2,4,8), whereas REP-UCB does not consistently reach the target.

CartPole-v1 (Figure 2). We further evaluate our method on a standard continuous-state environemnt Cartpole-v1, comparing against REP-UCB, PPO, and DQN. Our method achieves an average return of 447.86447.86, compared with 411.27411.27 for REP-UCB.

These additional experiments provide more informative comparisons with feature-based exploration and extend our evaluation beyond the synthetic setting.

W2: The empirical results are restricted to a single synthetic block MDP serving as a sanity check. Standard continuous-state benchmark domains are needed to demonstrate practical applicability and numerical stability beyond artificial extreme cases.

A2: We thank the reviewer for this constructive suggestion. To address this concern, we have extended our empirical evaluation to CartPole-v1, a standard continuous-state control benchmark, in addition to our original synthetic block MDP experiments.

As shown in Figure 2, under the same training budget, our method achieves an average return of 447.86±25.82447.86\pm25.82, compared with 411.27±59.74411.27\pm59.74 for REP-UCB and 394.15±86.95394.15\pm86.95 for DQN, while PPO achieves 497.18±2.82497.18\pm2.82. These results demonstrate the practical feasibility of our approach beyond synthetic environments, although they do not establish general numerical stability across diverse benchmarks.

We would like to clarify that our primary contribution is theoretical, establishing near-optimal sample-complexity guarantees for low-rank MDPs. The experiments are intended to complement these guarantees.

AuthorsOpenReview ↗

Response to Question

Q1: The paper should discuss and compare against [1], which also studies sample complexity bounds (both upper and lower bounds) in linear MDP settings. How do the structural assumptions and sample complexity in [1] differ from the low-rank factorization studied here?

[1] Sample complexity of reinforcement learning using linearly combined model ensembles

A1: We thank the reviewer for pointing out this relevant work. Although both studies exploit structural assumptions on transition dynamics to achieve sample-efficient reinforcement learning, they consider different model classes and sources of prior information.

In [1], the transition kernel is modeled as a state-action-dependent linear combination of a fixed set of known base transition models, with unknown combination weights. In contrast, our framework assumes an unknown low-rank factorization of the transition kernel. This allows us to accommodate rich function classes, including neural-network-parameterized models. We will add this discussion in the revision.

Q2: Prior work on non-stationary infinite-horizon MDPs (e.g., [2]) studies time-varying dynamics similar to the time-inhomogeneous setting here, typically bounding transitions via variation budgets. Could the authors clarify the connection and whether the theoretical results can be transferred between the two settings?

[2] Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism

A2: We thank the reviewer for raising this important question. Although both settings involve time-dependent dynamics, they differ fundamentally in their assumptions and learning objectives.

In our episodic time-inhomogeneous setting, transition kernels Ph(⋅∣s,a)P_h(\cdot\mid s,a) may vary across stages h∈[H]h\in[H] but remain fixed across episodes. In contrast, [2] allows transitions and rewards to change throughout the learning process, with changes limited by variation budgets.

Our work considers unknown low-rank transition models and establishes PAC sample complexity guarantees for identifying an ϵ\epsilon-optimal policy. In contrast, [2] does not assume low-rank structure and focuses on minimizing dynamic regret in non-stationary environments.

These guarantees cannot be directly transferred. Our analysis relies on fixed stage-dependent transition kernels, allowing historical data to be reused for model estimation. In [2], environmental drift may invalidate historical observations, requiring different estimation and analysis techniques. Conversely, dynamic regret bounds do not directly imply our PAC guarantees.

Dear reviewer WFS1,

Thank you again for your review and your positive assessment. As the discussion period ends today, we wanted to check whether our responses have addressed your concerns. If so, we would be grateful if you would consider a higher score. Thank you for your time.

Reviewer_hEwrOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The authors study PAC learning in low-rank MDPs with unknown representations and known rewards. They assume a finite realizable transition class Θ\Theta. The authors propose an uncertainty-marking algorithm and proves sample complexities of O~(H3dAlog⁡∣Θ∣/ϵ2)\widetilde O(H^3 dA\log|\Theta|/\epsilon^2) in the homogeneous setting and O~(H4dAlog⁡∣Θ∣/ϵ2)\widetilde O(H^4 dA\log|\Theta|/\epsilon^2) in the inhomogeneous setting. It also gives worst-case lower bounds that essentially match these rates. Exploration and planning rely on an MLE oracle, and polynomial additional computation.

Critical strengths
  • The bounds improve the dependence on HH, dd, AA, and log⁡∣Θ∣\log|\Theta| at the same time. This gives a tighter characterization of the problem.
  • The algorithm needs only an MLE oracle. It avoids the constrained-optimization and optimistic-posterior-sampling oracles that prior work requires, which complements the statistical results.
  • The homogeneous construction recovers the extra horizon factor while keeping the rank independent of HH. It also explicitly handles adaptive selection of informative contexts.
Critical weaknesses
  • The algorithm follows a familiar template: model estimation, then optimistic planning, then exploration. Most analytical ingredients are established tools. The contribution therefore seems to lie mainly in how these tools are combined and refined. However, the paper should identify the key new idea more clearly and explain why existing approaches cannot already achieve the claimed rates.
  • The additional computation is polynomial, but Appendix E.6 reports very large polynomial simulation costs.
  • The experiments are a reasonable sanity check for exploration. However, the no-bonus ablation only shows that exploration helps. It does not show that the marking bonus outperforms alternative uncertainty bonuses. The authors appropriately acknowledge the limitations of the neural implementation and the experimental scope.
Questions for authors
  • Could the authors explain which step in prior MLE-based methods (REP-UCB, RAFFLE) produces the extra dependence on dd, AA, or HH, and how does the present method remove it? Are the algorithmic changes essential, or could a refined analysis of an existing algorithm recover part of the improvement?
  • RAFFLE already uses truncation to control cumulative uncertainty. Beyond the difference in formulation, what property does first-mark uncertainty provide that truncation does not? Specifically, which step that yields the linear dAdA dependence and the improved horizon dependence would fail under a RAFFLE-style construction?
3 comments
AuthorsOpenReview ↗

Response to Weakness

We thank the reviewer for careful reading and thoughtful comments. We provide detailed responses to each point below.

W1: The algorithm follows a familiar template: model estimation, then optimistic planning, then exploration. Most analytical ingredients are established tools. The contribution therefore seems to lie mainly in how these tools are combined and refined. That can support a valuable theoretical result. However, the paper should identify the key new idea more clearly and explain why existing approaches cannot already achieve the claimed rates.

A1: We thank the reviewer for this thoughtful comment. The key novelties lie in both the algorithmic design and theoretical analysis.

Algorithmic Design: (1) Unlike conventional elliptical bonuses of the form ∥ϕ(s,a)∥Λ−1\|\phi(s,a)\|_{\Lambda^{-1}}, our uncertainty bonus is constructed using density ratios, enabling a more refined characterization of exploration uncertainty. (2) Our first-mark mechanism captures uncertainty at its first occurrence along a trajectory, avoiding repeated accumulation and enabling efficient computation through an augmented-state formulation. (3) The resulting planning objective is nonlinear in the marking probability. We exploit its concavity and employ binary search over tangent coefficients and policy mixture weights, reducing nonlinear planning to a sequence of additive planning problems.

Theoretical Analysis: (1) Rather than relying on the standard elliptical potential lemma in our main sample-complexity analysis, we develop a different analytical approach based on Lemma 15. This lemma provides a general tool applicable to other adaptive online problems and does not inherently depend on the low-rank structure. Combined with our first-mark construction, it plays a central role in establishing the improved dependence on dd, AA, and HH. (2) We establish matching lower bounds up to logarithmic factors, demonstrating the statistical optimality of our sample-complexity rates under the considered assumptions.

Together, these contributions establish a distinct exploration mechanism and analytical framework that achieve near-optimal sample complexity, rather than merely combining existing techniques. We will clarify these distinctions and their roles in obtaining the improved rates in the revised paper.

W2: Scope of the computational claim. The additional computation is polynomial, but Appendix E.6 reports very large polynomial simulation costs.

A2: We thank the reviewer for highlighting this distinction. Our primary contribution is statistical, establishing near-optimal sample complexity for learning low-rank MDPs while maintaining polynomial computational complexity under relatively weak MLE oracle assumptions.

The reported simulation complexity is a conservative worst-case upper bound and does not necessarily reflect the computational cost in practice. Our experiments demonstrate the practical implementability of the proposed exploration mechanism in challenging environments, complementing the theoretical worst-case guarantees. As with many theoretically motivated algorithms, the worst-case complexity can be substantially larger than the computational requirements observed in practice.

Further reducing the computational complexity and tightening these worst-case bounds are important directions for future work.

W3: The experiments are a reasonable sanity check for exploration. However, the no-bonus ablation only shows that exploration helps. It does not show that the marking bonus outperforms alternative uncertainty bonuses. The authors appropriately acknowledge the limitations of the neural implementation and the experimental scope.

A3: We thank the reviewer for this observation. We agree that the original no-bonus ablation does not establish an advantage over alternative uncertainty bonuses. To address this concern, we have added REP-UCB, an important baseline and Cartpole-v1 experiments in the revision.

Synthetic block MDP (Figure 1). Under matched interaction budgets, our method achieves near-optimal final performance for all three action-space sizes (A=2,4,8A=2,4,8), whereas REP-UCB shows temporary improvement for A=2A=2 but remains near the safe value for A=4,8A=4,8.

CartPole-v1 (Figure 2). Our method achieves 447.86±25.82447.86\pm25.82, compared with 411.27±59.74411.27\pm59.74 for REP-UCB, demonstrating competitive performance on a standard continuous-state benchmark.

These results provide additional evidence for the effectiveness of first-marking exploration relative to an alternative uncertainty-based method.

AuthorsOpenReview ↗

Response to Question

Q1: Could the authors explain which step in prior MLE-based methods (REP-UCB, RAFFLE) produces the extra dependence on dd, AA, or HH, and how does the present method remove it? Are the algorithmic changes essential, or could a refined analysis of an existing algorithm recover part of the improvement?

A1: We thank the reviewer for this important question. In REP-UCB, the additional dd and AA dependencies arise from the one-step-back error-transfer analysis and the accumulation of learned-feature elliptical bonuses. In RAFFLE, importance-sampling-based error transfer introduces additional action dependence, while elliptical-bonus calibration and accumulation contribute further dimension dependence.

In contrast, our method combines a new constrained uncertainty radius with first-marking exploration and trajectory-level Hellinger control. Crucially, Lemma 15 provides a general cumulative uncertainty bound without relying on the elliptical potential lemma, yielding linear dAdA dependence and improved PAC guarantees.

In summary, both algorithm design and analysis contribute to the tighter results.

Q2: RAFFLE already uses truncation to control cumulative uncertainty. Beyond the difference in formulation, what property does first-mark uncertainty provide that truncation does not? Specifically, which step that yields the linear dAdA dependence and the improved horizon dependence would fail under a RAFFLE-style construction?

A2: We thank the reviewer for this important question. Mathematically, first-marking and truncation are closely related; in fact, they can be bounded by constant multiples of each other, i.e., C0⋅Marking≤Truncation≤C1⋅MarkingC_0\cdot\mathrm{Marking}\leq\mathrm{Truncation}\leq C_1\cdot\mathrm{Marking} for some absolute constants C0,C1C_0, C_1. Their main distinction lies in computational implementation: RAFFLE-style truncation requires sequential dynamic programming with truncation at each stage, whereas our first-marking objective allows the marking probabilities to be evaluated in parallel, simplifying the planning procedure.

Importantly, the linear dAdA dependence does not arise from first-marking alone. It follows from our new uncertainty-radius design, which avoids the conventional elliptical bonus ∥ϕ∥Λ−1\|\phi\|_{\Lambda^{-1}}, together with the tighter cumulative uncertainty analysis in Lemma 15. The improved horizon dependence is further supported by trajectory-level Hellinger error control, which avoids accumulating model-estimation errors through repeated stagewise bounds.

Dear reviewer hEwr,

Thank you again for your review and your positive assessment. As the discussion period ends today, we wanted to check whether our responses have addressed your concerns. If so, we would be grateful if you would consider a higher score. Thank you for your time.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.