Pith. sign in

REVIEW 3 major objections 5 minor 10 references

Online Learning in MDPs with Partially Adversarial Transitions and Losses

T0 review · 3 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read This paper proves that in MDPs with a fixed set of Λ adversarial transition steps per episode, regret scales exponentially only with Λ, not with the horizon H.

desk verdict The COM idea is genuinely new and Theorem 4.1 looks plausible, but Theorem 4.3's proof omits the adversarial block losses and doesn't support the advertised S improvement. read the letter →

arxiv 2602.09474 v2 pith:PJ7HTIVY submitted 2026-02-10 cs.LG

Ofir Schlisselberg , Tal Lancewicki , Yishay Mansour This is my paper · ORCID
classification cs.LG
keywords partiallyadversarialMDPsconditionedoccupancymeasuresonlinelearningregretboundstransitionsbanditfeedbackfull-informationepisodicreinforcement
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 studies reinforcement learning in MDPs where the transition function is stochastic at most steps but can be chosen adversarially at a fixed set of Λ steps in every episode. It introduces conditioned occupancy measures, which remain well-defined and episode-invariant despite adversarial transitions, and proves that regret grows exponentially only in Λ rather than in the horizon H. This gives a continuum between stationary dynamics (Λ=0) and fully adversarial dynamics (Λ=H-1), and it completes the regret landscape for fully adversarial transitions across all four feedback combinations. A reader should care because environments that are stable except at a few vulnerable points are common, and the results show such settings are learnable with sublinear regret.

What carries the argument

Conditioned occupancy measure (COM). For each time h, a condition c records the realized (state, action, next-state) triplet at every adversarial step before h. The COM μ_h(s,a,c) is the probability of reaching (s,a) at step h with condition c, conditioned on c being feasible, and ρ^k(c) is the episode-k probability that c is feasible. The identity q_h^k = Σ_c μ_h ρ^k(c) (Lemma A.9) separates an episode-invariant optimization target μ from an episode-dependent factor ρ that only needs estimation; this restores a fixed feasible polytope for occupancy-measure mirror-descent updates.

What would settle it

Construct an MDP with horizon H=3 and one adversarial transition per episode, choose that step uniformly at random among steps 1 and 2 in each episode while keeping all other data identical, and run the paper's Algorithm 2 with Λ=1; if its regret remains sublinear in K, then the fixed-set premise is not necessary for the bounds, whereas linear regret would confirm it is load-bearing. Alternatively, check empirically whether the factorization q_h^k(s,a)=Σ_c μ_h(s,a,c)ρ^k(c) holds with a single μ across episodes when the adversarial set changes.

Watch

Extended reading notes

Core claim

The central claim is that for a fixed set of Λ adversarial transition steps per episode, the minimax regret scales exponentially in Λ, not in the horizon H. The mechanism is a conditioned occupancy measure (COM) decomposition: any policy's occupancy measure factorizes as q_h^k(s,a) = Σ_c μ_h(s,a,c) ρ^k(c), where μ is an episode-independent probability that an algorithm can optimize and ρ^k(c) is the episode-dependent feasibility probability of the condition c listing realized outcomes at adversarial steps. Two algorithms use this stable part: one for arbitrary adversary step sets with regret O~(H S^Λ √(K S A^{Λ+1}) + H^3 S^2 A + √(H^4 S^2 A K)), and one for consecutive adversarial blocks wit

Load-bearing premise

The set of adversarial transition steps is fixed across episodes and all non-Λ transitions are exactly stationary, so the episode-invariant part μ of the conditioned occupancy measure is well defined; if the adversarial set drifts or transitions are merely close to stationary, the decomposition and the regret bounds collapse.

Editorial extensions

If this is right

  • With Λ small, partially adversarial dynamics are learnable even when losses are fully adversarial, so systems with a few vulnerable steps no longer require worst-case exponential regret.
  • If the adversarial steps are consecutive, the state-space dependence becomes polynomial in S, so the structure of the vulnerable block matters, not just its size; the exponential term is then A^{Λ+1} only.
  • The learner can avoid knowing the identity of adversarial steps through a model-selection reduction, paying only an extra K^{2/3} factor in regret.
  • Fully adversarial dynamics with bandit observation of the transition force regret Ω(√(A^H S K)), while full information on dynamics keeps regret polynomial; the exponential hardness is tied to bandit feedback on dynamics, not on losses.
  • Setting Λ=0 recovers the known state-of-the-art rates for adversarial losses with stationary transitions, so the bounds interpolate cleanly between the two extremes.

Reading between the lines

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

  • The fixed-set assumption is likely stronger than needed: the decomposition suggests the result may extend to slowly drifting adversarial sets by tracking conditions online, at the price of an additional non-stationarity term.
  • The K^{2/3} penalty for unknown adversarial steps appears to be an artifact of the black-box multiplicative-weights reduction; a direct algorithm that estimates which steps corrupt the dynamics could plausibly achieve √K regret.
  • The S^Λ versus S^3 gap between arbitrary and consecutive adversarial blocks points to a general principle: the L1 diameter of the COM polytope is controlled by the fragmentation of the adversarial set, so multi-block structures may interpolate the two rates.
  • The separation between bandit-dynamics and full-information-dynamics regimes suggests that observing losses globally does not circumvent the need to observe the transition function; this may carry over to partially observable control problems beyond MDPs.
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.

Referee Report

3 major / 5 minor

Summary. The paper studies finite-horizon episodic MDPs in which the loss function is fully adversarial and the transition kernel is adversarial at a fixed subset Λ of Λ steps per episode while being stationary at all other steps. It introduces conditioned occupancy measures (COMs), an episode-invariant object that, combined with an episode-dependent feasibility probability, decomposes the usual occupancy measure (Lemma A.9). Algorithm 2 (COM-OMD) is claimed to achieve regret ~O(H S^Λ sqrt(K S A^{Λ+1}) + H^3 S^2 A + sqrt(H^4 S^2 A K)) for arbitrary adversarial sets; Algorithm 3 (COMSP-OMD) is claimed to improve the S-dependence to ~O(H sqrt(K S^3 A^{Λ+1}) + ...) when the adversarial steps are consecutive; Algorithm 4 is a K^{2/3}-regret reduction for unknown adversarial sets. Section 3 gives upper and lower bounds for fully adversarial transitions under four feedback regimes (F/F, B/F, F/B, B/B).

Significance. If the results were fully established, the COM framework would be a genuine conceptual contribution: it extends occupancy-measure optimization to settings with a small number of adversarial transition steps and shows that the exponential hardness of adversarial MDPs scales with Λ rather than the full horizon H. The fully adversarial lower-bound reductions are explicit and the B/F results usefully separate the roles of loss feedback and transition feedback. The paper also ships extensive, mostly self-contained proofs; the four-way regret decomposition in Lemma A.16 is coherent, and no circular dependence on target regret bounds is apparent. However, the consecutive-block theorem has a substantive proof gap, the B/B upper-bound statement is contradicted by its own appendix, and the unknown-steps reduction has an exploration-probability inconsistency. These issues are load-bearing for the advertised contributions.

major comments (3)
  1. [§4.3 / Theorem 4.3 / Definitions B.1, B.5 / Lemma B.16] The consecutive-block proof does not account for losses incurred during the adversarial block. Definition B.1 defines the COM only for h < ~h1, h = ~h1, and h ≥ ~h2, and Remark 1 explicitly restricts all regret sums to h ≤ ~h1 union h ≥ ~h2. Definition B.5's estimator at h = ~h1 uses ℓ_{~h1}(s, σ), which is the per-step loss at ~h1, not the cumulative loss over the block [~h1, ~h2-1]. For Λ ≥ 2, the intermediate block losses contribute to both the learner's value and the benchmark policy's value, but they appear in no term of Lemma B.16 and are never optimized or estimated by the OMD objective. The informal remark 'Assume for simplicity that the adversarial transitions are deterministic' is not an assumption of Theorem 4.3, and even with deterministic transitions the proof would need to redefine ℓ_{~h1}(s, σ) as the total block loss. Thus Theorem B.22 / Theorem 4.3 is not established as
  2. [§3 / Theorem 3.5 vs §D.3.1] The main text states that in the B/B regime Algorithm 6 has regret R_K = \tilde O(sqrt(A^H S K)) and describes this as 'matching' the lower bound. The proof in Appendix D.3.1, with η = sqrt(S log A / (K A^H H)), yields R_K ≤ sqrt(H^3 K S A^H log A). Since \tilde O in this paper normally hides only logarithmic factors (cf. Theorem 4.1, where H^3 is displayed explicitly), the main-text theorem as stated is false. The actual upper bound carries an extra H^{3/2} factor relative to the lower bound Ω(sqrt(A^H S K)), so the 'matching' / 'almost matching' claim should be corrected and the gap acknowledged.
  3. [§4.4 / Algorithm 4 / Lemma C.2 / Theorem C.3] The unknown-adversarial-steps reduction has an exploration-probability inconsistency. Algorithm 4 line 12 sets ν_{k+1}(i) = (1-ξ)\hatν_{k+1}(i) + ξ / C(H,Λ), so the minimum selection probability of any candidate, in particular A*, is ξ / H^Λ, not ξ. However Lemma C.2 and Theorem C.3 repeatedly assume ν_k ≥ ξ, and Theorem C.3's proof bounds E[\barℓ^2] by 1/ξ. With the implemented exploration, E[\barℓ^2] ≤ H^Λ/ξ and the B2-type term becomes approximately sqrt(K H^Λ A/ξ), changing the claimed K^{2/3} bound by a factor exponential in Λ. The reduction needs either per-algorithm exploration with total probability |C|ξ (and the corresponding ξ H K |C| cost in Lemma C.1) or a different analysis.
minor comments (5)
  1. [Algorithm 3, §4.3] The pseudocode of Algorithm 3 is identical to Algorithm 2 at line 6 and does not describe how the sub-policy σ is selected and executed on the adversarial block. The surrounding text says 'σ is integrated into π', but the pseudocode should be updated to be self-contained.
  2. [Lemma B.19 / Lemma B.20] These lemmas are asserted with 'Same proof as Lemma A.19' / 'same way', but the sub-policy COM has a different conditional structure for h ≥ ~h2 and a different estimator normalization. The paper should state the required modifications or provide the full proof; this is particularly important because the transferred lemma is used to bound Error and Bias1 in Theorem B.22.
  3. [§3, F/B lower bound] The claimed F/B lower bound Ω(sqrt(A^{H-1} S K)) is stated informally after Theorem 3.4 ('at the small price of replacing H by H-1') without a proof. It should be stated as a theorem with a derivation, or explicitly deferred with a reference to the construction.
  4. [Lemma C.2 proof] The proof has unfinished sentences ('the last is since the .') and the probability argument is abbreviated. Please clean up the proof and state the high-probability event explicitly.
  5. [Abstract and Theorem 4.1] The abstract's first regret bound omits the lower-order terms H^3 S^2 A and sqrt(H^4 S^2 A K) that appear in Theorem 4.1. This is acceptable as a summary, but the simplified form should be flagged as such.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the derivations are self-contained reductions to standard concentration, OMD, and bandit bounds.

full rationale

The paper's derivation chain decomposes regret into Error, Bias1, Reg, and Bias2 terms, then bounds each term using concentration inequalities, optimistic estimates, the standard OMD regret lemma, and known bandit/expert lower bounds. The conditioned occupancy decomposition q_h^pi(s,a) = sum_c mu_h(s,a,c) rho^k(c) is introduced as a definition and proved in Lemma A.9 / B.9; it is an identity used to reorganize the value, not an assumption equivalent to the target regret bound. The step sizes eta, gamma, xi are tuning parameters inserted after symbolic bounds are derived in order to balance provable terms; they are not fitted to data and then reported as predictions. Citations to prior work (Jin et al. 2020, Abbasi Yadkori et al. 2013, Slivkins 2024) are external standard results, not self-citations carrying the proof. The flagged concern about Theorem 4.3 — that the proof's summations omit intermediate adversarial-block steps and that the h1 estimator uses the per-step loss rather than a block-cumulative loss — is a potential proof gap or correctness issue, not circularity: it does not make the claimed regret bound equivalent to the model assumptions by construction. No step reduces a fitted parameter to a prediction, no theorem is imported solely from the authors' own prior work, and no ansatz is smuggled in via self-citation. Accordingly, the circularity score is 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 1 invented entities

The paper is a self-contained theory contribution. The only real 'free parameters' are algorithm step sizes tuned to balance provable regret terms. The load-bearing domain assumptions are the fixed-and-known Lambda set and exact stationarity of safe transitions; these are explicit in the model definition. The COM is the key invented construct, justified entirely within the paper.

free parameters (3)
  • eta, gamma in Algorithm 2 = 1 / sqrt(K A^(Lambda+1) S)
    OMD step size and implicit-exploration constant; chosen to balance KL and second-moment terms in the regret bound, not fitted to data.
  • eta, gamma in Algorithm 3 = sqrt(1 / (S K A^(Lambda+1)))
    Tuning constants for the consecutive-block algorithm; chosen to balance the leading regret terms.
  • eta, gamma, xi in Algorithm 4 = eta=K^(-2/3)H^(1/3)S^(Lambda/3-1/3)A^(-Lambda/3-1/3), gamma=K^(-1/3)S^(-Lambda/3-2/3)A^(-2Lambda/3-2/3), xi=K^(-1/3)H^(2
    Tuned to balance the K^(2/3) regret terms in the unknown-Lambda reduction; not empirical fits.
assumptions (5)
  • domain assumption The adversarial steps are confined to a fixed set Lambda of size Lambda in every episode; all other transitions are exactly stationary (p^k_h = p^{stat}_h).
    Central model definition in Section 2; if the adversarial set can drift or non-adversarial transitions vary, the COM decomposition in Lemma A.9 and all regret bounds fail.
  • domain assumption The learner knows Lambda and, for Algorithms 2 and 3, the identity of the adversarial steps; Algorithm 4 removes identity knowledge but still assumes Lambda is known.
    Algorithms 2 and 3 take the adversarial step set as input; Section 4.4 explicitly retains Lambda as prior knowledge and only removes the identity of the steps.
  • domain assumption For Algorithm 3, the Lambda adversarial steps form a consecutive block.
    The sub-policy construction requires a single adversarial block; Section 4.3 states this assumption explicitly.
  • standard math Standard concentration and online-learning results (Hoeffding-Azuma, OMD regret, EXP3, bandit lower bounds) are used as black boxes.
    Invoked throughout the appendices, e.g., Lemmas A.6-A.8, standard EXP3 regret bounds, and classical bandit lower bounds from Slivkins.
  • domain assumption Losses are bounded (in [0,1]) and fully adversarial across episodes.
    The value and regret definitions in Section 2 assume bounded losses; the estimators and concentration bounds rely on boundedness.
invented entities (1)
  • Conditioned occupancy measure (COM) mu_h(s,a,c)
    purpose: A representation of visit probabilities conditioned on realized outcomes of prior adversarial steps; it is the episode-invariant object over which the algorithms optimize.
    A new proof device introduced in Section 4.1. It has no external falsifiable handle; its validity is established only by the paper's own Lemma A.9. This is normal for a mathematical construct, but it is an invented entity rather than an independent benchmark.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Learning in MDPs with Partially Adversarial Transitions and Losses." pith.science (2026). https://pith.science/paper/PJ7HTIVY

@misc{pith2026260209474,
  author       = {Pith},
  title        = {Pith review of: Online Learning in MDPs with Partially Adversarial Transitions and Losses},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PJ7HTIVY}},
  note         = {Machine review of arXiv:2602.09474}
}
abstract

We study reinforcement learning in MDPs whose transition function is stochastic at most steps but may behave adversarially at a fixed subset of $\Lambda$ steps per episode. This model captures environments that are stable except at a few vulnerable points. We introduce \emph{conditioned occupancy measures}, which remain stable across episodes even with adversarial transitions, and use them to design two algorithms. The first handles arbitrary adversarial steps and achieves regret $\tilde{O}(H S^{\Lambda}\sqrt{K S A^{\Lambda+1}})$, where $K$ is the number of episodes, $S$ is the number of state, $A$ is the number of actions and $H$ is the episode's horizon. The second, assuming the adversarial steps are consecutive, improves the dependence on $S$ to $\tilde{O}(H\sqrt{K S^{3} A^{\Lambda+1}})$. We further give a $K^{2/3}$-regret reduction that removes the need to know which steps are the $\Lambda$ adversarial steps. We also characterize the regret of adversarial MDPs in the \emph{fully adversarial} setting ($\Lambda=H-1$) both for full-information and bandit feedback, and provide almost matching upper and lower bounds (slightly strengthen existing lower bounds, and clarify how different feedback structures affect the hardness of learning).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 2 linked inside Pith

  1. [1]

    We’ll now proveG 4 is true w.p at least 1−δ

    is true w.p at least 1−δ(each) from Lemma A.7. We’ll now proveG 4 is true w.p at least 1−δ. We have for everyk∈[K] X h,s,a,c ˆµk h(s, a, c)ˆℓk h(s, a, c) = X h,s,a,c ˆµk h(s, a, c)1k[s, a, c] uk h(s, a, c) +γ ≤ X h,s,a,c 1k[s, a, c] =H Thus, from Hoeffding-Azuma inequality w.p 1−δ: X k,h,s,a,c ˆµk h(s, a, c) ˆℓk h(s, a, c)−E h ˆℓk h(s, a, c) i ≤H s 2Kln 1...

    2020

  2. [4]

    Online learning in episodic markovian decision processes by relative entropy policy search

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

    2013

  3. [7]

    =µ h(sh, ah, c) Equation (4) - for everyh∈Λ,s h, sh+1,a h ∈ Aandc∈ Ch: X ah+1,sh+2 µh+1(sh+1, ah+1, sh+2, c∥(sh, ah, sh+1)) = X ah+1 µh+1(sh+1, ah+1, c∥(sh, ah, sh+1)) =µ h(sh, ah, c) Where the last equation is exactly the same as the proof of Equation (3). Equation (5) - X s,a µ1(s, a,()) = X a µ1(sinit, a,()) = X a π(a|s init) = 1 24 Equation (6) - we f...

    2020

  4. [8]

    42 Forh≥ ˜h2 we have: X c µp,π h (s, a,(s′, σ, s′′))ϱp(c) =q p,π ˜h1 (s′, σ)qp,π h (s, a|s ˜h2 =s ′′)qp,σ ˜h2 (s′′ |s ˜h1 =s ′) =q p,π h (s, a|s ˜h2 =s ′′)qp,π ˜h2 (s′′) =q p,π h (s, a) Lemma B.10.ˆµ1 is in the polytope Proof.Equation (18), forh= 1 ( ˜h1 >2): X a,s′ ˆµ1 2(s, a, s′,()) = X a,s′ 1 S2A = X a 1 SA = X a ˆµ1 1(sinit, a, s,()) = X a,s′ ˆµ1 1(s′...

    2020

  5. [9]

    qpk,πk h (s, a)− X c∈Ch ˆµk h(s, a, c)ϱk(c) ! ¯ℓk h(s, a) # (tower rule) = X k,h,s,a Ek

    ≤ ˜O s KSA ξ ! SinceGis true w.p 1−9δ(Lemma A.8), this concludes the proof. Theorem C.3.Initializing all sub-algorithms in algorithm Algorithm 4 as Algorithm 2 with: η=K −2/3H 1/3SΛ/3−1/3A−Λ/3−1/3 ξ=K −1/3H 2/3S2Λ/3+1/3AΛ/3+1/3 γ=K −1/3S−Λ/3−2/3A−2Λ/3−2/3 We get that the expected regret of algorithm Algorithm 4 is bounded by, E[RK]≤ ˜O K 2/3S2Λ/3+1/3AΛ/3+...

    2024

  6. [10]

    bandit decision step

    Combining this with the transition definition, for episodek∈ K si,h, the episode loss is Θ(H· ˜ℓ(i,h) tk (ak)) wherea k is the action that the learner choose in episodekinsat steph. This equivalent to scaling the expert loss ˜ℓ(i,h) tk (ak) by a factor Θ(H), and thus the regret in these rounds is Ω(H √ TlnA). Summing over the ˜S ¯H= Θ(HS) blocks we get th...

    2024

  7. [2013]

    That is, a tuple (s, a, s′) for each step inΛ h

    15 A Action based conditions A.1 General defintions Ch is the set of conditions in steph. That is, a tuple (s, a, s′) for each step inΛ h. It contains only consistenet conditions, namely ifh ′, h′ + 1∈Λ, the relevant tuples isn’t contradictive. Formally, (c h′)3 = (ch′+1)1. We denote byT h the set of all trajectories ofhsteps. We denote byT c forc∈ Ch to ...

    2020

  8. [2021]

    Corruption robust exploration in episodic reinforcement learning.arXiv preprint arXiv:1911.08689,

    Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun. Corruption robust exploration in episodic reinforcement learning.arXiv preprint arXiv:1911.08689,

    arXiv 1911

Show all 10 references
  1. [2024]

    URLhttps://arxiv.org/abs/1904. 07272. Richard S. Sutton and Andrew G. Barto.Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA,

    1904

  2. [2026]

    (To appear.)

    URLhttps://sites.google.com/view/rlfoundations/home. (To appear.). Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Ba¸ sar. Model-free non- stationary rl: Near-optimal regret and applications in multi-agent rl and inventory control.arXiv preprint arXiv:2010.03161,

    2010 arXiv

Pith tools

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