Pith. sign in

REVIEW 4 major objections 4 minor 73 references

Adaptive Resolving Methods for Reinforcement Learning with Function Approximations

T0 review · 4 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims an RL algorithm that re-solves a small identified LP basis as data arrive attains an instance-dependent ~O(1/N) suboptimality gap, tightening the prior O(1/√N) worst case on favorable instances.

desk verdict The resolving-on-a-fixed-basis idea is a real step forward for LP-based RL, but the pseudocode as written does not implement the analyzed algorithm: J* in Algorithm 1 is the set of inactive basic slacks, not the active constraints Lemma 1 requires. read the letter →

arxiv 2505.12037 v1 pith:DMSAIUCG submitted 2025-05-17 cs.LG

Jiashuo Jiang , Yiming Zong , Yinyu Ye This is my paper · ORCID
classification cs.LG MSC 90C4090C0568Q32
keywords reinforcementlearninglinearfunctionapproximationapproximateprogrammingconstraintsamplingonlineoptimalbasisidentificationinstance-dependentsamplecomplexityMarkovdecisionprocesses
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper aims to establish that the linear-programming route to reinforcement learning with linear function approximation need not pay the worst-case $O(1/\sqrt{N})$ suboptimality gap of earlier LP-based methods. Its algorithm first pinpoints the small optimal basis of the value LP — at most as many constraints as basis functions, regardless of the state–action space size — and then, as each new batch of transition samples arrives, re-solves only the linear equations of that basis while adaptively correcting the right-hand side, so that constraint violations self-correct. The paper proves an instance-dependent bound: for instances whose gap parameter $\Delta$ and basis conditioning $\sigma$ are favorable, the output after $N$ samples has $\tilde{O}(1/N)$ suboptimality, equivalent to $O(1/\varepsilon)$ sample complexity instead of $O(1/\varepsilon^2)$. The Mountain Car experiments illustrate the mechanism, shrinking an LP with 12,000 constraints to 25 and reaching roughly 92.5% task success. The proven guarantees concern the reduced LP, and the final bridge back to the original RL problem relies on a constraint-sampling theorem from prior work.

What carries the argument

The load-bearing object is the optimal basis $(I^*, J^*)$ of the value LP: Lemma 1 shows some optimal weight vector is supported on at most $d_2 \le d_1$ coordinates and is the unique solution of the square system $A_{J^*,I^*} x_{I^*} = c_{J^*}$, so all other constraints and variables are irrelevant at the optimum. Algorithm 1 identifies the basis from an estimated matrix using the simplex method, and Theorem 2 shows $O(K \log(1/\varepsilon)/\Delta^2)$ samples suffice to identify the true optimal basis with high probability. Algorithm 2 then solves only that system each round, with right-hand side $c^n_{J^*}/(N-n+1)$, queries the generative model on the $J^*$ constraints, and updates $c^{n+1} = c^n - A^n x^n$, which drives the scaled slack process $\tilde{c}_{(s,a)}(n)$ back toward $c$ instead of letting violations accumulate. A sub-martingale concentration argument with a stopping time $\tau$ shows this process stays near $c$ long enough that $E[N-\tau] = O((d_2^2/\sigma^2) \log N)$, and the duality identity of Lemma 2 converts that final drift into both the objective gap and the per-constraint violations.

What would settle it

Run Algorithm 2 on a continuous-state MDP (for example Mountain Car) with a fixed set $K$ of sampled constraints, then evaluate the returned weight vector on a fresh held-out set $K'$ of state–action constraints that were never used in training. If the maximum violation on $K'$ stays bounded away from zero while the violation on $K$ converges to zero, or if the violation on $K'$ grows as $K'$ is enlarged, then Theorem 4 holds for the reduced LP but Corollary 1 does not deliver the promised guarantee for the RL problem itself, and the implied policy's gap to the optimal value would fail to shrink like $1/N$.

Watch

Extended reading notes

Core claim

The central claim is an instance-dependent sample-complexity theorem for the LP formulation of RL with linear function approximation. Theorem 4 states that Algorithm 2 returns, within $O(K \log(1/\varepsilon)/\Delta^2 + d_2^2(1 + \lVert A_{J^*,I^*} \rVert_\infty)/\sigma^2 \cdot \log(1/\varepsilon)/\varepsilon)$ samples, a weight vector $\bar{x}_N$ with $V^{\mathrm{ALP}} - r^\top \bar{x}_N \le \varepsilon$ and $A \bar{x}_N - c \le \varepsilon$ for every constraint of the LP, where $K$ is the constraint count, $d_2 \le d_1$ is the size of the optimal basis, $\Delta$ is the smallest gap between the optimal basic solution and any other (non-optimal or infeasible) basic solution, and $\sigma$ is the smallest eigenvalue magnitude of the optimal-basis matrix $A_{J^*,I^*}$. When $\Delta$ and $\sigma$ are bounded away from zero, this is an $O(1/\varepsilon)$ sample complexity, i.e. an instance-dependent $\tilde{O}(1/N)$ suboptimality gap, improving on the $O(1/\sqrt{N})$ worst-case gap previously established for LP-based RL. The theorem also bounds constraint violations on every constraint of the LP, a benefit the authors attribute to working with the identified optimal basis.

Load-bearing premise

The load-bearing premise is that the sampled constraints of the reduced LP stand in for the full value LP: an earlier constraint-sampling theorem bounds the value gap between the two LPs, but nothing in this paper shows the returned weights also satisfy the unsampled constraints, so the promised $O(1/N)$ gap to the true optimal policy is, strictly, a guarantee about the reduced LP.

Editorial extensions

If this is right

  • On favorable instances (fixed $\Delta$ and $\sigma$), the sample complexity to reach $\varepsilon$ suboptimality drops from $O(1/\varepsilon^2)$ to $O(1/\varepsilon)$, i.e. an $\tilde{O}(1/N)$ suboptimality gap after $N$ samples.
  • The number of LP constraints and variables that must be learned is at most the number of basis functions, independent of the state–action space size; in the Mountain Car experiment the RLP shrinks from 12,000 constraints to 25.
  • The guarantee needs no unique optimal basis (non-degeneracy), because the algorithm commits to one identified basis and re-solves only it.
  • Constraint violations are controlled on every constraint of the reduced LP, not only the binding ones, through the non-singularity of $A_{J^*,I^*}$.
  • Empirically the resolving policy reaches about 92.5% success on Mountain Car, roughly 40 points above a non-resolving LP baseline, and matches DQN while using fewer samples in the small-sample regime.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's feasibility guarantee is only for the sampled constraints; lifting it to the full ALP would likely require a margin or Lipschitz condition on the constraint functions, a checkable property of the basis and feature map, and would turn Corollary 1 into a genuine end-to-end $O(1/\varepsilon)$ policy guarantee.
  • The same resolving-while-fixed-basis scheme should transfer to other online LP settings (bandits with knapsacks, network revenue management) where earlier logarithmic-regret results required non-degeneracy; the sub-martingale argument could plausibly yield $O(1/\varepsilon)$ guarantees there as well.
  • The bound predicts a specific degradation: instances with a nearly tied second-best basis (small $\Delta$) or an ill-conditioned basis matrix (small $\sigma$) should need visibly more samples; a computational study that varies $\Delta$ and $\sigma$ across random MDPs would test whether the claimed instance-dependence is real.
  • The success-rate advantage over DQN at small sample counts hints that LP-resolving is data-frugal when function approximation must be learned from few transitions; a second benchmark would show whether the $1/N$ rate holds beyond this single continuous-control example.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper develops an LP-based reinforcement learning algorithm with linear function approximation. It first proposes Algorithm 1 to identify an optimal basis of an empirical ALP/RLP, reducing the number of constraints from K to d2 <= d1 using O(K log(1/epsilon)/Delta^2) samples (Theorem 2). It then proposes Algorithm 2, a resolving scheme that repeatedly solves the d2-by-d2 linear system corresponding to the identified basis, and proves in Theorems 3 and 4 an instance-dependent sample complexity of the form O(K log(1/epsilon)/Delta^2 + d2^2(1+||A_{J*,I*}||_inf)/sigma^2 * log(1/epsilon)/epsilon) for approximating the LP value and satisfying the sampled constraints. Corollary 1 claims an extension to large or infinite state-action spaces with O(((d2^2/sigma^2)+1/Delta^2) log^2(1/epsilon)/epsilon) samples. Numerical experiments on a Mountain Car task compare the resolving algorithm with direct LP solving and DQN.

Significance. If the technical gaps identified below are repaired, this would be a meaningful contribution: it is one of the few LP-based RL algorithms with an instance-dependent bound, and the idea of resolving a fixed optimal basis rather than the whole LP relaxes uniqueness and non-degeneracy conditions common in online LP. The manuscript provides detailed appendices, including perturbation analysis of the linear systems, a martingale concentration argument for the resolving scheme, and a constraint-violation bound for the complement of the identified basis; these substantially support the finite-RLP claims. The numerical study is clearly presented and demonstrates practical convergence behavior. At present, however, the central guarantee is proved for the reduced LP, while the abstract and Corollary 1 claim an RL guarantee for large or infinite state-action spaces; the bridge between these two statements is load-bearing and not supplied.

major comments (4)
  1. [Section 3.1, Algorithm 1, line 17] Algorithm 1, line 17, sets J* = B intersect {indices of slack variables s}, i.e., the basic slack variables of the simplex tableau. In the standard-form LP (7), a basic slack variable corresponds to an inactive constraint with A_j x^* < c_j, whereas Lemma 1 (Eq. (8)) and the subsequent analysis require J* to be the set of active (nonbasic slack) constraints satisfying A_{J*,I*} x^*_{I*} = c_{J*}. Consequently Eq. (15)/(16) in Section 4 is not the system satisfied by the returned J*; in the Mountain Car RLP (K = 12,000, |I*| <= 25) the returned J* would contain roughly 11,975 indices, making the d2-by-d2 linear system in Algorithm 2 ill-posed. The pseudocode as written therefore does not implement the algorithm whose guarantees are proved; the appendices appear to analyze the complementary choice J* = (indices of nonbasic slacks). This must be corrected before Theorems 2-4 can be attributed to Algorithm 1 and Algorithm 2.
  2. [Section 5, Corollary 1, with Section 2.2 and Theorem 1] The extension to large or infinite state-action spaces is not justified. Theorem 1 (De Farias and Van Roy 2004) bounds only the objective gap |V_ALP - V_RLP|; it says nothing about whether a solution that approximately satisfies the K sampled constraints also approximately satisfies the omitted constraints in (S x A)\K. Theorem 4's guarantee A \bar{x} - c <= epsilon is for the K constraints of the RLP, and Appendix F only extends violations to J*^c within that same finite constraint set. Without a bound on violations of unsampled constraints, the value-function approximation error for the original ALP is uncontrolled, so the abstract's claim of an instance-dependent ~O(1/N) suboptimality gap for RL does not follow. Corollary 1 should either be restricted to the RLP, or an additional uniform-convergence/coverage condition over S x A should be stated and used.
  3. [Abstract and Section 5, Theorem 4] The abstract states that the algorithm enjoys an instance-dependent ~O(1/N) suboptimality gap for RL. What Theorem 4 actually proves is a bound on the LP objective gap V_ALP - r^T \bar{x} and on constraint violations for the RLP, not a bound on V^pi - V^* for a policy derived from \bar{x}. Converting an approximately optimal and approximately feasible approximate LP solution into a policy with a suboptimality gap requires additional steps, such as a greedy policy with respect to \Phi \bar{x}, and no policy-extraction argument or associated error bound appears. The guarantee should be described as a value-function approximation error for the ALP/RLP, or the policy-extraction step should be supplied.
  4. [Section 2.2, Theorem 1, and Corollary 1] Theorem 1 is quoted as sampling K independently from S x A, but no sampling distribution is specified. The validity of the constraint-sampling approximation, the resulting definition of Delta, and the constants in Corollary 1 all depend on this distribution (e.g., state-relevance weights or a coverage condition). Without specifying the distribution and any implied concentrability/coverage constants, the corollary's sample-complexity expression is not well defined. The authors should state the distribution used for K and account for it in the statements of Theorem 2 and Corollary 1.
minor comments (4)
  1. [Section 2] The cost function is written as c : S x A -> D[0,1]; the 'D' appears to be a typo and should be c : S x A -> [0,1].
  2. [Section 5, Theorem 3] The theorem statement says 'where the parameters Delta with Delta defined in (12) and sigma defined in (22)', but the displayed bound (23) contains no Delta; clarify that Delta enters only through the regime N >= N0 from Theorem 2 and through the basis-identification probability.
  3. [Appendix D, proof of Lemma 2] The proof says 'noting that x*_{I*} > 0' before applying complementary slackness. This is an implicit non-degeneracy assumption; if zero basic variables are allowed, the argument should be stated in terms of the signs of the basic variables and the complementary-slackness conditions rather than an unqualified strict positivity.
  4. [Section 6.1 and Figure 2] The text says r_epsilon is a pre-specified range and Figure 2 uses r_epsilon = 40, 80, but the state/action discretization has 40, 60, and 5 parts; the relationship between the noise radius and these index units should be clarified to avoid confusion.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular reduction found; the sample-complexity derivation is self-contained and depends on instance parameters, not fitted quantities. The notable J*/basis mismatch is a correctness bug, not circularity.

full rationale

The claimed derivation chain does not reduce any output to an input by construction. Lemma 1 is standard LP basis theory; Theorem 2 identifies the true optimal basis using a Hoeffding/perturbation argument whose threshold Rad(N,epsilon) <= O(Delta) uses the instance gap Delta defined over the LP's basic solutions. Delta and sigma are instance parameters, not fitted from data, and the proof does not assume the target suboptimality gap. Algorithm 2's resolving analysis (Lemmas 2-4, Appendix E) is self-contained: the objective gap is expressed via E[c^N_J*] and then bounded by martingale concentration, with constants depending on sigma, ||A_J*,I*||_inf and d2. No equation is equivalent to a fitted parameter renamed as a prediction. The paper cites the authors' prior resolving idea (Jiang and Ye 2024), but the citation is not load-bearing because the present proof is carried out in the appendix; at most it is a minor self-citation. Separately, the Skeptic's internal-inconsistency concern is real but non-circular: Algorithm 1 line 17 sets J* = B cap {slack variables} (basic slacks), whereas Lemma 1 requires J* to be the nonbasic slacks for which A_J*,I* x*_I* = c_J* holds. For basic slacks, A_j x* = c_j - s_j < c_j, so Eq. (8) generally fails and |J*| = K - |I*|, making the square system (15)/(16) ill-posed. That is a correctness defect in the pseudocode, not a case of a prediction being equivalent to its input, so it does not raise the circularity score.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the generative model, an unquantified function approximation assumption, an unspecified constraint sampling distribution for the infinite-state extension, and the standard non-singularity of the optimal LP basis. The main free parameters are user choices (basis, state-relevance weights, projection bound C), not fitted values.

free parameters (3)
  • C
    Upper bound on 2||x*||, required as input to Algorithm 2; appears in projection step and in N'_0 sample complexity. It is an instance-dependent constant chosen by the user, not fitted to data.
  • basis functions phi_i
    The choice of basis functions is user-specified (Eq. 4) and affects approximation quality; no procedure for selecting them is given.
  • state-relevance weights mu
    The ALP objective (5a) uses mu(s) with positive elements; the choice is an input to the LP formulation.
assumptions (4)
  • domain assumption Generative model (Assumption 1): each query to the model returns an independent next-state sample for a given (s,a).
    Used throughout to construct unbiased estimates of A and to enable Hoeffding bounds.
  • domain assumption The value function V* is well approximated by the span of the basis functions Phi w (Eq. 4); no approximation error bound is given.
    The analysis bounds the gap to the LP optimum, not to V*, so the function approximation error is an unquantified source of suboptimality.
  • ad hoc to paper For the RLP, the sampled constraint set K is drawn i.i.d. from some distribution over S x A (Theorem 1); the distribution is not specified.
    Corollary 1 relies on Theorem 1's sampling bound but does not state the sampling distribution or how it should be chosen.
  • standard math The optimal basis matrix A_{J*,I*} is non-singular and the LP gaps Delta and sigma are positive.
    Non-singularity follows from LP basis theory; for the finite RLP the set of basic solutions is finite so the minimum gap Delta is positive unless the LP is degenerate to the point of triviality.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Resolving Methods for Reinforcement Learning with Function Approximations." pith.science (2026). https://pith.science/paper/DMSAIUCG

@misc{pith2026250512037,
  author       = {Pith},
  title        = {Pith review of: Adaptive Resolving Methods for Reinforcement Learning with Function Approximations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DMSAIUCG}},
  note         = {Machine review of arXiv:2505.12037}
}
abstract

Reinforcement learning (RL) problems are fundamental in online decision-making and have been instrumental in finding an optimal policy for Markov decision processes (MDPs). Function approximations are usually deployed to handle large or infinite state-action space. In our work, we consider the RL problems with function approximation and we develop a new algorithm to solve it efficiently. Our algorithm is based on the linear programming (LP) reformulation and it resolves the LP at each iteration improved with new data arrival. Such a resolving scheme enables our algorithm to achieve an instance-dependent sample complexity guarantee, more precisely, when we have $N$ data, the output of our algorithm enjoys an instance-dependent $\tilde{O}(1/N)$ suboptimality gap. In comparison to the $O(1/\sqrt{N})$ worst-case guarantee established in the previous literature, our instance-dependent guarantee is tighter when the underlying instance is favorable, and the numerical experiments also reveal the efficient empirical performances of our algorithms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

73 extracted references · 58 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address author booktitle chapter doi edition editor eid howpublished institution isbn issn journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in "" FUNCTION format.date year ...

  3. [3]

    Agrawal, Z

    S. Agrawal, Z. Wang, and Y. Ye. A dynamic near-optimal algorithm for online linear programming. Operations Research, 62 0 (4): 0 876--890, 2014

    work page 2014

  4. [4]

    Al-Marjani, A

    A. Al-Marjani, A. Tirinzoni, and E. Kaufmann. Towards instance-optimality in online pac reinforcement learning. arXiv preprint arXiv:2311.05638, 2023

    arXiv 2023

  5. [5]

    M. Alvo, D. Russo, and Y. Kanoria. Neural inventory control in networks via hindsight differentiable policy optimization. arXiv preprint arXiv:2306.11246, 2023

    arXiv 2023

  6. [6]

    R. Ao, J. Jiang, and D. Simchi-Levi. Learning to price with resource constraints: From full information to machine-learned prices. arXiv preprint arXiv:2501.14155, 2025

    arXiv 2025

  7. [7]

    Arlotto and X

    A. Arlotto and X. Xie. Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards. Stochastic Systems, 10 0 (2): 0 170--191, 2020

    work page 2020

  8. [8]

    K. P. Badrinath and D. Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning, pages 511--520. PMLR, 2021

    work page 2021

Show all 73 references
  1. [9]

    Banerjee and D

    S. Banerjee and D. Freund. Good prophets know when the end is near. Management Science, 2024

    2024

  2. [10]

    Buchbinder and J

    N. Buchbinder and J. Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34 0 (2): 0 270--286, 2009

    2009

  3. [11]

    Bumpensanti and H

    P. Bumpensanti and H. Wang. A re-solving heuristic with uniformly bounded loss for network revenue management. Management Science, 66 0 (7): 0 2993--3009, 2020

    2020

  4. [12]

    Chen and N

    J. Chen and N. Jiang. Information-theoretic considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042--1051. PMLR, 2019

    2019

  5. [13]

    Chen and N

    J. Chen and N. Jiang. Offline reinforcement learning under value and density-ratio realizability: the power of gaps. In Uncertainty in Artificial Intelligence, pages 378--388. PMLR, 2022

    2022

  6. [14]

    Cheng, T

    C.-A. Cheng, T. Xie, N. Jiang, and A. Agarwal. Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning, pages 3852--3878. PMLR, 2022

    2022

  7. [15]

    C. Dann, L. Li, W. Wei, and E. Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507--1516. PMLR, 2019

    2019

  8. [16]

    D. P. De Farias and B. Van Roy. The linear programming approach to approximate dynamic programming. Operations research, 51 0 (6): 0 850--865, 2003

    2003

  9. [17]

    D. P. De Farias and B. Van Roy. On constraint sampling in the linear programming approach to approximate dynamic programming. Mathematics of operations research, 29 0 (3): 0 462--478, 2004

    2004

  10. [18]

    T. S. Ferguson. Who solved the secretary problem? Statistical science, 4 0 (3): 0 282--289, 1989

    1989

  11. [19]

    Gallego and G

    G. Gallego and G. Van Ryzin. A multiproduct dynamic pricing problem and its applications to network yield management. Operations research, 45 0 (1): 0 24--41, 1997

    1997

  12. [20]

    Z. D. Guo, S. Doroudi, and E. Brunskill. A pac rl algorithm for episodic pomdps. In Artificial Intelligence and Statistics, pages 510--518. PMLR, 2016

    2016

  13. [21]

    Gupta and M

    A. Gupta and M. Molinaro. How experts can solve lps online. In European Symposium on Algorithms, pages 517--529. Springer, 2014

    2014

  14. [22]

    J. He, D. Zhou, and Q. Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference on Machine Learning, pages 4171--4180. PMLR, 2021

    2021

  15. [23]

    J. He, H. Zhao, D. Zhou, and Q. Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. In International Conference on Machine Learning, pages 12790--12822. PMLR, 2023

    2023

  16. [24]

    N. J. Higham. Accuracy and stability of numerical algorithms. SIAM, 2002

    2002

  17. [25]

    Huang, H

    J. Huang, H. Zhong, L. Wang, and L. Yang. Tackling heavy-tailed rewards in reinforcement learning with function approximation: Minimax optimal and instance-dependent regret bounds. Advances in Neural Information Processing Systems, 36, 2024

    2024

  18. [26]

    S. Jasin. Reoptimization and self-adjusting price control for network revenue management. Operations Research, 62 0 (5): 0 1168--1178, 2014

    2014

  19. [27]

    Jasin and S

    S. Jasin and S. Kumar. A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Mathematics of Operations Research, 37 0 (2): 0 313--345, 2012

    2012

  20. [28]

    Jiang and Y

    J. Jiang and Y. Ye. Achieving \ o (1/ ) sample complexity for constrained markov decision process. CoRR, 2024

    2024

  21. [29]

    Jiang, W

    J. Jiang, W. Ma, and J. Zhang. Degeneracy is ok: Logarithmic regret for network revenue management with indiscrete distributions. Operations Research, 2025

    2025

  22. [30]

    C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018

    2018

  23. [31]

    Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline rl? In International Conference on Machine Learning, pages 5084--5096. PMLR, 2021

    2021

  24. [32]

    o nnis, K. Radke, and B. V \

    T. Kesselheim, A. T \"o nnis, K. Radke, and B. V \"o cking. Primal beats dual on online packing lps in the random-order model. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 303--312, 2014

    2014

  25. [33]

    Y. Kim, I. Yang, and K.-S. Jun. Improved regret analysis for variance-adaptive linear bandits and horizon-free linear mixture mdps. arXiv preprint arXiv:2111.03289, 2021

    2021 arXiv

  26. [34]

    Kober, J

    J. Kober, J. A. Bagnell, and J. Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32 0 (11): 0 1238--1274, 2013

    2013

  27. [35]

    G. Li, L. Shi, Y. Chen, Y. Chi, and Y. Wei. Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, 52 0 (1): 0 233--260, 2024

    2024

  28. [36]

    Li and Q

    X. Li and Q. Sun. Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards. arXiv preprint arXiv:2303.05606, 2023

    2023 arXiv

  29. [37]

    Li and Y

    X. Li and Y. Ye. Online linear programming: Dual convergence, new algorithms, and regret bounds. Operations Research, 70 0 (5): 0 2948--2966, 2022

    2022

  30. [38]

    X. Li, C. Sun, and Y. Ye. The symmetry between arms and knapsacks: A primal-dual approach for bandits with knapsacks. In International Conference on Machine Learning, pages 6483--6492. PMLR, 2021

    2021

  31. [39]

    Y. Liu, A. Swaminathan, A. Agarwal, and E. Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Advances in neural information processing systems, 33: 0 1264--1274, 2020

    2020

  32. [40]

    W. Ma, Y. Cao, D. H. Tsang, and D. Xia. Optimal regularized online convex allocation by adaptive re-solving. arXiv preprint arXiv:2209.00399, 2022

    2022 arXiv

  33. [41]

    Mehta, A

    A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. Adwords and generalized online matching. Journal of the ACM (JACM), 54 0 (5): 0 22--es, 2007

    2007

  34. [42]

    M \'e nard, O

    P. M \'e nard, O. D. Domingues, A. Jonsson, E. Kaufmann, E. Leurent, and M. Valko. Fast active learning for pure exploration in reinforcement learning. arXiv preprint arXiv:2007.13442, 2020

    2007 arXiv

  35. [43]

    V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013

    2013 arXiv

  36. [44]

    Molinaro and R

    M. Molinaro and R. Ravi. The geometry of online packing linear programs. Mathematics of Operations Research, 39 0 (1): 0 46--59, 2014

    2014

  37. [45]

    R. Munos. Error bounds for approximate policy iteration. In ICML, volume 3, pages 560--567. Citeseer, 2003

    2003

  38. [46]

    Munos and C

    R. Munos and C. Szepesv \'a ri. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9 0 (5), 2008

    2008

  39. [47]

    A. E. Ozdaglar, S. Pattathil, J. Zhang, and K. Zhang. Revisiting the linear-programming framework for offline rl with general function approximation. In International Conference on Machine Learning, pages 26769--26791. PMLR, 2023

    2023

  40. [48]

    M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 1994

    1994

  41. [49]

    Rashidinejad, B

    P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34: 0 11702--11716, 2021

    2021

  42. [50]

    Rashidinejad, H

    P. Rashidinejad, H. Zhu, K. Yang, S. Russell, and J. Jiao. Optimal conservative offline rl with general function approximation via augmented lagrangian. arXiv preprint arXiv:2211.00716, 2022

    2022 arXiv

  43. [51]

    Reemtsen

    R. Reemtsen. Semi-infinite programming: discretization methods. 2001

    2001

  44. [52]

    Scherrer

    B. Scherrer. Performance bounds for policy iteration and application to the game of tetris. Journal of Machine Learning Research, 14 0 (4), 2013

    2013

  45. [53]

    Scherrer

    B. Scherrer. Approximate policy iteration schemes: A comparison. In International Conference on Machine Learning, pages 1314--1322. PMLR, 2014

    2014

  46. [54]

    Shani, D

    G. Shani, D. Heckerman, R. I. Brafman, and C. Boutilier. An mdp-based recommender system. Journal of Machine Learning Research, 6 0 (9), 2005

    2005

  47. [55]

    Simchowitz and K

    M. Simchowitz and K. G. Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019

    2019

  48. [56]

    Swietanowski

    A. Swietanowski. Simplex v. 2.17: an implementation of the simplex algorithm for large scale linear problems. user's guide. 1994

    1994

  49. [57]

    Uehara and W

    M. Uehara and W. Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXiv:2107.06226, 2021

    2021 arXiv

  50. [58]

    S. A. Vavasis and Y. Ye. Identifying an optimal basis in linear programming. Annals of Operations Research, 62 0 (1): 0 565--572, 1996

    1996

  51. [59]

    Vera and S

    A. Vera and S. Banerjee. The bayesian prophet: A low-regret framework for online decision making. Management Science, 67 0 (3): 0 1368--1391, 2021

    2021

  52. [60]

    Wagenmaker and K

    A. Wagenmaker and K. G. Jamieson. Instance-dependent near-optimal policy identification in linear mdps via online experiment design. Advances in Neural Information Processing Systems, 35: 0 5968--5981, 2022

    2022

  53. [61]

    A. J. Wagenmaker, Y. Chen, M. Simchowitz, S. Du, and K. Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In International Conference on Machine Learning, pages 22384--22429. PMLR, 2022 a

    2022

  54. [62]

    A. J. Wagenmaker, M. Simchowitz, and K. Jamieson. Beyond no regret: Instance-dependent pac reinforcement learning. In Conference on Learning Theory, pages 358--418. PMLR, 2022 b

    2022

  55. [63]

    Y. Wei, J. Xu, and S. H. Yu. Constant regret primal-dual policy for multi-way dynamic matching. In Abstract Proceedings of the 2023 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 79--80, 2023

    2023

  56. [64]

    Xie and N

    T. Xie and N. Jiang. Batch value-function approximation with only realizability. In International Conference on Machine Learning, pages 11404--11413. PMLR, 2021

    2021

  57. [65]

    Xie, C.-A

    T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34: 0 6683--6694, 2021

    2021

  58. [66]

    Y. Ye. The simplex and policy-iteration methods are strongly polynomial for the markov decision problem with a fixed discount rate. Mathematics of Operations Research, 36 0 (4): 0 593--603, 2011

    2011

  59. [67]

    Zanette, D

    A. Zanette, D. Brandfonbrener, E. Brunskill, M. Pirotta, and A. Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954--1964. PMLR, 2020

    1954

  60. [68]

    Zanette, M

    A. Zanette, M. J. Wainwright, and E. Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in neural information processing systems, 34: 0 13626--13640, 2021

    2021

  61. [69]

    W. Zhan, B. Huang, A. Huang, N. Jiang, and J. Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pages 2730--2775. PMLR, 2022

    2022

  62. [70]

    Zhang, J

    Z. Zhang, J. Yang, X. Ji, and S. S. Du. Improved variance-aware confidence sets for linear bandits and linear mixture mdp. Advances in Neural Information Processing Systems, 34: 0 4342--4355, 2021

    2021

  63. [71]

    Zhou and Q

    D. Zhou and Q. Gu. Computationally efficient horizon-free reinforcement learning for linear mixture mdps. Advances in neural information processing systems, 35: 0 36337--36349, 2022

    2022

  64. [72]

    D. Zhou, Q. Gu, and C. Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532--4576. PMLR, 2021

    2021

  65. [73]

    H. Zhu, P. Rashidinejad, and J. Jiao. Importance weighted actor-critic for optimal conservative offline reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024

    2024

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.