Reinforcement Learning with Segment Feedback

Anna Winnicki; Gal Dalal; R. Srikant; Shie Mannor; Yihan Du

REVIEW 2 major objections 3 minor 2 cited by

Reinforcement Learning with Segment Feedback

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

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

Pith's one-line read Under binary segment feedback, RL regret decays exponentially with the number of segments, while under sum segment feedback the number of segments barely affects regret.

desk verdict The binary-vs-sum contrast is real and well supported, but Theorem 4.1 as stated omits the coverage condition its E-optimal design needs, so the m-independence claim needs qualification. read the letter →

arxiv 2502.01876 v2 pith:AJR7CYNW submitted 2025-02-03 cs.LG

Yihan Du , Anna Winnicki , Gal Dalal , Shie Mannor , R. Srikant This is my paper · ORCID

classification cs.LG MSC 68Q3290C4062K05

keywords segmentfeedbackbinarysumepisodicMDPregretboundsThompsonsamplingLinUCBE-optimaldesign

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

The paper introduces RL with segment feedback: an episode is split into $m$ segments and the agent receives a reward signal only at the end of each segment, interpolating between per-state-action reward and once-per-trajectory reward. It asks how the number of segments $m$ affects learning, and answers with matching upper and lower regret bounds. For binary feedback, where each segment yields a thumbs-up/down generated by a sigmoid of the segment reward, the regret carries a factor of order $\exp(H r_{\max}/(2m))$, so more segments shrink regret exponentially. For sum feedback, where the agent observes the total reward in each segment, the leading regret is $O(|S||A|\sqrt{HK}\log(\cdot))$ and is essentially independent of $m$. The lower bounds show that both behaviors are unavoidable, not artifacts of the algorithms.

What carries the argument

For binary feedback, the machinery is maximum-likelihood estimation of the reward parameter from sigmoid observations, a Gaussian posterior perturbation scaled by the inverse sigmoid derivative, and the feature covariance matrix of past segments; the exponential factor enters through the quantity $\alpha = \exp(H r_{\max}/m) + \exp(-H r_{\max}/m) + 2$, which bounds the inverse derivative. The lower bound uses a KL-divergence/Pinsker argument that turns the sigmoid derivative into the exponential factor. For sum feedback, the machinery treats segment rewards as linear in segment visitation counts and uses E-optimal experimental design: a distribution over policies is chosen to maximize the minimum eigenvalue of the expected segment-feature covariance, then rounded to a discrete initial exploration sequence with the ROUND procedure. This ensures the elliptical norm $\|\phi\|_{(\Sigma_{k-1})^{-1}}$ is bounded by $1$, which is what removes the $m$-dependence from the leading regret term.

What would settle it

On the binary side, run SegBiTS on the paper's experimental MDP with $H=100$, $r_{\max}=0.5$ for $m=1$ and $m=2$; the claimed bound predicts the $m=1$ regret exceeds the $m=2$ regret by a factor on the order of $\exp(H r_{\max}/2)=\exp(25)\approx 7.2\times 10^{10}$, so a measured ratio orders of magnitude smaller would falsify the exponential dependence. On the sum side, execute E-LinUCB on an MDP where the E-optimal design is singular, e.g., some state-action pair is unreachable under every policy; the theorem as stated promises the flat-in-$m$ bound but the algorithm has no defined $K_0$, revealing that the missing coverage assumption is load-bearing.

Watch

Extended reading notes

Core claim

The central discovery is that the information content of a segment depends on the feedback type. Under binary segment feedback, the decisive quantity is the per-segment reward scale $H r_{\max}/m$: when it is large, the sigmoid is flat, the observed binary outcomes are almost constant, and distinguishing good from bad actions is exponentially hard; when $m$ increases, the scale drops and learning accelerates. The paper proves this with a Thompson-sampling algorithm whose regret is $\widetilde{O}(\exp(H r_{\max}/(2m)) \cdot \mathrm{poly}(|S|,|A|,H) \cdot \sqrt{K})$ and a lower bound $\Omega(\exp((1/2-c_0)H r_{\max}/m)\sqrt{|S||A|mK})$. Under sum feedback, by contrast, an E-optimal-design LinUCB algorithm achieves regret $O(|S||A|\sqrt{HK}\log(\cdot) + (z^*)^2 H^5 \log(\cdot) + |S||A|H)$, with a matching $\Omega(\sqrt{|S||A|HK})$ lower bound: splitting the trajectory into segments neither helps nor hurts in leading order, because the smaller per-segment feature vectors shrink the covariance and offset the extra observations.

Load-bearing premise

The sum-feedback result with known transitions requires at least one distribution over policies whose expected segment-feature covariance matrix is invertible, meaning every state-action pair must be reachable by some policy; the theorem statement itself does not explicitly include this coverage condition.

Editorial extensions

If this is right

Under binary feedback, doubling $m$ replaces $\exp(-H r_{\max}/(2m))$ with a much smaller factor, so even a modest number of segments per trajectory yields most of the statistical benefit of fine-grained feedback.
Under sum feedback, there is no leading-order statistical penalty for using fewer, longer segments, so algorithms can operate on trajectory-level totals without sacrificing regret order when $m$ is small.
At $m=1$, sum segment feedback reduces to trajectory feedback, and the E-optimal-design analysis improves the existing trajectory-feedback regret by a factor of $\sqrt{H}$.
The binary lower bound applies to any algorithm, not just SegBiTS, so the exponential dependence on $H r_{\max}/m$ is inherent to the information structure of binary segment feedback.
Together the two results give a practical rule-of-thumb: for binary human feedback, split trajectories into more segments; for numerical summed rewards, segment count is not a major lever.

Reading between the lines

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

One extension the paper leaves implicit is unequal segment lengths; under sum feedback the noise variance per segment would vary, so the cancellation between more observations and smaller features may break, giving a testable departure from the flat-in-$m$ bound.
The exponential binary-feedback penalty is driven by the per-segment reward scale, so a practical design implication not drawn by the paper is to normalize or clip segment rewards so human queries fall in the steep part of the sigmoid.
The lower-bound constructions use bandit-like MDPs with absorbing states, suggesting the exponential factor should also appear in contextual or partially observable variants whenever per-segment reward scale is large; this is a conjecture an interested reader could test.
A natural next experiment would vary $H r_{\max}/m$ directly while holding $m$ fixed to confirm that the binary-feedback regret tracks the exponential factor rather than $m$ alone.

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.

Desk Editor's Note

read the letter

You should know two things. First, this paper gives the first regret bounds that quantify how the number of segments m affects learning under segment feedback, and the central contrast is credible: binary feedback regret scales like exp(H rmax / 2m), while sum feedback regret is essentially m-independent. Second, the sum-feedback upper bound in Theorem 4.1 is overstated as printed. The proof depends on Algorithm 2's E-optimal design, which requires some mixture of policies to make the segment-feature covariance invertible. That assumption appears only in the algorithm description, not in the theorem statement. So the m-independence result is proved only for MDPs with full reachability/coverage.

What the paper does well: the binary lower bound is genuinely new and the KL/Pinsker argument is clean. The binary upper bound uses adapted logistic-bandit self-concordance tools and looks coherent. The sum-feedback analysis is standard linear bandit plus E-optimal design, and it improves the prior trajectory-feedback result by sqrt H. No parameters are fitted; all constants are explicit. The proof appendix is consistent with the stated theorems as far as I checked without machine verification. The experiments are small and no code or data are released, but they are clearly secondary to the theory.

The soft spot I want you to weigh is just the missing coverage condition in Theorem 4.1. This is a qualification, not a fatal error. The lower bound in Theorem 4.2 is built on a covered instance, so the worst-case claim that increasing m does not help much under sum feedback still stands. The fix is straightforward: state the reachability assumption in the theorem and, ideally, discuss how it relates to the empirical bagged-reward work. A secondary concern is that the E-LinUCB algorithm is computationally heavy; the paper even says the experiments use a small MDP because of that, so the "practical" message is weaker than the abstract suggests.

Who gets value from this: RL theorists and anyone working on reward engineering with sparse or aggregated feedback. The binary lower bound alone is worth a serious referee. I would send it to review rather than desk-reject, with a request to fix the theorem statement and add a short discussion of coverage. I would not block publication on the missing condition, but it has to be written down.

My bottom line: the central result is likely correct; it needs an honest qualifier, not a rewrite.

Referee Report

2 major / 3 minor

Summary. The paper introduces RL with segment feedback, an episodic tabular setting in which each episode is split into m equal segments and the agent observes feedback only at the end of each segment. Two feedback models are studied: binary feedback, where each segment yields a Bernoulli observation with parameter the sigmoid of the segment reward, and sum feedback, where the segment reward sum is observed with sub-Gaussian noise. The paper proposes Thompson-sampling algorithms SegBiTS and SegBiTS-Tran for binary feedback with known and unknown transitions, and E-LinUCB and LinUCB-Tran for sum feedback with known and unknown transitions. The main results are: for binary feedback, regret scales as exp(H rmax/(2m)) times polynomial factors, with a matching lower bound exp((1/2-c0)H rmax/m) sqrt(mK); for sum feedback, the leading regret term is O(|S||A| sqrt(HK) log) and is independent of m, with lower bounds Omega(sqrt(|S||A|HK)) and Omega(rmax H sqrt(|S||A|K)). Small experiments support the binary exponential decay and the roughly flat m-dependence for sum feedback. The appendix contains complete proofs, including self-concordance arguments for logistic bandits, KL/Pinsker lower bounds, and E-optimal experimental design for the initialization phase.

Significance. The segment-feedback model is a natural interpolation between per-step feedback and once-per-episode trajectory feedback, and the paper gives the first systematic theoretical treatment of how the number of segments affects regret. If the stated bounds are correct, the contrast between exponential improvement in m under binary feedback and essentially flat leading-order behaviour under sum feedback is an interesting and non-obvious message. The proofs are detailed and self-contained: the binary upper bound adapts logistic-bandit self-concordance and Thompson-sampling anti-concentration, the binary lower bound uses a clean KL/Pinsker construction, and the sum upper bound improves the prior trajectory-feedback result of Efroni et al. by a sqrt(H) factor through E-optimal design. The lower bounds are information-theoretic rather than algorithmic, and the constants are explicit analytic functions of the problem parameters rather than fitted values.

major comments (2)

[§4.1, Theorem 4.1, Algorithm 2, Eq. (4)] Theorem 4.1 is stated without the full-rank coverage condition that Algorithm 2's E-optimal design actually requires. In Eq. (4), z* is finite only if some distribution w over policies makes the expected segment-feature covariance matrix nonsingular; otherwise z*=infinity, K0 in Line 3 is undefined, and Lemma D.2, which is used to prove ||phi_pi||_{Sigma_{k-1}^{-1}} <= 1 for all k > K0, fails. The assumption appears only as 'We assume...' inside the algorithm description, not in the theorem statement. The m-independence conclusion for sum feedback is therefore established only for MDPs satisfying this coverage property, and the theorem statement as well as the discussion following it should say so explicitly.
[§4.1, Eq. (4), Theorem 4.1] The additive term (z*)^2 H^5 log(1/delta) in Theorem 4.1 is not m-independent. Here z* is the E-optimal value of the unnormalized segment-feature covariance, and for a one-state, one-action MDP one has z* = m/H^2, making this term of order m^2 H. Thus the text's claim that the upper bound 'does not depend on m when ignoring logarithmic factors' is not literally true: the leading term in K is m-independent, but the initialization term can grow with m and the finite-K regret bound can worsen as m grows. The authors should either state explicitly that the m-independence claim concerns only the leading term in K and for K sufficiently large, or provide an additional argument controlling the z* term if the claim is meant to hold for all K.

minor comments (3)

[Algorithm 1, §3.1] Algorithm 1 takes lambda as an input but no value or tuning rule is given; the regret bound in Theorem 3.1 depends on lambda through nu(K) and alpha lambda, so a specific choice (or a statement that the bound holds for any fixed lambda) should be included.
[Appendix C.2, proof of Lemma C.11] In the union-bound arguments in Lemma C.11 and the parallel Lemmas D.6 and D.14, the text says 'with probability at least delta-prime' after taking the union bound; this should read 'with probability at least 1 - delta-prime'.
[Figure 5 and §C.2] In the lower-bound instance description, r(s_{n+2}, a) = (1 - eps) rmax appears in some places as '1 - eps rmax' without parentheses; this is a typographical issue in the display but should be corrected for clarity.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity found: the m-dependence results are established by independent explicit bounds and lower-bound constructions; self-cited technical lemmas are not load-bearing, and the sum-feedback coverage assumption is a qualification, not a circular definition.

full rationale

I walked the derivation chain for Theorems 3.1-3.3 and 4.1-4.3. No parameter appearing in the stated bounds is fitted to data or defined in terms of the quantity being predicted. The binary-feedback upper bound is built from an MLE confidence set (Lemmas C.2, C.6, C.7) whose constants are explicit functions of |S|, |A|, H, rmax, m, lambda, and delta; the exponential exp(Hrmax/(2m)) factor arises from the sigmoid derivative bound alpha, not from assuming the conclusion. The matching lower bound (Theorem 3.2) is a Pinsker/KL construction on a bandit-like MDP, so the exponential dependence is independently established. For sum feedback, Theorem 4.1 is a UCB regret decomposition with two explicit terms: the leading |S||A| sqrt(HK) log(...) term and a K0 term containing z* and H^5; z* is the optimal value of the E-optimal design (Eq. (4)), not a fitted parameter, and the m-independence claim is corroborated by the lower bound in Theorem 4.2. The proof does rely on technical lemmas from prior work with overlapping authorship, e.g., 'This proof is originated from the analysis of Lemma 11 in (Efroni et al., 2021)' and the analogous attribution for Lemma 13; these are standard Thompson-sampling/Gaussian-tail tools and do not smuggle in the segment-feedback conclusion. I also flag the in-scope passage in Algorithm 2: 'We assume that there exists a policy distribution w under which this matrix is invertible.' This reachability/coverage condition is needed for z* < infinity and for Lemma D.2, but it is not restated in Theorem 4.1. That is an omitted/understated assumption that narrows the theorem's applicability; it is a correctness or qualification concern, not circularity, because the assumption concerns state-action coverage and not the regret value being predicted. Overall, the central claims are self-contained against explicit problem parameters, so no circular step is established.

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

The central claims rest on the standard episodic MDP model plus two specific feedback-generating assumptions: sigmoid Bernoulli for binary feedback and additive sub-Gaussian noise for sum feedback. The E-optimal design coverage condition is a paper-specific assumption that should be stated in the main theorems. No data-fitted free parameters appear; all constants are explicit analytic choices.

assumptions (6)

domain assumption The environment is an episodic finite MDP with horizon H and rewards bounded in [-rmax, rmax].
Used throughout Sections 2-4 to define theta*, value functions, and regret.
domain assumption Each episode is partitioned into m equal segments of length H/m, and H is divisible by m.
Defines the segment feedback model and is stated at the start of Section 2.
domain assumption Binary feedback y_i is drawn as Bernoulli(mu(phi_i^T theta*)) independently across segments.
Load-bearing for all binary results; the exponential-in-m factor comes from the flatness of the sigmoid when segment sums are large.
domain assumption Sum feedback is the sum of per-step rewards plus zero-mean 1-sub-Gaussian noise, observed at segment ends.
Used for confidence ellipsoids and for the lower-bound construction in Section 4.
ad hoc to paper There exists a policy distribution w such that the expected segment-feature covariance matrix is invertible.
Stated in Algorithm 2 after Line 2 but absent from Theorem 4.1; without it z* is infinite and Lemma D.2 fails. See weakest_assumption.
standard math External concentration results hold: matrix Bernstein, self-normalized martingale bounds, and KL-based transition concentration from Menard et al. 2021.
The theorems rely on these standard results, which the paper cites but does not reprove.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Reinforcement Learning with Segment Feedback." pith.science (2026). https://pith.science/paper/AJR7CYNW

@misc{pith2026250201876,
  author       = {Pith},
  title        = {Pith review of: Reinforcement Learning with Segment Feedback},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AJR7CYNW}},
  note         = {Machine review of arXiv:2502.01876}
}

abstract

Standard reinforcement learning (RL) assumes that an agent can observe a reward for each state-action pair. However, in practical applications, it is often difficult and costly to collect a reward for each state-action pair. While there have been several works considering RL with trajectory feedback, it is unclear if trajectory feedback is inefficient for learning when trajectories are long. In this work, we consider a model named RL with segment feedback, which offers a general paradigm filling the gap between per-state-action feedback and trajectory feedback. In this model, we consider an episodic Markov decision process (MDP), where each episode is divided into $m$ segments, and the agent observes reward feedback only at the end of each segment. Under this model, we study two popular feedback settings: binary feedback and sum feedback, where the agent observes a binary outcome and a reward sum according to the underlying reward function, respectively. To investigate the impact of the number of segments $m$ on learning performance, we design efficient algorithms and establish regret upper and lower bounds for both feedback settings. Our theoretical and experimental results show that: under binary feedback, increasing the number of segments $m$ decreases the regret at an exponential rate; in contrast, surprisingly, under sum feedback, increasing $m$ does not reduce the regret significantly.

Figures

Figures reproduced from arXiv: 2502.01876 by the authors.

**Figure 1.** Lower bound instance. Under any suboptimal action a sub i , the agent transitions to sn+2 deterministically, and r(si , asub i ) = (1 − ε)rmax, where ε ∈ (0, 1 2 ) is a parameter specified later. For all actions a ∈ A, r(sn+1, a) = rmax and r(sn+2, a) = (1 − ε)rmax. Then, the KL divergence of binary observations between the optimal action and suboptimal actions in an episode is Xm i=1 KL B µ (1 − ε)Hrmax m … view at source ↗

**Figure 2.** Experimental results for RL with binary or sum segment feedback. m does not impact the regret result in essence. 4.3. Algorithm LinUCB-Tran for Unknown Transition Now we investigate RL with sum segment feedback in the unknown transition case. For unknown transition, we design an algorithm LinUCB-Tran, which establishes a variance-aware uncertainty bound for the estimated visitation indicator ϕˆπ k , and incorporate… view at source ↗

**Figure 3.** Instance used in the experiment for RL with binary segment feedback. For the sum segment feedback setting, since algorithms E-LinUCB and LinUCB-Tran are computationally inefficient (which are mainly designed for revealing the optimal dependency on H and m), we consider a smaller MDP as in [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Instance used in the experiment for RL with sum segment feedback. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

**Figure 5.** Figure 5: Instance for the lower bound under binary segment feedback and known transition. C.2. Proof for the Regret Lower Bound with Known Transition In the following, we prove the regret lower bound (Theorem 3.2) for RL with binary segment feedback and known transition. Proof …

**Figure 6.** Figure 6: Instance for the lower bound under sum segment feedback and known transition. where inequality (a) follows from Eq. (28), inequality (b) is due to the definition of π k , and inequality (c) uses the Jensen inequality. Plugging Eq. (29) and Lemma D.4 into Eq. (30) and u…

**Figure 7.** Figure 7: Instance for the lower bound under sum segment feedback and unknown transition. In this proof, we will also use an alternative uniform instance Iunif. The only difference between Iunif and I is that for any i ∈ [n], in state si , under all actions a ∈ A, the agent tran…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

Temporal GRPO: Beyond Trajectory-Level Credit in Vision-Language-Action Reinforcement Learning
cs.RO 2026-08 conditional novelty 6.0 of 10

Temporal GRPO splits a robot rollout into detectable task stages and applies separate group-relative policy advantages to each stage's action interval, improving success rates by 7 points on average over matched baselines.
SP3O: Reinforcement Learning from Segment Preferences without Reward Modeling
cs.LG 2026-08 conditional novelty 6.0 of 10

SP3O is a reward-model-free, critic-free, gradient-based RL algorithm that optimizes policies from segment-level preferences in stochastic MDPs via off-policy importance sampling and PPO-style clipping.

Reference graph

Works this paper leans on

26 extracted references · 21 canonical work pages · cited by 2 Pith papers

[1]

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 format.date year duplicate empty "emp...
[2]

Improved algorithms for linear stochastic bandits

Abbasi-Yadkori, Y., P \'a l, D., and Szepesv \'a ri, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, 2011

work page 2011
[3]

Near-optimal discrete optimization for experimental design: A regret minimization approach

Allen-Zhu, Z., Li, Y., Singh, A., and Wang, Y. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Programming, 186: 0 439--478, 2021

work page 2021
[4]

Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32 0 (1): 0 48--77, 2002

work page 2002
[5]

G., Osband, I., and Munos, R

Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pp.\ 263--272. PMLR, 2017

work page 2017
[6]

and Sundberg, C.-E

Borjesson, P. and Sundberg, C.-E. Simple approximations of the error function q (x) for communications applications. IEEE Transactions on Communications, 27 0 (3): 0 639--643, 1979

work page 1979
[7]

On the theory of reinforcement learning with once-per-episode feedback

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

work page 2021
[8]

Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning

Dann, C., Lattimore, T., and Brunskill, E. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, volume 30, 2017

work page 2017

Show all 26 references

[9]

Reinforcement learning with trajectory feedback

Efroni, Y., Merlis, N., and Mannor, S. Reinforcement learning with trajectory feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp.\ 7288--7295, 2021

2021
[10]

Improved optimistic algorithms for logistic bandits

Faury, L., Abeille, M., Calauz \`e nes, C., and Fercoq, O. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pp.\ 3052--3060. PMLR, 2020

2020
[11]

Parametric bandits: The generalized linear case

Filippi, S., Cappe, O., Garivier, A., and Szepesv \'a ri, C. Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, volume 23, 2010

2010
[12]

Harnessing causality in reinforcement learning with bagged decision times

Gao, D., Lai, H.-Y., Klasnja, P., and Murphy, S. Harnessing causality in reinforcement learning with bagged decision times. In International Conference on Artificial Intelligence and Statistics, 2025

2025
[13]

Gheshlaghi Azar, M., Munos, R., and Kappen, H. J. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine Learning, 91: 0 325--349, 2013

2013
[14]

Near-optimal regret bounds for reinforcement learning

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

2010
[15]

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

2018
[16]

and Hutter, M

Lattimore, T. and Hutter, M. Pac bounds for discounted mdps. In International Conference on Algorithmic Learning Theory, pp.\ 320--334. Springer, 2012

2012
[17]

and Massart, P

Laurent, B. and Massart, P. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pp.\ 1302--1338, 2000

2000
[18]

D., Jonsson, A., Kaufmann, E., Leurent, E., and Valko, M

M \'e nard, P., Domingues, O. D., Jonsson, A., Kaufmann, E., Leurent, E., and Valko, M. Fast active learning for pure exploration in reinforcement learning. In International Conference on Machine Learning, pp.\ 7599--7608. PMLR, 2021

2021
[19]

and Moore, A

Munos, R. and Moore, A. Influence and variance of a markov chain: Application to adaptive discretization in optimal control. In Proceedings of the IEEE Conference on Decision and Control, volume 2, pp.\ 1464--1469. IEEE, 1999

1999
[20]

Optimal design of experiments

Pukelsheim, F. Optimal design of experiments. SIAM, 2006

2006
[21]

Self-concordant analysis of generalized linear bandits with forgetting

Russac, Y., Faury, L., Capp \'e , O., and Garivier, A. Self-concordant analysis of generalized linear bandits with forgetting. In International Conference on Artificial Intelligence and Statistics, pp.\ 658--666. PMLR, 2021

2021
[22]

Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018

2018
[23]

Reinforcement learning from bagged reward

Tang, Y., Cai, X.-Q., Ding, Y.-X., Wu, Q., Liu, G., and Sugiyama, M. Reinforcement learning from bagged reward. In ICML 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorists, 2024

2024
[24]

Thompson, W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25 0 (3-4): 0 285--294, 1933

1933
[25]

Tropp, J. A. et al. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning , 8 0 (1-2): 0 1--230, 2015

2015
[26]

and Brunskill, E

Zanette, A. and Brunskill, E. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp.\ 7304--7312. PMLR, 2019

2019

Pith tools

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

[1] [1]

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 format.date year duplicate empty "emp...

[2] [2]

Improved algorithms for linear stochastic bandits

Abbasi-Yadkori, Y., P \'a l, D., and Szepesv \'a ri, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24, 2011

work page 2011

[3] [3]

Near-optimal discrete optimization for experimental design: A regret minimization approach

Allen-Zhu, Z., Li, Y., Singh, A., and Wang, Y. Near-optimal discrete optimization for experimental design: A regret minimization approach. Mathematical Programming, 186: 0 439--478, 2021

work page 2021

[4] [4]

Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32 0 (1): 0 48--77, 2002

work page 2002

[5] [5]

G., Osband, I., and Munos, R

Azar, M. G., Osband, I., and Munos, R. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pp.\ 263--272. PMLR, 2017

work page 2017

[6] [6]

and Sundberg, C.-E

Borjesson, P. and Sundberg, C.-E. Simple approximations of the error function q (x) for communications applications. IEEE Transactions on Communications, 27 0 (3): 0 639--643, 1979

work page 1979

[7] [7]

On the theory of reinforcement learning with once-per-episode feedback

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

work page 2021

[8] [8]

Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning

Dann, C., Lattimore, T., and Brunskill, E. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In Advances in Neural Information Processing Systems, volume 30, 2017

work page 2017