Pith. sign in

REVIEW 5 major objections 8 minor 33 references

Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs

T0 review · 5 major / 8 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper claims that two variants of LSVI-UCB that alternate learning and non-learning episodes reduce space and time usage while keeping regret sublinear.

desk verdict A modest but plausible fixed-reset result and a genuinely new adaptive scheme whose only theoretical support is built on a false equality; the paper deserves referee time but not acceptance as-is. read the letter →

arxiv 2411.10906 v1 pith:IQKTB46Q submitted 2024-11-16 cs.LG cs.DS

Philips George John , Arnab Bhattacharyya , Silviu Maniu , Dimitrios Myrisiotis , Zhenan Wu This is my paper · ORCID
classification cs.LGcs.DS
keywords linearMDPsLSVI-UCBonlinereinforcementlearningregretboundsspaceefficiencymemory-constrainedadaptiveintervalsfunctionapproximation
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

LSVI-UCB is one of the few online reinforcement learning algorithms with formal regret guarantees for linear MDPs, but it stores data from every episode, so memory grows linearly in the episode count $K$. This paper proposes two variants that deliberately stop learning for stretches of episodes and discard accumulated samples. The fixed-interval variant resets the workspace every $K^{\rho}$ episodes and is proved to use space $O_d(|A| K^{\rho})$ and time $O_d(|A| K^{1+\rho})$ while keeping regret at $\tilde O_d(K^{1-\rho/2})$; the adaptive variant learns only when a cheap matrix-change test fires, and is proved to use space $O_d(|A| \mathrm{Budget})$ and time $O_d(|A| K \mathrm{Budget})$, with experiments showing regret close to the original. The payoff is a tunable space-versus-regret trade-off that could make provable RL algorithms usable where memory is scarce.

What carries the argument

The load-bearing mechanism is the workspace reset combined with the fact that LSVI-UCB's regression step needs only the current covariance matrix and the stored feature-reward pairs. The fixed variant caps the number of stored samples by resetting every $K^{\rho}$ episodes, and Sherman-Morrison rank-one updates keep covariance inverses current without recomputation. The adaptive variant's central object is its Learn trigger (Equation 1), which compares inverse covariance matrices from the last $m$ episodes in Frobenius norm and skips learning when they have not moved by at least $\tau$; the paper argues that convergence of these inverse matrices in operator norm implies the learned $Q$-function stays close to the one LSVI-UCB would have produced, and proves such convergence under a fixed-state-distribution and independent-Gaussian-feature assumption.

What would settle it

Run LSVI-UCB-Adaptive with Budget $K^{0.5}$ on a linear MDP that satisfies Definition 2 but whose initial states are chosen adversarially so that Equation (1) rarely fires; if regret is linear in $K$ while space stays sublinear, the Learn trigger is not a valid proxy for regret.

Watch

Extended reading notes

Core claim

The paper's central claim is that LSVI-UCB's memory bottleneck can be removed by alternating short learning phases with phases in which the agent only executes its latest policy and stores nothing. The first algorithm, LSVI-UCB-Fixed, resets all accumulated data every $K^{\rho}$ episodes; over $K$ episodes this gives space $O_d(|A| K^{\rho})$, time $O_d(|A| K^{1+\rho})$, and regret $\tilde O_d(K^{1-\rho/2})$ with constant probability, interpolating between the original algorithm's linear memory and a much smaller footprint. The second algorithm, LSVI-UCB-Adaptive, keeps a rolling window of the last $m$ inverse covariance matrices and learns only when the maximum Frobenius-norm difference among them crosses a threshold $\tau$, subject to a per-phase budget on learning episodes; the paper proves space $O_d(|A| \mathrm{Budget})$ and time $O_d(|A| K \mathrm{Budget})$, and reports that on synthetic linear MDPs and linearized Atari RAM environments its regret is experimentally indistinguishable from LSVI-UCB. The fixed variant's regret bound is proved; the adaptive variant's regret claim is experimental rather than proved.

Load-bearing premise

The adaptive variant's savings depend on the assumption that a small change in the regression matrix used by the algorithm means it can safely skip learning; this is proved only in a special setting where states come from a fixed distribution and features are independent Gaussian draws.

Editorial extensions

If this is right

  • Setting $\rho=1/2$ in LSVI-UCB-Fixed gives space $O_d(|A| \sqrt{K})$ and time $O_d(|A| K^{3/2})$ with regret $\tilde O_d(K^{3/4})$, a concrete memory-regret knob for deployments.
  • The adaptive variant decouples memory from total episode count: space remains within $O_d(|A| \mathrm{Budget})$ no matter how long the agent runs, once the budget and lookback window are fixed.
  • On linearized Atari RAM environments, both variants completed 500 episodes while the baseline LSVI-UCB was stopped at 280 because of time and memory, suggesting the approach transfers beyond synthetic MDPs.
  • If the adaptive variant's regret is truly close to LSVI-UCB, provable RL becomes usable on embedded or low-power devices where linear-in-$K$ memory is infeasible.

Reading between the lines

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

  • The same learn-skip-reset pattern could be applied to other regression-based RL algorithms that maintain a design or covariance matrix, provided a cheap error proxy exists; this is our inference, not a paper claim.
  • A natural next step the paper leaves implicit is a regret bound for LSVI-UCB-Adaptive under assumptions weaker than its fixed-distribution and Gaussian-feature assumptions; without such a bound the adaptive variant's practical claim rests on the reported experiments.
  • The Learn trigger itself could be made cheaper by using a sketched or spectral approximation of the inverse-covariance difference instead of exact Frobenius norms; we offer that as a testable extension.
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

5 major / 8 minor

Summary. The paper proposes two memory-reduced variants of LSVI-UCB (Jin et al., 2023) for episodic linear MDPs. LSVI-UCB-Fixed (Algorithm 2) partitions episodes into phases of length K^rho and resets the regression workspace at each phase boundary; Proposition 6 claims time O_d(|A|K^{1+rho}), space O_d(|A|K^rho), and regret ~O_d(K^{1-rho/2}). LSVI-UCB-Adaptive (Algorithm 3) performs the ridge-regression update only when a trigger (Eq. (1)) detects sufficient change in the inverse covariance and when per-step budget and phase counters allow; Proposition 8 claims time O_d(|A|K*Budget) and space O_d(|A|Budget), and Section 5 claims experimentally that its regret is indistinguishable from LSVI-UCB. Proposition 7, proved in Appendix A, is the adaptive variant's only theoretical support: it asserts that operator-norm convergence of the inverse covariance sequence implies closeness of the learned Q-function to LSVI-UCB's Q-function. Experiments on a synthetic linear MDP and on two CTRL-linearized Atari environments (Alien, Phoenix) compare regret, space, and running time with LSVI-UCB.

Significance. Proportionate to its claims, the paper would be useful: replacing LSVI-UCB's O(|A|K) memory with O(|A|K^rho) at a K^{rho/2} regret penalty is a natural and practically motivated trade-off, and the CTRL linearization of Atari environments is a valuable experimental contribution. The manuscript is honest in important places: Assumptions 19-20 are stated explicitly in Appendix A, and Remark 9 concedes that linear MDP feature maps need not exist for arbitrary benchmarks. These strengths do not offset the central gap: the adaptive variant, which accounts for one of the paper's two main contributions, has no regret theorem, and the proof of its only theoretical justification (Proposition 7) is invalid at a specific step (Corollary 17), as detailed below. The abstract's statement that both variants maintain sublinear regret is therefore unsupported, and I do not see a local repair: validating the adaptive variant's regret claim requires either a new analysis or an honest demotion of that claim.

major comments (5)
  1. [Appendix A.3.1, Corollary 17] Corollary 17's assertion that "By construction of Algorithm 3, we have bQ_{h,k} = bQ_{h,k'} = Q_{h,k'}" is false. Algorithm 3 (lines 12-16) computes bQ_h by ridge regression over the set I_h of prior learning episodes only, whereas Algorithm 1 (lines 5-9) regresses over episodes 1,...,k'-1; as soon as one episode in the phase is non-learning, I_h is a proper subset and the regression weights differ. Moreover, if layers h+1,...,H did not learn in episode k, the target values max_a Q_{h+1}(s_{h+1,i},a) in line 14 come from an older stored Q-function, so a 'learning' episode of Algorithm 3 does not reproduce LSVI-UCB's update. Lemmas 15-16 bound the drift of LSVI-UCB's own Q sequence and cannot transfer to the subset-based bQ; the claimed equality conflates the two regression sets. Since Corollary 17 is the only bridge from the adaptive algorithm's value function to LSVI-UCB's, Proposition 7's first clause is unproved. The proof of Lemma 15 additionally relies on informal '=F' substitutions (replacing a k-term sum by k*Sigma and setting lambda = o(1)) that need norm bounds to be verifiable.
  2. [Section 4.3, Proposition 7; Abstract] Algorithm 3 has no regret theorem. Even if Proposition 7's pointwise-closeness conclusion were correct, it would not imply a sublinear regret bound for Algorithm 3: the executed policy is greedy with respect to a stale, non-optimistic Q-function, and the appendix supplies no optimism, bonus, or eluder-type argument converting closeness into regret. The manuscript effectively concedes this: Section 1.1 and Section 4.3 describe the adaptive variant's regret only as 'within reasonable bounds' and 'indistinguishable' empirically, and Proposition 8 is only a time/space statement. The abstract's claim that the two modifications maintain sublinear regret, and the conclusion's phrase 'provably space efficient variants... perform well in terms of accumulated regret,' overstate what is proved.
  3. [Appendix A.3.2, Assumptions 19 and 20] Proposition 21, and hence the formal content of Proposition 7, holds only under Assumptions 19-20, which are not part of the linear MDP model of Definition 2 and are partially incompatible with it. Assumption 19 sets Ph(s,a) = pS for all (s,a), so transitions no longer depend on the state or action; Assumption 20 makes the features independent Gaussian draws, whereas in a linear MDP phi is a fixed feature map. Lemmas 14-16 and Theorem 13 likewise presuppose Gaussianity. The appendix should state plainly that the convergence result concerns a random-feature, action-independent model; as written, Proposition 7 is presented as supporting Algorithm 3 in the standard linear MDP setting, which it does not.
  4. [Section 4.2, Proposition 6 and Algorithm 2] The fixed variant's analysis is a sketch at a load-bearing point. The claim that each phase incurs ~O_d(sqrt(K^rho)) regret 'by the correctness of LSVI-UCB for K^rho episodes' requires (i) a formal identification of each phase with an LSVI-UCB run of length K^rho against adaptively chosen initial states and (ii) a union bound over the K^{1-rho} phases; both are plausible but not given. In addition, Algorithm 2's pseudocode executes the reset (line 19, 'Delete the working space; I_h := empty') at episode k = K0 + K^rho before the action-selection loop (lines 21-24) of that same episode, so the policy executed at reset episodes is undefined; the regret accounting must specify which Q-function is used then.
  5. [Section 5.3-5.4] The empirical claim that the adaptive variant's regret is 'indistinguishable' from LSVI-UCB's is the only evidence for that variant's regret behavior, but it is presented without supporting statistics: Figures 1, 6, and 7 show single runs on log-scale axes, with no error bars, no multiple seeds, and no statistical test. There is also a factual inconsistency: Section 5.4 states 'We have stopped LSVI-UCB algorithm at K = 280,' yet Table 1 and Table 2 list Phoenix LSVI-UCB values at K = 500 (reward 50306.24, space 2.054 GiB). The experimental section needs to resolve this and report variance.
minor comments (8)
  1. [Corollary 17, Appendix A.3.1] The hypothesis reads 'If Algorithm 2 converges at sqrt(K)' although the statement concerns Algorithm 3; the surrounding text also alternates between the two algorithms, which impedes verification.
  2. [Section 4.2, Proposition 6 sketch] The phase counting in the proof sketch (K^{1-rho} intervals, each of length K^rho) is off by one episode because the reset occurs at k = K0 + K^rho rather than after action selection; the off-by-one is harmless asymptotically but should be made consistent with the pseudocode.
  3. [Section 3.1] The symbol r_h denotes both a distribution over [0,1] and the scalar expected reward (Definition 2 versus the definition of Q^pi_h); the notation should be disambiguated.
  4. [Section 4.3, Algorithm 3 parameters] No guidance is given for setting m and tau consistently with any guarantee, and the reader should be told explicitly that in the absence of a regret theorem these triggers are heuristics; a one-sentence disclaimer would make the contribution's scope clear.
  5. [Lemma 11, Appendix A.2] The statement that the resampled distribution 'is the same as the distribution D' is only true marginally; the proof establishes that the m samples are i.i.d. from D with probability at least 1 - delta, which is what should be stated.
  6. [Remark 9] The relevance of [HO23], a paper on multinomial logistic function approximation, to the claimed non-existence of inducing feature maps should be spelled out, or the remark should cite a directly relevant reference.
  7. [Algorithm 3, lines 21-24] The reset deletes 'the working space' but the Learn trigger needs the stored window L^{-1}_{h,k-m},...,L^{-1}_{h,k} of full-history matrices; the pseudocode should specify precisely which data survive a reset.
  8. [Proposition 6] The regime of rho should be stated: sublinearity of regret requires rho < 2, whereas the advertised space saving requires rho < 1, and the proposition's usefulness depends on rho in (0,1).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the fixed variant inherits external LSVI-UCB bounds, and the adaptive variant's theoretical gap is a soundness issue, not a circular reduction.

full rationale

The paper's main theoretical result, Proposition 6, is derived by partitioning K episodes into independent intervals of length K^rho and invoking the external Jin et al. LSVI-UCB regret bound on each interval; the space and time bounds are direct counting arguments. No fitted parameter is renamed as a prediction, and no load-bearing step reduces to a self-citation. The adaptive variant's Proposition 7 is supported in Appendix A by an argument containing a false 'by construction' identification between Algorithm 3's subset-based Q-function and LSVI-UCB's full-history Q-function (Corollary 17), and the paper itself concedes that Assumptions 19-20 are not part of the linear MDP definition and provides no regret bound for Algorithm 3. This is a correctness/completeness defect, not circularity: the missing step is not equivalent to an input of the derivation, and no claim is forced by self-citation or by definition. The experimental claims are empirical comparisons against LSVI-UCB and are not circular. Therefore no circular step meeting the evidentiary standard is present, and the appropriate score is 0.

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

The fixed variant rests on the assumption that each reset phase can be treated as an independent LSVI-UCB run. The adaptive variant's only theoretical support, Proposition 7, requires state sampling independent of actions and i.i.d. Gaussian features, which are not properties of linear MDPs; no regret bound for Algorithm 3 is derived. The paper introduces no new physical or mathematical entities; all extra structure is inherited from LSVI-UCB and representation learning.

free parameters (4)
  • rho (phase length exponent) = 0.5 to 0.75 in experiments
    Controls the reset frequency K^rho; directly sets the space and regret trade-off in Proposition 6. Chosen by hand, not derived.
  • Budget exponent c (Budget = K^c) = c in [0.5, 0.75]
    Sets the maximum number of learning episodes in each phase for Algorithm 3; determines the space and time bounds in Proposition 8.
  • m (lookback window) = 10 to 50
    Window length in the Learn trigger (Equation 1); affects storage and trigger sensitivity.
  • tau_c (Learn threshold scalar) = tau_c = 0.1 in linearized experiments, scaled as tau_c * d^2
    Threshold for when projection-matrix deviation triggers learning; hand-chosen with no sensitivity analysis or error bars.
assumptions (4)
  • domain assumption Each reset phase of Algorithm 2 can be analyzed as an independent fresh run of LSVI-UCB, so the per-phase regret bound eO_d(sqrt(K^rho)) sums over K^(1-rho) phases.
    Used in the Proposition 6 proof sketch; not formally proven, and the interaction between phases through adversary-chosen initial states is not addressed.
  • ad hoc to paper Assumption 19: the state s_{h,k} is sampled from a fixed distribution p_S on S independent of the action, and when S is finite ||p_S||_2^2 <= 1/T^4.
    Needed in Appendix A.3.2 for convergence of the inverse covariance matrices; it excludes general linear MDPs and contradicts the transition dynamics of an MDP.
  • ad hoc to paper Assumption 20: for each state-action pair, the feature vector phi(s,a) is drawn independently from a non-degenerate Gaussian N(0,Sigma) with lambda_min(Sigma) = c_min > 0.
    Used in Lemma 14 and Proposition 21; not satisfied by controlled exploration in linear MDPs, where features are chosen by the learner, not sampled from a fixed Gaussian.
  • ad hoc to paper Appendix A.3 assumes H, Tr(Sigma), and norm of Sigma^{-1} are O_d(1), and sets lambda = o(1).
    These are declared as natural assumptions in the appendix but are additional restrictions not implied by the linear MDP definition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs." pith.science (2026). https://pith.science/paper/IQKTB46Q

@misc{pith2026241110906,
  author       = {Pith},
  title        = {Pith review of: Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IQKTB46Q}},
  note         = {Machine review of arXiv:2411.10906}
}
read the original abstract

Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomial-time reinforcement learning algorithm (namely, LSVI-UCB) for the setting of linear Markov decision processes, and provided theoretical guarantees regarding its running time and regret. In real-world scenarios, however, the space usage of this algorithm can be prohibitive due to a utilized linear regression step. We propose and analyze two modifications of LSVI-UCB, which alternate periods of learning and not-learning, to reduce space and time usage while maintaining sublinear regret. We show experimentally, on synthetic data and real-world benchmarks, that our algorithms achieve low space usage and running time, while not significantly sacrificing regret.

Figures

Figures reproduced from arXiv: 2411.10906 by the authors.

Figure 1
Figure 1. Synthetic data: Regret curve. We get empirical verification of this on synthetic data, as well as an idea of the substantial improvement in the sizes of the data structures ( [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Synthetic data: Space usage. 0 1000 2000 3000 4000 5000 6000 7000 8000 K (Episode #) 1 0 1 2 Log-scale Process Time (log minutes) Process Time Curves LSVI-UCB (Baseline) LSVI-UCB-Fixed LSVI-UCB-Adaptive [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 3
Figure 3. Synthetic data: Running time. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Synthetic data: Space usage of LSVI-UCB-Fixed as a function of parameters. 0 1000 2000 3000 4000 5000 K (Episode #) 20 40 60 80 100 120 Space Usage (MiB) Space Usage Curves Adaptive m = 10, budget = K 0.5 , K = K 0.5 Adaptive m = 50, budget = K 0.5 , K = K 0.75 Adaptiv…
Figure 5
Figure 5. Figure 5: Synthetic data: Space usage of LSVI-UCB-Adaptive as a function of parameters. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Synthetic data: Regret of LSVI-UCB-Fixed as a function of parameters. 0 1000 2000 3000 4000 5000 K (Episode #) 1.75 2.00 2.25 2.50 2.75 3.00 3.25 3.50 Log-scale Regret Regret Curves Adaptive m = 10, budget = K 0.5 , K = K 0.5 Adaptive m = 50, budget = K 0.5 , K = K 0.7…
Figure 7
Figure 7. Figure 7: Synthetic data: Regret of LSVI-UCB-Adaptive as a function of parameters. 26 [PITH_FULL_IMAGE:figures/full_fig_p026_7.png]
Figure 8
Figure 8. Figure 8: Synthetic data: Process time of LSVI-UCB-Fixed as a function of parameters. 0 1000 2000 3000 4000 5000 K (Episode #) 1.0 0.5 0.0 0.5 1.0 1.5 Log-scale Process Time (log minutes) Process Time Curves Adaptive m = 10, budget = K 0.5 , K = K 0.5 Adaptive m = 50, budget = K…
Figure 9
Figure 9. Figure 9: Synthetic data: Process time of LSVI-UCB-Adaptive as a function of parameters. 27 [PITH_FULL_IMAGE:figures/full_fig_p027_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 28 canonical work pages

  1. [1]

    Near-optimal regret bounds for reinforcement learning

    Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and L \' e on Bottou, editors, Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia,...

    work page 2008

  2. [2]

    Modular multitask reinforcement learning with policy sketches

    Jacob Andreas, Dan Klein, and Sergey Levine. Modular multitask reinforcement learning with policy sketches. In ICML 2017 , volume 70 of Proceedings of Machine Learning Research , pages 166--175, 2017

    work page 2017

  3. [3]

    Litvak, Alain Pajor, and Nicole Tomczak-Jaegermann

    Radosław Adamczak, Alexander E. Litvak, Alain Pajor, and Nicole Tomczak-Jaegermann. Sharp bounds on the rate of convergence of the empirical covariance matrix, 2012

    work page 2012

  4. [4]

    Logarithmic online regret bounds for undiscounted reinforcement learning

    Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning. In Bernhard Sch \" o lkopf, John C. Platt, and Thomas Hofmann, editors, Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, D...

    work page 2006

  5. [5]

    Bellemare, Joel Veness, and Michael Bowling

    Marc G. Bellemare, Joel Veness, and Michael Bowling. Sketch-based linear value function approximation. In Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012 , pages 2222--2230, 2012

    work page 2012

  6. [6]

    Vallis, Bruno Lacerda, and Nick Hawes

    Paul Duckworth, Katherine A. Vallis, Bruno Lacerda, and Nick Hawes. Reinforcement learning for bandits with continuous actions and large context spaces. In ECAI 2023, Including (PAIS 2023) , volume 372 of Frontiers in Artificial Intelligence and Applications , pages 590--597, 2023

    work page 2023

  7. [7]

    Towards deployment-efficient reinforcement learning: Lower bound and optimality

    Jiawei Huang, Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie - Yan Liu. Towards deployment-efficient reinforcement learning: Lower bound and optimality. In ICLR 2022 , 2022

    work page 2022

  8. [8]

    Model-based reinforcement learning with multinomial logistic function approximation

    Taehyun Hwang and Min - hwan Oh. Model-based reinforcement learning with multinomial logistic function approximation. In Brian Williams, Yiling Chen, and Jennifer Neville, editors, AAAI 2023, IAAI 2023, EAAI 2023 , pages 7971--7979, 2023

    work page 2023

Show all 33 references
  1. [9]

    Nearly minimax optimal reinforcement learning for linear markov decision processes

    Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. In ICML 2023 , volume 202 of Proceedings of Machine Learning Research , pages 12790--12822, 2023

    2023

  2. [10]

    Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I. Jordan. Provably efficient reinforcement learning with linear function approximation. Math. Oper. Res. , 48(3):1496--1521, 2023

    2023

  3. [11]

    Sample-efficient reinforcement learning is feasible for linearly realizable mdps with limited revisiting

    Gen Li, Yuxin Chen, Yuejie Chi, Yuantao Gu, and Yuting Wei. Sample-efficient reinforcement learning is feasible for linearly realizable mdps with limited revisiting. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Sys...

    2021

  4. [12]

    Reinforcement learning and bandits for speech and language processing: Tutorial, review and outlook

    Baihan Lin. Reinforcement learning and bandits for speech and language processing: Tutorial, review and outlook. Expert Syst. Appl. , 238(Part E ):122254, 2024

    2024

  5. [13]

    Bandit Algorithms , 2020

    Tor Lattimore and Csaba Szepesvári. Bandit Algorithms , 2020

    2020

  6. [14]

    Asynchronous methods for deep reinforcement learning

    Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. arXiv preprint arXiv:1602.01783 , 2016

    2016 arXiv

  7. [15]

    Machado, Marc G

    Marlos C. Machado, Marc G. Bellemare, Erik Talvitie, Joel Veness, Matthew J. Hausknecht, and Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research , 61:523--562, 2018

    2018

  8. [16]

    Riedmiller

    Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin A. Riedmiller. Playing A tari with deep reinforcement learning. CoRR , abs/1312.5602, 2013

    2013 arXiv

  9. [17]

    Human-level control through deep reinforcement learning

    Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature , 518(7540):529--533, 2015

    2015

  10. [18]

    Genetic multi-armed bandits: a reinforcement learning approach for discrete optimization via simulation

    Deniz Preil and Michael Krapp. Genetic multi-armed bandits: a reinforcement learning approach for discrete optimization via simulation. CoRR , abs/2302.07695, 2023

    2023 arXiv

  11. [19]

    Reinforcement learning in linear mdps: Constant regret and representation selection

    Matteo Papini, Andrea Tirinzoni, Aldo Pacchiano, Marcello Restelli, Alessandro Lazaric, and Matteo Pirotta. Reinforcement learning in linear mdps: Constant regret and representation selection. In NeurIPS 2021 , pages 16371--16383, 2021

    2021

  12. [20]

    Markov decision processes: discrete stochastic dynamic programming, 2014

    Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming, 2014

    2014

  13. [21]

    Mastering the game of go without human knowledge

    David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature , 550(7676):354--359, 2018

    2018

  14. [22]

    Sublinear least-squares value iteration via locality sensitive hashing

    Anshumali Shrivastava, Zhao Song, and Zhaozhuo Xu. Sublinear least-squares value iteration via locality sensitive hashing. CoRR , abs/2105.08285, 2021

    2021 arXiv

  15. [23]

    Proximal policy optimization algorithms

    John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 , 2017

    2017 arXiv

  16. [24]

    Sketching for first order method: Efficient algorithm for low-bandwidth channel and vulnerability

    Zhao Song, Yitan Wang, Zheng Yu, and Lichen Zhang. Sketching for first order method: Efficient algorithm for low-bandwidth channel and vulnerability. In ICML 2023 , volume 202 of Proceedings of Machine Learning Research , pages 32365--32417, 2023

    2023

  17. [25]

    Sketching linear classifiers over data streams

    Kai Sheng Tai, Vatsal Sharan, Peter Bailis, and Gregory Valiant. Sketching linear classifiers over data streams. In SIGMOD 2018 , pages 757--772, 2018

    2018

  18. [26]

    How close is the sample covariance matrix to the actual covariance matrix?, 2010

    Roman Vershynin. How close is the sample covariance matrix to the actual covariance matrix?, 2010

    2010

  19. [27]

    Wagenmaker, Yifang Chen, Max Simchowitz, Simon S

    Andrew J. Wagenmaker, Yifang Chen, Max Simchowitz, Simon S. Du, and Kevin G. Jamieson. First-order regret in reinforcement learning with linear function approximation: A robust estimation approach. In ICML 2022 , volume 162 of Proceedings of Machine Learning Research , pages 2...

    2022

  20. [28]

    Woodruff

    David P. Woodruff. Sketching as a tool for numerical linear algebra. Found. Trends Theor. Comput. Sci. , 10(1-2):1--157, 2014

    2014

  21. [29]

    Provably efficient reinforcement learning with linear function approximation under adaptivity constraints

    Tianhao Wang, Dongruo Zhou, and Quanquan Gu. Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. In Marc'Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, NeurIPS 2021...

    2021

  22. [30]

    A general framework for sequential decision-making under adaptivity constraints

    Nuoya Xiong, Zhaoran Wang, and Zhuoran Yang. A general framework for sequential decision-making under adaptivity constraints. In ICML 2024, Vienna, Austria, July 21-27, 2024 , 2024

    2024

  23. [31]

    Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound

    Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In ICML 2020 , volume 119 of Proceedings of Machine Learning Research , pages 10746--10756, 2020

    2020

  24. [32]

    Varshney, and Ashish Jagmohan

    Huozhi Zhou, Jinglin Chen, Lav R. Varshney, and Ashish Jagmohan. Nonstationary reinforcement learning with linear function approximation. Trans. Mach. Learn. Res. , 2022

    2022

  25. [33]

    Making linear mdps practical via contrastive representation learning

    Tianjun Zhang, Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making linear mdps practical via contrastive representation learning. In ICML 2022 , volume 162 of Proceedings of Machine Learning Research , pages 26447--26466, 2022

    2022

Pith tools

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