acceptodds
Under review as a conference paper at ICLR 2027

A Computationally Efficient and Rate-optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

Abstract

We study episodic linear Markov decision processes with unknown transitions, adversarial losses, and bandit feedback. The state-of-the-art result for this setting (Liu et al., 2024a) either achieves regret with a computationally inefficient algorithm or achieves suboptimal regret, where is the number of episodes. Our work gives the first regret with a polynomial-time algorithm. Our method reduces adversarial linear MDPs to adversarial linear bandits whose action set consists of policies’ expected feature vectors. The central challenge is that is unknown and can be estimated only through exploration. We address this challenge by constructing an *approximate separation oracle* for that either generates executable policies from queried features or refines an outer approximation of . This approach draws inspiration from the reduction of van Erven et al. (2025) for linear contextual bandits and the oracle-efficient linear bandit algorithm of Ito et al. (2019), but additionally handles the imprecision of the oracle. The resulting algorithm requires only aggregate loss feedback and, to our knowledge, is the first polynomial-time algorithm for adversarial MDPs with aggregate feedback beyond the tabular case.

Primary area:
learning theory
Keywords:
Adversarial MDPs, Learning Theory, Online Learning, Reinforcement Learning

Reviews

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

The paper studies adversarial linear MDPs with unknown transitions and aggregate bandit feedback, where the learner observes only the total episode loss. It obtains O~(d5H9/2K)\widetilde{\mathcal O}(d^5H^{9/2}\sqrt K) expected regret with polynomial computation. Previous work by Liu et al. achieves either K\sqrt K regret with an inefficient algorithm or K3/4K^{3/4} regret with an efficient algorithm.

At a high level, the algorithm represents each policy by its expected feature vector, reducing the problem to a linear bandit problem over an unknown feasible set. It runs a linear bandit algorithm over an outer convex approximation of this set and refines the approximation using separating cuts. To do this, the authors develop ApproxSep, which either returns a certified cut or constructs a policy mixture approximating a queried feature vector.

Critical strengths

The main result addresses a significant gap in prior work by achieving the optimal dependence on KK with polynomial computation.

I also find the techniques interesting. The method combines approximate linear optimization from transition data, certified cuts, policy mixtures, and bias correction to avoid enumerating an exponentially large policy class. In particular, the analysis connects the approximation certificates to uncertainty under the policies actually executed, allowing accumulated error to be controlled through an elliptical-potential argument.

Critical weaknesses

Some algorithmic choices are insufficiently motivated. The paper provides formal guarantees, but more intuition would help explain why the finite-support exploration distribution and the particular Frank–Wolfe update in ApproxSep are appropriate. The limited explanation makes the algorithm harder to understand and assess.

Questions for authors

Why use the particular 2p2p support points instead of sampling directly from qkq_k? A finite batch sampled from qkq_k could also be processed by ApproxSep. Could the authors explain which properties of the support construction are needed for the regret and cut-complexity analyses, and clarify its connection to SCRiBLe?

Could the authors provide intuition for choosing the step size γj=1/j\gamma_j=1/j in the ApproxSep update xj=xj−1+γj(ϕ^j−xj−1)x_j=x_{j-1}+\gamma_j(\widehat\phi_j-x_{j-1})?

Although Liu et al. assume per-step bandit feedback, their inefficient exponential-weights algorithm appears to use losses only through Lk=∑hℓk,hL_k=\sum_h\ell_{k,h}. Their transition estimation uses the observed trajectory. Does any component require observing individual per-step losses? If not, please clarify in the introduction that their inefficient K\sqrt K algorithm is also compatible with aggregate feedback, while the present contribution achieves this regret rate with polynomial computation.

Could the authors explain which steps in the analysis lead to the large dependence on dd and HH?

Could the authors provide an explicit bound on the total computational complexity in K,d,H,AK,d,H,A, including moment estimation, repeated cuts, and LSVI calls?

3 comments

We thank the reviewer for the valuable feedback. You questions are elaborated below.

Question 1:

Why use the particular 2p2p support points instead of sampling directly from qkq_k? A finite batch sampled from qkq_k could also be processed by ApproxSep. Could the authors explain which properties of the support construction are needed for the regret and cut-complexity analyses, and clarify its connection to SCRiBLe?

Answer:

Following Ito et al. (2019), we use the 2p2p symmetric points Yi,±=μ^k±c0Σ^k1/2ei,,p=dH.Y_{i,\pm}=\widehat\mu_k\pm c_0\widehat\Sigma_k^{1/2}e_i, \\, p=dH. These perturbations explore all feature directions around the estimated mean, with scales determined by the covariance of qkq_k, enabling loss estimation from bandit feedback. The symmetric construction provides two properties needed in our analysis.

First, conditional on the moment estimates, uniform sampling over these points gives exactly mean μ^k\widehat\mu_k and covariance (c02/p)Σ^k(c_0^2/p)\widehat\Sigma_k. These identities let us compute the expected loss estimator and control its bias (Lemma B.2). Using a random batch with the same estimator would introduce additional errors from the batch's empirical moments.

Second, when the moment estimates are accurate, every point is close to the mean of qkq_k in its covariance norm. Any certified cut excluding such a point therefore removes a constant fraction of the current probability mass, yielding the cut bound in Lemma D.3. Direct samples from qkq_k can lie far from the mean, so excluding one need not remove a constant fraction of the mass.

SCRiBLe explores using perturbations scaled by the inverse of a Hessian matrix. For the entropic barrier FOF_{\mathcal O}, ∇2FO(μk)=Σk−1\nabla^2F_{\mathcal O}(\mu_k)=\Sigma_k^{-1}. We implement the inverse-Hessian using the estimated covariance Σ^k\widehat\Sigma_k.

Question 2:

Could the authors provide intuition for choosing the step size γj=1/j\gamma_j=1/j in the ApproxSep update xj=xj−1+γj(ϕ^j−xj−1)x_j=x_{j-1}+\gamma_j(\widehat\phi_j-x_{j-1})?

Answer:

The choice γj=1/j\gamma_j=1/j makes the iterate a uniform average and matches the uniform sampling of policies for execution:

x^M=1M∑j=1Mϕ^j,EJ∼Unif[M][ΔJ2]=1M∑j=1MΔj2.\widehat x_M=\frac1M\sum_{j=1}^M\widehat\phi_j, \qquad \mathbb{E}_{J\sim\mathrm{Unif}[M]}[\Delta_J^2] =\frac1M\sum_{j=1}^M\Delta_j^2.

Lemma 5.2 bounds the mixture's feature error using this same average of squared estimation error. Thus the error weights in the analysis are exactly the execution probabilities, allowing collected trajectories to control the cumulative error through exploration.

Similar step size is used in the standard Frank-Wolfe algorithm [1]. They choose γj=2/(j+2)\gamma_j = 2/(j+2), which is of the same order as ours. Theirs allows a slightly better convergence rate (in terms of log-terms), while we use the 1/j for simplicity, as it leads to a uniform sampling as discussed above.

[1] Bubeck, S., 2015. Convex Optimization: Algorithms and Complexity.

Question 3:

Can Liu et al [2024] handle aggregated bandit feedback?

Answer:

Liu et al.'s algorithm can also handle aggregate-feedback. We will acknowledge its aggregate-feedback compatibility in the introduction and identify polynomial computation with K\sqrt{K} regret as our contribution.

Question 4:

Could the authors explain which steps in the analysis lead to the large dependence on dd and HH?

Answer:

The large dimension and horizon factors mainly come from computing reliable bounds on policy-feature estimation errors and correcting the resulting bias in loss estimation.

First, Algorithm 3 incurs a confidence factor β=O~(d)\beta=\widetilde O(d) for planning and feature estimation, and an additional factor βH\beta H to obtain a computable upper bound on the uncertainty encountered by the returned policy. Squaring the resulting error bounds and summing over executed trajectories gives EK=E∑k=1Kϵk2=O~(d6H5),E_K =\mathbb{E}\sum_{k=1}^K\epsilon_k^2 =\widetilde O(d^6H^5), as shown in Section 5.3.

Second, the bias-correction analysis in Lemma 4.1 contributes a factor p2=(dH)2p^2=(dH)^2, giving the dominant regret term p2KEK=O~(d5H9/2K).p^2\sqrt{KE_K}=\widetilde O(d^5H^{9/2}\sqrt K).

Question 5:

Could the authors provide an explicit bound on the total computational complexity in K,d,H,AK,d,H,A, including moment estimation, repeated cuts, and LSVI calls?

Answer:

Let p=dHp=dH. Algorithm 4 limits each episode to at most Nmax⁡=O~(p+H,K3/2)N_{\max}=\widetilde O(p+\sqrt H\\,K^{3/2}) preparation attempts. Thus, over KK episodes, there are at most B=KNmax⁡=O~(pK+H,K5/2)B=KN_{\max}=\widetilde O(pK+\sqrt H\\,K^{5/2}) preparation attempts, hence at most BB moment-estimation calls, 2pB2pB calls to ApproxSep, and 2pKB2pKB calls to ApproxLO.

All ApproxLO calls within an episode use the same transition data, so we can reuse the matrices Λk,h−1\Lambda_{k,h}^{-1} across these calls. Each ApproxLO call then costs CLO=O!(H[(K+1)A(dp+d2)+d2p]),C_{\mathrm{LO}}=O\\!\left(H\left[(K+1)A(dp+d^2)+d^2p\right]\right), including vector-valued feature evaluation.

Moment estimation uses batches of m=O(p2+pK)m=O(p^2+pK) samples from qkq_k to estimate its mean and covariance. Theorem 4 of Ito et al. (2019) gives a sampler with total-variation error ϵ\epsilon and cost O~(p4/ϵ4)\widetilde O(p^4/\epsilon^4) per sample. Taking ϵ=Θ(1/m)\epsilon=\Theta(1/m) gives O~(p4m5)\widetilde O(p^4m^5) per batch. In our implementation, checking whether x∈Ox\in\mathcal O means checking the stored cut inequalities and the initial bounding ball, costing O(p(B+1))O(p(B+1)). Evaluating f(x)=ηx⊤Zk−1f(x)=\eta x^\top Z_{k-1} is a length-pp inner product, costing O(p)O(p). Thus, the total moment-estimation cost is B⋅O~(p4m5)⋅O(p(B+1))=O~(p5B2m5).B\cdot\widetilde O(p^4m^5)\cdot O(p(B+1)) =\widetilde O(p^5B^2m^5). Rank-one updates to the covariance inverses cost O(d2)O(d^2) per observed transition, hence O(KHd2)O(KHd^2) in total. Combining the three contributions gives the conservative total arithmetic bound

O~!(pKB,CLO⏟ApproxLO calls+p5B2m5⏟moment estimation+KHd2⏟covariance updates).\widetilde O\\!\left( \underbrace{pKB\\,C_{\mathrm{LO}}}_{\text{ApproxLO calls}} +\underbrace{p^5B^2m^5}_{\text{moment estimation}} +\underbrace{KHd^2}_{\text{covariance updates}} \right).

I thank the authors for their detailed response. The authors' response has addressed my concerns regarding several motivations behind the algorithmic design. In my opinion, achieving optimal guarantees for adversarial linear MDPs under bandit feedback with a computationally efficient algorithm is a meaningful contribution to RL theory. Therefore, I would like to maintain my positive assessment of this paper.

Reviewer_ZQS9OpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies linear AMDPs under aggregate bandit feedback. Even without aggregate bandit feedback, the currently known UBs are K^{3/4} efficiently and K^{1/2} inefficiently. This paper obtain the first efficient K^{1/2} algorithm, which also extends to aggregate bandit feedback.

Technically, this paper builds upon the idea of Liu et al [2024] to view linear MDPs as linear bandits, and adopted a convex approximation idea from van Erven et al [2025] (who used for linear contextual bandits). But due to the recursive structure of MDPs, the expected feature set K\mathcal K formed by all policies can be quite weird, and the authors adopted an idea from Ito et al [2019] to optimize on an outer convex set O\mathcal O that contain all these features. To refine O\mathcal O, the authors develop an efficient implementation (via Frank-Wolfe) of an approximate separation oracle, which, when given a point in O\mathcal O, either gives a policy approximating this point or gives a separation oracle between it and K\mathcal K. The algorithm then performs continuous Hedge over O\mathcal O.

Critical strengths

The optimal KK-dependencies for linear AMDPs has been open for long, from Luo et al's 14/15, all the way along Dai et al's 8/9, Sherman et al's 6/7, Kong et al's 4/5, finally to Liu et al's {efficient 3/4, inefficient 1/2}. This paper closes the final missing piece: K1/2K^{1/2} is indeed attainable efficiently.

While the techniques seem a combination of existing methods (and the idea of using approximate separation oracles is quite common in recent developments of Φ\Phi-regret in game theory or swap regret; given the closeness, I encourage the authors to give more details on how your technique differs from theirs), I feel putting all of them together (and finding the right pieces to put together) may not be super easy, and the result is good. So I'm somehow leaning towards acceptance.

Critical weaknesses

While this paper is indeed polytime (and thus computationally efficient in standard TCS sense), the extensive usage of continuous exponential weights, Frank-Wolfe decomposition, cutting plane oracles, etc (like, at least dHKdHK calls to the approximate linear optimization procedure ApproxLO per episode, so in total dHK2dHK^2 calls at least, where KK is the number of episodes) make it hardly "efficient" in a common sense.

Indeed, let's look back into tabular AMDPs with unknown transitions and bandit feedback: Jin et al [2020] already established O(HSAK)O(HS\sqrt{AK}) regret using occupancy measure methods, which is only S\sqrt S away from the lower bound, but subsequent works have focused a lot on policy optimization (Shani et al [2020] for K2/3K^{2/3}, Luo et al [2021] for H2SAKH^2 S\sqrt{AK}, and very recently/concurrently Li & Tsuchiya [2026] for HSAKH S \sqrt{AK}) & FTPL (Wang & Dong [2020] for HSAKHS\sqrt{AK} with full information and Dai et al [2022] for HSAKHS\sqrt{AK} with bandit feedback) methods to match the same rate already attainable by Jin et al [2020]. The only reason is that occupancy measure methods solve a giant optimization problem in each round, while PO and FTPL perform local updates and are much more efficient. So when looking at this title, I was originally expceting a PO (or FTPL, although I feel highly unlikely) method.

With that being said, Jin et al [2020] was still a very good paper, and this paper indeed gives the first "computationally efficient" (polytime) for linear AMDPs (which even extends to aggregate bandit feedback). Technical speaking, this paper looks a bit like A+B+C, but I agree it's quite non-trivial to put them together.

Overall, I feel this paper suitable for ICLR, but all these points also explain why I didn't give a 4.

Questions for authors
  1. How does your approx separation oracle differ from those recently commonly used for Φ\Phi-regret or swap regret? Say Daskalakis et al [2025 "Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games"]'s Shell algo, and moreover Zhang et al [2025 "Learning and Computation of Φ\Phi-Equilibria at the Frontier of Tractability"]'s version that also give one of {a policy approximating the fixed point, a separating plane}.
  2. While it is clear that the algorithm is polytime, I am trying to find an exact upper bound somewhere in the paper, but didn't suceed. Only the exact regret bound O~(d5H4.5K)\tilde O(d^5 H^{4.5} \sqrt K) is given. What's the exact dependencies, in terms of both the number of oracle calls and the remaining computational cost for planning, of the proposed algorithm?
  3. Are there any other technical contributions that I missed? Overall, I feel the technical contributions incremental, and I lean towards acceptance solely because this paper completes the last piece of puzzle. So it'd be great if the authors can remind me of some extra technical contributions, that can be of general and independent interest, of this paper.
3 comments

We thank the reviewer for the valuable feedback. You questions are elaborated below.

Question 1:

How does your approx separation oracle differ from those recently commonly used for Φ\Phi-regret or swap regret? Say Daskalakis et al [2025]'s Shell algo, and moreover Zhang et al [2025]'s version that also give one of {a policy approximating the fixed point, a separating plane}.

Answer:

Thanks for pointing out these references. We will add comparison with their procedure. Below we compare our approximate separation oracle with their semi-separation oracle:

Similarity: Both oracles rely on the following one-sided guarantee: if a queried point is in the desired set, the oracle will NOT cut it; if a quered point is not in the desired set, the oracle MAY or MAY NOT cut it.

Differences: The source of the "ambiguity region" is different: ours is due to statistically limits, while theirs is due to computational limits. More precisely, in our case, for a queried point, it might be impossible to tell whether it belongs to the desired set because of the limited data the learner currently has. In their case, one can determine if a point belongs to the desired set if there is unrestricted computational power.

Due to the problem differences, the implementation is also different: we accept a point if one can find a mixture of policies whose average policy-feature approximates the queried feature, while they accept a point if one can find a fixed point for the quered mapping. Along with the set of policies, ours also output the policies' corresponding feature error bounds.

Question 2:

What's the exact dependencies for computational complexity, in terms of both the number of oracle calls and the remaining computational cost for planning, of the proposed algorithm?

Answer:

Let p=dHp=dH. Algorithm 4 limits each episode to at most Nmax⁡=O~(p+H,K3/2)N_{\max}=\widetilde O(p+\sqrt H\\,K^{3/2}) preparation attempts. Thus, over KK episodes, there are at most B=KNmax⁡=O~(pK+H,K5/2)B=KN_{\max}=\widetilde O(pK+\sqrt H\\,K^{5/2}) preparation attempts, hence at most BB moment-estimation calls, 2pB2pB calls to ApproxSep, and 2pKB2pKB calls to ApproxLO.

All ApproxLO calls within an episode use the same transition data, so we can reuse the matrices Λk,h−1\Lambda_{k,h}^{-1} across these calls. Each ApproxLO call then costs CLO=O!(H[(K+1)A(dp+d2)+d2p]),C_{\mathrm{LO}}=O\\!\left(H\left[(K+1)A(dp+d^2)+d^2p\right]\right), including vector-valued feature evaluation.

Moment estimation uses batches of m=O(p2+pK)m=O(p^2+pK) samples from qkq_k to estimate its mean and covariance. Theorem 4 of Ito et al. (2019) gives a sampler with total-variation error ϵ\epsilon and cost O~(p4/ϵ4)\widetilde O(p^4/\epsilon^4) per sample. Taking ϵ=Θ(1/m)\epsilon=\Theta(1/m) gives O~(p4m5)\widetilde O(p^4m^5) per batch. In our implementation, checking whether x∈Ox\in\mathcal O means checking the stored cut inequalities and the initial bounding ball, costing O(p(B+1))O(p(B+1)). Evaluating f(x)=ηx⊤Zk−1f(x)=\eta x^\top Z_{k-1} is a length-pp inner product, costing O(p)O(p). Thus, the total moment-estimation cost is B⋅O~(p4m5)⋅O(p(B+1))=O~(p5B2m5).B\cdot\widetilde O(p^4m^5)\cdot O(p(B+1)) =\widetilde O(p^5B^2m^5). Rank-one updates to the covariance inverses cost O(d2)O(d^2) per observed transition, hence O(KHd2)O(KHd^2) in total. Combining the three contributions gives the conservative total arithmetic bound

O~!(pKB,CLO⏟ApproxLO calls+p5B2m5⏟moment estimation+KHd2⏟covariance updates).\widetilde O\\!\left( \underbrace{pKB\\,C_{\mathrm{LO}}}_{\text{ApproxLO calls}} +\underbrace{p^5B^2m^5}_{\text{moment estimation}} +\underbrace{KHd^2}_{\text{covariance updates}} \right).

Question 3:

Are there any other technical contributions that I missed? Overall, I feel the technical contributions incremental, and I lean towards acceptance solely because this paper completes the last piece of puzzle. So it'd be great if the authors can remind me of some extra technical contributions, that can be of general and independent interest, of this paper.

Answer:

A reusable contribution is the oracle in Theorem 5.3: it returns an executable policy, an estimate of its full expected-feature vector, and a computable error bound. The bound certifies feature accuracy and approximate optimality for the queried linear cost.

The technical contribution is to obtain these guarantees jointly, with high probability and uniformly over adaptive queries using the same transition data, while controlling errors by uncertainty under the returned policy itself. Standard scalar planning alone does not provide this joint guarantee. Algorithm 3 combines optimistic planning with vector-valued feature evaluation and uncertainty evaluation. Gibbs smoothing enables the covering argument in Appendix C. Consequently, data collected by executing these policies control the cumulative error.

These guarantees do not depend on our separation procedure or bandit update. They can be used by other algorithms that repeatedly query linear objectives in an unknown MDP and need reliable policy-feature estimates.

Thanks for the clarification. The first and third clarification resolves my concern regarding technical contributions. I encourage the authors to incorporate them in the revision. I maintain my assessment of a "clear accept": Giving the first computationally efficient K\sqrt K algorithm for the standard and well-studied linear AMDP problem, which has been open for 5 or 6 years despite a lot of technical advances, is definitely suitable for ICLR and should be accepted. I originally reserved 4, the highest score for this year's ICLR, for the "top paper". But it seems that 4 is intended to mean "clear accept" while 3 is "borderline accept". Therefore, I am happy to adjust my score to 4 to reflect my original and current assessment of "clear accept".

We thank the reviewer for the quick follow-up and positive assessment. We will incorporate these clarifications into the revision, including a comparison with prior separation oracles, the detailed computational complexity, and a clearer explanation of our technical contributions.

Reviewer_oBBvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work studies adversarial linear MDPs under aggregate bandit feedback, with the goal of developing a more computationally efficient learning algorithm. In this setting, the learner receives aggregated reward information, which creates challenges for using the feedback to guide policy updates. To address these challenges, the authors introduce a new algorithmic component specifically designed to handle aggregate reward feedback and incorporate it into the proposed learning procedure. They establish a K\sqrt{K}-type regret bound for the resulting algorithm, providing a theoretical performance guarantee under this feedback model.

Critical strengths
  1. This work considers aggregate reward feedback, which is relevant to practical applications where only cumulative rewards are observed. This setting also introduces additional challenges for learning and algorithm design.

  2. The authors develop an oracle component that enables a more computationally efficient algorithm, addressing a key computational challenge in this feedback setting.

Critical weaknesses

First, the practical applicability of the setting is limited by its restrictive assumptions. Specifically, the model assumes that transitions and rewards admit exact linear representations using known, shared feature functions, with small approximation error. These assumptions are difficult to satisfy in practical applications.

Second, the technical contributions are unclear. The paper does not adequately explain how the proposed techniques improve upon existing approaches or identify the key methodological advances that enable the computational improvements.

Questions for authors
  1. The motivation for studying adversarial linear MDPs with known feature functions should be clarified, particularly in comparison with prior work on tabular MDPs. What advantages does this formulation offer, and how do these advantages justify its complexity and structural assumptions? The authors should also explain the specific technical improvements in the proofs relative to previous work, identifying the key challenges and the new arguments needed to address them.

  2. I suggest renaming Section 2, “Linear MDPs,” to “Assumptions.” This section should explain when the assumptions hold and provide examples of settings in which they are reasonable. It should also compare these assumptions with those used in previous work, including the tabular setting, and clarify their implications for the applicability of the results.

2 comments

We thank the reviewer for the valuable feedback. You questions are elaborated below.

Question 1:

The motivation for studying adversarial linear MDPs with known feature functions should be clarified, particularly in comparison with prior work on tabular MDPs. What advantages does this formulation offer, and how do these advantages justify its complexity and structural assumptions? The authors should also explain the specific technical improvements in the proofs relative to previous work, identifying the key challenges and the new arguments needed to address them.

Answer:

Motivation and tabular inclusion. Linear MDPs are a basic and standard model for studying function approximation in large state-action spaces: a low-dimensional representation lets the learner generalize across pairs instead of learning each pair separately as in tabular MDPs. Compared to the bounds in tabular MDPs, our regret bound depends only on the feature dimension dd, with no dependence on the number of states or actions. The linear MDP model has been widely adopted for function approximation since being proposed (Jin et al., 2020).

The linear MDP model includes tabular MDPs with d=SAd=SA where SS is the number of states per layer, ϕh(s,a)=e(s,a),[ψh(s′)](s,a)=Ph(s′∣s,a),[θk,h](s,a)=ℓk,h(s,a).\phi_h(s,a) =e_{(s,a)}, [\psi_h(s')]_{(s,a)} =P_h(s'\mid s,a), [\theta_{k,h}]_{(s,a)} =\ell_{k,h}(s,a). Linear MDP is more general than tabular MDP because informative representation can have d≪SAd\ll SA.

[Jin et al., 2020] Provably Efficient Reinforcement Learning with Linear Function Approximation.

Technical improvement. Algorithmically, our algorithm is most closely related to prior algorithms for linear bandits (Ito et al., 2019) and linear contextual bandits (van Erven et al., 2025). It is also conceptually related to the computationally inefficient algorithm of Liu et al. (2024), with their enumeration over exponentially many policies replaced by an optimization over a convex region in the feature space. The key technical challenges are constructing valid separating cuts despite estimation errors and controlling the resulting bias in loss estimation. Please refer to the Introduction section for a detailed discussion on the relation between our algorithm and the prior algorithms, an explanation of the technical challenges, and an overview of our new arguments.

Question 2:

I suggest renaming Section 2, “Linear MDPs,” to “Assumptions.” This section should explain when the assumptions hold and provide examples of settings in which they are reasonable. It should also compare these assumptions with those used in previous work, including the tabular setting, and clarify their implications for the applicability of the results.

Answer:

We will rename Section 2 to “Problem setting and assumptions” and add examples and the tabular comparison in Question 1.

Examples for linear MDPs are rich in the literature, e.g., Example 2.1 and Example 2.2 in Jin et al. (2020). We will include some of them and provide references for readers.

Question 3:

First, the practical applicability of the setting is limited by its restrictive assumptions. Specifically, the model assumes that transitions and rewards admit exact linear representations using known, shared feature functions, with small approximation error. These assumptions are difficult to satisfy in practical applications.

Answer:

Although the linear MDP model is simple, empirical studies also demonstrate its practical value. Zhang et al. (2022) learn linear-MDP representations through contrastive learning and use uncertainty bonuses in the learned representation to guide exploration. Their algorithm achieves superior performance on continuous control tasks. Zhou et al. (2024) use a linear-MDP model to learn treatment recommendations from patient records. Combining data from several hospital units gives better results on test data than learning from each unit separately.

It is quite often that in theoretical work, researchers assume exact realizability to obtain clean theoretical insights. However, such assumptions do not necessarily limit the practical applicability of algorithms developed based on them, as the above empirical examples demonstrate.

Thank you for your response. I will decide my final score after discussing it with other reviewers and the AC.

Comments on the paper

1 comment

Dear Reviewers,

The reviewer–author discussion period closes in approximately 36 hours. If you have not yet reviewed the authors’ rebuttal, please do so as soon as possible and post a brief acknowledgment, indicating whether the response addresses your main concerns. Please raise any remaining questions promptly so the authors have an opportunity to respond, and update your review and scores if warranted.

Thank you for your time and thoughtful engagement!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.