Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback

Tal Lancewicki; Yishay Mansour

REVIEW 2 major objections 4 minor 1 cited by

Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback

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

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

Pith's one-line read In online MDPs with aggregate bandit feedback and known dynamics, policy optimization achieves the first optimal regret bound $\tilde\Theta(H^2\sqrt{SAK})$.

desk verdict The U-function is a genuine new tool and the known-dynamics bound is near-optimal in the SA >= H^2 regime, but the abstract's unqualified Theta(H^2 sqrt(SAK)) overstates what Theorems 2 and 4 actually deliver. read the letter →

arxiv 2502.04004 v1 pith:VSOARE5S submitted 2025-02-06 cs.LG

Tal Lancewicki , Yishay Mansour This is my paper · ORCID

classification cs.LG

keywords onlineMDPsaggregatebanditfeedbackpolicyoptimizationregretboundsadversariallossesfull-banditU-functionmultiplicativeweights

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 studies finite-horizon Markov decision processes in which an adversary chooses the cost of each state-action pair each episode, and the learner observes only the episode's total cost, never the per-step costs. The authors introduce policy-optimization algorithms for this aggregate-bandit setting. With known transition dynamics, their algorithm attains $\tilde O(H^2\sqrt{SAK}+H^3\sqrt K)$ regret, which matches the lower bound $\Omega(H^2\sqrt{SAK})$ up to log factors whenever $SA\ge H^2$, making it the first optimal-order guarantee in this feedback model. With unknown dynamics, they obtain $\tilde O(H^3 S\sqrt{AK})$, an improvement over the previous best bound by a factor of $H^2 S^5 A^2$, and it matches the best policy-optimization bound known for the strictly easier semi-bandit setting. The paper's central new device is the U-function, the expected total episode cost conditional on visiting a state-action pair, which can be estimated directly from the aggregated trajectory loss.

What carries the argument

The load-bearing object is the U-function $U^\pi_h(s,a;\ell)$, defined as the expected total cost of the episode conditional on reaching $(s,a)$ at step $h$ under policy $\pi$; the paper shows that replacing the Q-function by U in the value-difference lemma costs nothing because the discrepancy is an action-independent offset (Lemma 2). The corresponding estimator $\hat U^k_h(s,a)=I\{s^k_h=s,a^k_h=a\}L^k_{1:H}/(\mu^k_h(s,a)+\gamma)$ uses only the aggregated trajectory loss, which is all the feedback available. Around this estimator the algorithm builds a multiplicative-weights update with a carefully chosen bonus $B^k$, computed as a Bellman value with local loss $b^k_h(s)=\sum_a 3\gamma H\pi^k_h(a|s)/(\mu^k_h(s)\pi^k_h(a|s)+\gamma)$; the bonus cancels the distribution-mismatch terms in the regret decomposition. In the unknown-dynamics version the same machinery is retained, with optimistic upper and lower occupancy estimates $\overline\mu^k_h(s,a)$ and $\underline\mu^k_h(s,a)$ obtained from Bernstein confidence sets.

What would settle it

Implement the lower-bound MDP from Appendix D with small $S,A$ and large $H$, and measure Algorithm 1's regret against both $H^2\sqrt{SAK}$ and $H^3\sqrt K$: the theorem's $H^3\sqrt K$ term should be visible whenever $SA<H^2$. More decisively, test whether the imported multi-task bandit lower bound used in Lemma 4 holds when each state receives a random number $T_i\sim\mathrm{Bin}(K,1/S)$ of rounds and the adversary picks per-state instances independently; if it fails for small $T_i$, the $\Omega(H^2\sqrt{SAK})$ lower bound no longer follows from the reduction.

Watch

Extended reading notes

Core claim

The central claim is that aggregate bandit feedback does not prevent optimal-order regret in online MDPs, provided the regret decomposition is built on the U-function rather than the Q-function. For a fixed policy $\pi$, $U^\pi_h(s,a;\ell)$ is the expected total loss of the episode given that $\pi$ chooses action $a$ in state $s$ at time $h$; Lemma 2 shows $U^\pi_h(s,a;\ell)-Q^\pi_h(s,a;\ell)$ is a state-only term independent of $a$. This makes the value-difference lemma valid with U in place of Q and yields an estimator $\hat U^k_h(s,a)=I\{s^k_h=s,a^k_h=a\}L^k_{1:H}/(\mu^k_h(s,a)+\gamma)$ that uses only the observed aggregate loss $L^k_{1:H}$. The analysis follows the policy-optimization template: a multiplicative-weights update on $\hat U^k$ with a variance-reducing bonus $B^k$, a regret decomposition whose bias and bonus terms cancel, and tuned $\eta,\gamma$ to balance the remaining terms. The result is a high-probability regret bound of $\tilde O(H^2\sqrt{SAK}+H^3\sqrt K)$ under known dynamics, and the paper's lower bound $\Omega(H^2\sqrt{SAK})$ is built by embedding a hard multi-task bandit into each state of an MDP.

Load-bearing premise

The claim of optimality rests on an imported multi-task bandit lower bound that the paper cites without proof or adaptation, together with the condition $SA\ge H^2$ that makes the $H^3\sqrt K$ term negligible.

Editorial extensions

If this is right

With known dynamics, aggregate-bandit online MDPs admit $\tilde\Theta(H^2\sqrt{SAK})$ regret, so no future algorithm in this feedback model can improve the order when $SA\ge H^2$.
With unknown dynamics, the $\tilde O(H^3 S\sqrt{AK})$ bound matches the best policy-optimization guarantee for semi-bandit feedback, showing the information gap between semi-bandit and aggregate feedback is not as large as previously thought.
The closed-form multiplicative-weights update avoids the per-iteration convex optimization of prior work, so the improvement comes with a computational gain rather than a trade-off.
The lower-bound construction transfers multi-task bandit hardness to MDPs by splitting visits across states, so any improved unknown-dynamics guarantee must close the remaining $H\sqrt S$ gap rather than change the known-dynamics exponent.

Reading between the lines

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

Beyond the paper's claims, the U-function estimator could be adapted to preference-based RL, where feedback is a binary outcome over a whole trajectory rather than a scalar loss; the same importance-weighted ratio would provide an unbiased trajectory-level gradient surrogate.
The $H^3\sqrt K$ term in Theorem 2 means the optimality claim is regime-dependent; an experiment sweeping $S,A,H$ separately could reveal whether this term is an artifact of the bonus construction and whether a tighter analysis can remove it.
Because the lower bound only uses states that are independent after the first step, a more informative probe of the unknown-dynamics gap $H\sqrt S$ would be to test whether intermediate state observations, but not intermediate losses, help; if they do, the gap reflects an information difference rather than a transition-estimation difficulty.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The core contribution is real: the U-function value difference lemma (Lemma 2, Corollary 1) is a clean and reusable way to handle aggregate bandit feedback, and it gives the first policy-optimization algorithm for this setting. The known-dynamics regret bound in Theorem 2 is the first to match the lower bound up to log factors when SA >= H^2, and the unknown-dynamics bound in Theorem 3 improves Cohen et al. (2021b) by a large factor while matching the best PO semi-bandit bound. I checked the key cancellations in the proof sketch and the full appendix: the bonus term indeed cancels the problematic distribution-mismatch terms, and the high-probability events are standard. The lower bound reduction in Appendix D is also plausible: the randomized initial state spreads the hard multi-task bandit instance across S independent subproblems, and Jensen/Chernoff gives the sqrt(SAK) rate. The paper is worth a serious referee. The soft spot is the width of the optimality claim. The abstract and contributions list say "optimal" without qualification, but Theorem 2 has an additive H^3 sqrt(K) term that dominates whenever SA < H^2. The authors themselves note this in the theorem statement, so the claim should be qualified there and in the abstract. This is a presentation problem, not a mathematical one, but it matters because the lower bound in Theorem 4 is only Omega(H^2 sqrt(SAK)). Also, the lower bound is inherited from Cohen et al. (2017) via a reduction; the paper does not prove that external lemma, so the tightness claim is only as solid as that citation. I did not find hidden missing conditions in the reduction, but the dependency should be flagged explicitly rather than presented as new. A smaller concern: the unknown-dynamics lower bound is still open, so the paper's title "Near-optimal" is accurate for known dynamics only. That said, the bounds are derived from first principles with no fitted constants, and the proofs are detailed enough to verify. Who this is for: RL theory readers working on bandit feedback, policy optimization, or MDP minimax regret. It is a solid paper with one overstated abstract. Send it to a serious referee, but ask for a revision that (i) qualifies the optimality statement to the SA >= H^2 regime and (ii) explicitly identifies the lower bound as inherited from Cohen et al. (2017).

Referee Report

2 major / 4 minor

Summary. The paper studies episodic finite-horizon online MDPs with adversarially chosen losses and aggregate bandit feedback, where the learner observes only the total episode loss rather than per-step losses. It introduces a new `U-function` decomposition (Lemma 2 and Corollary 1) that replaces the Q-function in the value-difference lemma with the expected total episode loss conditional on visiting a state-action pair, and it gives the first policy-optimization algorithms for this setting. For known dynamics, Algorithm 1 combines a multiplicative-weights update with a nearly unbiased estimator of the U-function and a state-dependent bonus; Theorem 2 claims regret \tilde O(H^2\sqrt{SAK}+H^3\sqrt K). For unknown dynamics, Algorithm 2 uses optimistic occupancy estimates and Bernstein-style confidence sets, giving Theorem 3 with regret \tilde O(H^3 S\sqrt{AK}+H^4 S^3 A). Theorem 4 states a lower bound \Omega(H^2\sqrt{SAK}) through a reduction to a multi-task bandit lower bound of Cohen et al. (2017). The abstract and contribution list describe the known-dynamics result as the first optimal bound \tilde\Theta(H^2\sqrt{SAK}).

Significance. The U-function decomposition is a natural and potentially reusable idea for aggregate-bandit feedback: it makes the full episode loss a valid unbiased signal for the quantity appearing in the regret decomposition, avoiding the need to estimate Q-functions from unavailable per-step losses. The proof structure in Appendix B is detailed and internally consistent; the key cancellation between the bonus term and the distribution-mismatch terms in Bias1 and Reg appears correct. If the optimality claim is properly qualified, the known-dynamics result is a genuine improvement over both inefficient reduction-to-linear-bandits bounds (\tilde O(H^2 S\sqrt{AK}) and \tilde O(H^2 SA\sqrt K)) and gives a matching lower bound in the SA \ge H^2 regime. The unknown-dynamics bound \tilde O(H^3 S\sqrt{AK}+H^4 S^3 A) improves on Cohen et al. (2021b) by a large factor and, surprisingly, matches the best known policy-optimization bound for the more informative semi-bandit setting. The paper also ships high-probability bounds with explicit logarithmic factors and a clear appendix, which strengthens the value of the contribution.

major comments (2)

[Abstract and Section 4 (Theorem 2)] The abstract and the contribution list state an unqualified optimal bound \tilde\Theta(H^2\sqrt{SAK}), but Theorem 2 only establishes \tilde O(H^2\sqrt{SAK}+H^3\sqrt K). The H^3\sqrt K term is not a proof artifact: with \eta=(H\sqrt{SAK}+H^2\sqrt K)^{-1}, the OMD term H\ln A/\eta contributes H^2\sqrt{SAK}\ln A + H^3\sqrt K\ln A. When SA < H^2, the H^3\sqrt K term dominates, and the lower bound in Theorem 4 (\Omega(H^2\sqrt{SAK})) does not close the gap. The paper itself acknowledges the condition SA \ge H^2 in the remarks after Theorem 2, so the abstract and contribution list must be revised to either state the optimality claim only in the regime SA \ge H^2 or to remove the second term from the upper bound.
[Section 6 and Appendix D (Lemma 4, Theorem 4)] The matching lower bound relies entirely on Lemma 4, imported as Theorem 1 of Cohen et al. (2017) and not proved in the paper. The reduction in Appendix D encodes a hard multi-task bandit problem in each state, but the number of rounds at a given state is a random variable T_i (roughly K/S in expectation), and the adversary's loss functions are fixed for all K episodes before the random state transitions are realized. The proof neither states the exact hypotheses of the cited theorem (e.g., fixed vs. random number of rounds, oblivious vs. adaptive adversary) nor verifies that the induced per-state subproblem satisfies them. This is load-bearing for the claimed \tilde\Theta(H^2\sqrt{SAK}) optimality, so the authors should either include a proof of Lemma 4 or provide a detailed verification/adaptation of its conditions in the MDP reduction.

minor comments (4)

[Lemma 2 statement] The quantifier in Lemma 2 is written as "(h,s,a)\,\in\,[H]\times A\times S", which reorders the state and action sets; it should be [H]\times S\times A.
[Section 2 notation] The definition of the indicator I^k_h(s,a) contains a typographical error: I^k_h(s,a)=I{s^k_h=s,\,a^k_h=s} should read a^k_h=a in the second component.
[Table 1] The table entries abbreviate the regret bounds without explicitly saying that logarithmic and lower-order terms are suppressed; adding a footnote to that effect would improve readability for readers comparing the rows.
[Appendix D] The notation in the lower-bound proof uses both "SAT_i" and "\sqrt{SA}" inconsistently; the derivation is correct once the missing parentheses are understood, but the display would benefit from a clearer statement of how the sum over states is evaluated.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular step: the regret upper bound is derived from first principles, and the lower bound is an external multi-task bandit result; the abstract's unqualified Theta is a scoping overclaim, not a circularity.

full rationale

The paper's central derivation is self-contained rather than self-referential. The U-function is defined in Section 3 as the expected total loss conditional on a time-h state-action visit; Lemma 2 proves U-Q equals an action-independent prefix term using the Markov property; and Corollary 1 derives the U-based value-difference decomposition from the standard value-difference lemma. None of these steps assumes the target regret bound. The estimator in Eq. (3) is analyzed in Lemma 3, which computes its conditional expectation directly from the definition and the law of total expectation, and the subsequent concentration arguments (Lemmas 5-8) are standard martingale bounds. The bonus B_k is a deterministic proof device designed to cancel distribution-mismatch terms through the value-difference lemma; its constants are chosen in the analysis, not fitted to data, and the resulting bound is stated explicitly, including the H^3 sqrt(K) term. The abstract's Theta(H^2 sqrt(SAK)) claim is formally narrower than Theorem 2, because the H^3 sqrt(K) term dominates when SA < H^2; this is a correctness or scoping issue about what 'optimal' means, not circularity. The lower bound Theorem 4 is obtained by reducing an MDP with a uniformly random first transition to the multi-task bandit problem and invoking Lemma 4 from Cohen et al. (2017), an independent external theorem proved outside this paper; importing it is a normal use of an external benchmark, and the proof does not assume the target bound. The only self-citations (Even-Dar et al. 2009 for the value-difference lemma; Cohen et al. 2021a for a Freedman consequence) are standard technical lemmas and are not load-bearing: deleting or replacing them would not change any conclusion. Hence no prediction or lower bound reduces to its own input.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

No new physical or model entities are posited. The U-function is a derived quantity, defined and verified internally; it is not a graviton pulled in without support. The only external ingredients are cited theorems and standard concentration lemmas.

free parameters (2)

learning rate eta = sqrt(iota)/(H sqrt(SAK)+H^2 sqrt(K))
Chosen to balance the OMD regret term and second-moment terms in the proof; not fitted to data.
exploration parameter gamma = 2 eta H
Chosen to make the bonus cancellation (Lemma 11) and variance bounds work; affects the H^3 sqrt(K) low-order term.

assumptions (5)

domain assumption Lemma 4: multi-task bandit lower bound (Cohen et al. 2017, Theorem 1)
Imported without proof; the lower bound and hence the optimality claim inherit it.
standard math Confidence-set transition bounds (Luo et al. 2021 Lemma 24; Jin et al. 2020 Lemmas 26-27)
Used for the unknown-dynamics optimistic estimator and occupancy estimation; standard concentration results.
standard math Entropy-regularized OMD guarantee (Lemma 25, Hazan et al.)
Basis of the multiplicative weights regret bound in both algorithms.
standard math Freedman-type concentration inequality (Lemma 22, Beygelzimer et al. 2011)
Used to define the good events G1-G5 that make the regret deterministic.
domain assumption Oblivious adversary and Markovian policies
The regret benchmark is the best fixed policy against a fixed loss sequence; the U-function estimator's unbiasedness is proved under this protocol.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback." pith.science (2026). https://pith.science/paper/VSOARE5S

@misc{pith2026250204004,
  author       = {Pith},
  title        = {Pith review of: Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VSOARE5S}},
  note         = {Machine review of arXiv:2502.04004}
}

abstract

We study online finite-horizon Markov Decision Processes with adversarially changing loss and aggregate bandit feedback (a.k.a full-bandit). Under this type of feedback, the agent observes only the total loss incurred over the entire trajectory, rather than the individual losses at each intermediate step within the trajectory. We introduce the first Policy Optimization algorithms for this setting. In the known-dynamics case, we achieve the first \textit{optimal} regret bound of $\tilde \Theta(H^2\sqrt{SAK})$, where $K$ is the number of episodes, $H$ is the episode horizon, $S$ is the number of states, and $A$ is the number of actions. In the unknown dynamics case we establish regret bound of $\tilde O(H^3 S \sqrt{AK})$, significantly improving the best known result by a factor of $H^2 S^5 A^2$.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits
cs.LG 2025-05 conditional novelty 7.0 of 10

Outcome-based online RL is tractable under coverability with general function approximation, but there are MDPs where trajectory-level feedback costs exponentially more samples than per-step feedback.

Reference graph

Works this paper leans on

34 extracted references · 28 canonical work pages · cited by 1 Pith paper

[1]

J. D. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, pages 263--274. Citeseer, 2008

work page 2008
[2]

Beygelzimer, J

A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 2011

work page 2011
[3]

Bubeck, N

S. Bubeck, N. Cesa-Bianchi, and S. M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference on Learning Theory, pages 41--1. JMLR Workshop and Conference Proceedings, 2012

work page 2012
[4]

Q. Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283--1294. PMLR, 2020

2020
[5]

Cassel, H

A. Cassel, H. Luo, A. Rosenberg, and D. Sotnikov. Near-optimal regret in linear mdps with aggregate bandit feedback. arXiv preprint arXiv:2405.07637, 2024

arXiv 2024
[6]

Cesa-Bianchi and G

N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78 0 (5): 0 1404--1422, 2012

work page 2012
[7]

Chatterji, A

N. Chatterji, A. Pacchiano, P. Bartlett, and M. Jordan. On the theory of reinforcement learning with once-per-episode feedback. Advances in Neural Information Processing Systems, 34: 0 3401--3412, 2021

work page 2021
[8]

L. Chen, H. Luo, and A. Rosenberg. Policy optimization for stochastic shortest path. In P. Loh and M. Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK , volume 178 of Proceedings of Machine Learning Research, pages 982--1046. PMLR , 2022 a

work page 2022

Show all 34 references

[9]

X. Chen, H. Zhong, Z. Yang, Z. Wang, and L. Wang. Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773--3793. PMLR, 2022 b

2022
[10]

Cohen, T

A. Cohen, T. Hazan, and T. Koren. Tight bounds for bandit combinatorial optimization. In Conference on Learning Theory, pages 629--642. PMLR, 2017

2017
[11]

Cohen, Y

A. Cohen, Y. Efroni, Y. Mansour, and A. Rosenberg. Minimax regret for stochastic shortest path. Advances in Neural Information Processing Systems, 34, 2021 a

2021
[12]

Cohen, H

A. Cohen, H. Kaplan, T. Koren, and Y. Mansour. Online markov decision processes with aggregate bandit feedback. In Conference on Learning Theory, pages 1301--1329. PMLR, 2021 b

2021
[13]

Y. Dai, H. Luo, C.-Y. Wei, and J. Zimmert. Refined regret for adversarial mdps with linear function approximation. arXiv preprint arXiv:2301.12942, 2023

2023 arXiv
[14]

V. Dani, S. M. Kakade, and T. Hayes. The price of bandit information for online optimization. Advances in Neural Information Processing Systems, 20, 2007

2007
[15]

Efroni, N

Y. Efroni, N. Merlis, and S. Mannor. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 7288--7295, 2021

2021
[16]

Even-Dar, S

E. Even-Dar, S. M. Kakade, and Y. Mansour. Online markov decision processes. Mathematics of Operations Research, 34 0 (3): 0 726--736, 2009

2009
[17]

Hazan and Z

E. Hazan and Z. Karnin. Volumetric spanners: an efficient exploration basis for learning. Journal of Machine Learning Research, 2016

2016
[18]

Hazan et al

E. Hazan et al. Introduction to online convex optimization. Foundations and Trends in Optimization , 2 0 (3-4): 0 157--325, 2016

2016
[19]

Jaksch, R

T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11 0 (4), 2010

2010
[20]

C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863--4873, 2018

2018
[21]

C. Jin, T. Jin, H. Luo, S. Sra, and T. Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pages 4860--4869. PMLR, 2020

2020
[22]

S. M. Kakade. A natural policy gradient. Advances in neural information processing systems, 14: 0 1531--1538, 2001

2001
[23]

Lattimore and C

T. Lattimore and C. Szepesv \'a ri. Bandit algorithms. Cambridge University Press, 2020

2020
[24]

Liu, C.-Y

H. Liu, C.-Y. Wei, and J. Zimmert. Towards optimal regret in adversarial linear mdps with bandit feedback. arXiv preprint arXiv:2310.11550, 2023

2023 arXiv
[25]

Luo, C.-Y

H. Luo, C.-Y. Wei, and C.-W. Lee. Policy optimization in adversarial mdps: Improved exploration via dilated bonuses. Advances in Neural Information Processing Systems, 34, 2021

2021
[26]

Rosenberg and Y

A. Rosenberg and Y. Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. In Advances in Neural Information Processing Systems, pages 2209--2218, 2019 a

2019
[27]

Rosenberg and Y

A. Rosenberg and Y. Mansour. Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning, pages 5478--5486. PMLR, 2019 b

2019
[28]

A. Saha, A. Pacchiano, and J. Lee. Dueling rl: Reinforcement learning with trajectory preferences. In International Conference on Artificial Intelligence and Statistics, pages 6263--6289. PMLR, 2023

2023
[29]

Schulman, S

J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889--1897, 2015

2015
[30]

Schulman, F

J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017

2017 arXiv
[31]

Shani, Y

L. Shani, Y. Efroni, A. Rosenberg, and S. Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604--8613. PMLR, 2020

2020
[32]

Sherman, T

U. Sherman, T. Koren, and Y. Mansour. Improved regret for efficient online reinforcement learning with linear function approximation. arXiv preprint arXiv:2301.13087, 2023

2023 arXiv
[33]

Wu and W

R. Wu and W. Sun. Making rl with preference-based feedback efficient via randomization. arXiv preprint arXiv:2310.14554, 2023

2023 arXiv
[34]

Zimin and G

A. Zimin and G. Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013., 2013

2013

Pith tools

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

[1] [1]

J. D. Abernethy, E. Hazan, and A. Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In COLT, pages 263--274. Citeseer, 2008

work page 2008

[2] [2]

Beygelzimer, J

A. Beygelzimer, J. Langford, L. Li, L. Reyzin, and R. Schapire. Contextual bandit algorithms with supervised learning guarantees. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. JMLR Workshop and Conference Proceedings, 2011

work page 2011

[3] [3]

Bubeck, N

S. Bubeck, N. Cesa-Bianchi, and S. M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Conference on Learning Theory, pages 41--1. JMLR Workshop and Conference Proceedings, 2012

work page 2012

[4] [4]

Q. Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283--1294. PMLR, 2020

2020

[5] [5]

Cassel, H

A. Cassel, H. Luo, A. Rosenberg, and D. Sotnikov. Near-optimal regret in linear mdps with aggregate bandit feedback. arXiv preprint arXiv:2405.07637, 2024

arXiv 2024

[6] [6]

Cesa-Bianchi and G

N. Cesa-Bianchi and G. Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78 0 (5): 0 1404--1422, 2012

work page 2012

[7] [7]

Chatterji, A

N. Chatterji, A. Pacchiano, P. Bartlett, and M. Jordan. On the theory of reinforcement learning with once-per-episode feedback. Advances in Neural Information Processing Systems, 34: 0 3401--3412, 2021

work page 2021

[8] [8]

L. Chen, H. Luo, and A. Rosenberg. Policy optimization for stochastic shortest path. In P. Loh and M. Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK , volume 178 of Proceedings of Machine Learning Research, pages 982--1046. PMLR , 2022 a

work page 2022