A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

1 Introduction

• The work gives a polynomial-time algorithm for adversarial MDPs with aggregate feedback beyond the tabular case.The learner observes the total episode loss rather than individual step losses.Source: §1 · p. 1
• The reduction views each policy’s expected state-action features as a linear-bandit action because expected episode loss is linear in that feature vector.The feasible policy-feature set is unknown because it depends on the unknown transition kernel.Source: §1 · p. 2
• The prior discretization approach achieves the optimal K regret rate, but its computation scales with an exponentially large policy class.The introduction identifies whether polynomial-time computation can attain K regret as an open question.Source: §1 · pp. 1–2
• The introduction situates the approach alongside an efficient contextual-bandit reduction and an oracle-efficient linear-bandit method, while noting that the MDP extension lacks an exact oracle.The outer convex set is refined only when a cut preserves containment of the feasible set with high probability.Source: §1 · p. 2
• The approximate separation procedure either constructs a policy mixture approximating a queried feature or returns a cut that refines the outer approximation.The procedure uses a Frank–Wolfe-style method and also generates uncertainty measures for a bias-correction bonus.Source: §1 · p. 2

2 Preliminaries

• The learner chooses a Markov policy over K episodes, while an oblivious adversary fixes losses across episodes and layers.The observed feedback is the episode’s total loss, not the individual step losses.Source: §2 · pp. 2–3
• Transitions and losses are linear in known feature maps, with unknown transition coefficients fixed across episodes and loss coefficients allowed to vary.The features and loss coefficients are norm-bounded.Source: §2 · p. 3
• Stacking expected features across H layers gives dimension p = dH, and feasible policy-feature vectors form a set K that depends on unknown transitions.The reduction relates regret to linear losses over this unknown feasible set.Source: §2 · p. 3
• Regret is eO(d^5 H^(9/2) √K), with total computation polynomial in K, d, H, and A.The guarantee is for adversarial linear MDPs with aggregate bandit feedback.Source: §2 · p. 3

3 Algorithm Overview

• The algorithm maintains an outer approximation O of the feasible set and uses continuous exponential weights to form an exploration distribution.It enlarges the feasible set so O has non-zero volume for the linear-bandit procedure.Source: §3 · pp. 3–4
• It replaces direct sampling from the continuous distribution with a uniform distribution over 2p points having the estimated mean and scaled covariance.Finite support allows Step 2 to process each possible support point before policy sampling.Source: §3 · p. 4
• For each support point, APPROXSEP either returns a policy list with an approximation certificate or a cut to refine O.Cuts are returned only when confidence bounds certify that the point is outside the feasible set.Source: §3 · p. 4
• When all points yield policy lists, the learner samples and executes a policy, then uses a loss estimator and bias-correction bonus to update cumulative estimates.The executed policy’s expected feature approximates the support point selected for it.Source: §3 · p. 4

4 Sketch of Regret Analysis and Bonus Design

• The executed policy’s true expected feature can differ from the mean feature used by the underlying linear-bandit algorithm, producing misspecified feedback.The regret analysis separates feature error, loss-estimator bias, and the correction term.Source: §4 · p. 5
• The feature-error contribution is controlled by approximation accuracy ε_k, while mean-estimation error can be made negligible with sufficiently accurate moment estimation.The cited analysis bounds the feature-error component by a term of order √p ε_k.Source: §4 · pp. 5–6
• The bonus removes a comparator-dependent term from the bias bound and replaces it with comparator-independent overhead O(p^2 ε_k).The text identifies B_k = 10ηpε_k as the correction bonus.Source: §4 · p. 6
• With high probability, shrinking decision sets and a comparator in K ⊆ O allow standard FTRL analysis to bound true regret by perceived regret plus discrepancy.The regret bound separates perceived regret from the bias-and-correction contribution.Source: §4 · p. 6

5.1 Constructing the policy list or excluding the target

• APPROXSEP never cuts a feasible target y ∈ Kζ; if it returns no cut, its policy list approximates y with controlled error.This gives the procedure its separation-or-approximation dichotomy.Source: §5.1 · pp. 8–9

5.2 Planning and evaluating from past transitions

• With probability at least 1 − δ, APPROXLO returns a policy, estimated feature, and error certificate simultaneously for every episode and call.The certificate uses an estimated uncertainty bound and is clipped at 2H.Source: §5.2 · pp. 9, 11
• APPROXLO uses optimistic LSVI with a Gibbs policy, making the map from cost vector c to estimated policy feature Lipschitz.The Lipschitz property supports a bounded log covering number for this mapping class.Source: §5.2 · p. 9
• Feature and uncertainty evaluation use backward policy evaluation; an added bonus guards against underestimating future uncertainty.The estimated uncertainty upper bound is used to choose the approximation tolerance.Source: §5.2 · pp. 10–11

5.3 Final Regret Bound

• The final regret proof bounds accumulated misspecification and plugs that bound into the preceding regret analysis.The supplied passage states that this yields the desired bound but does not provide its explicit rate.Source: §5.3 · p. 11

6 Computation

• MOMENTESTIMATE requires poly(d, H, K, log(1/δ)) calls to the outer-set membership oracle.Its complexity bound is taken from Ito et al. (2019).Source: §6 · p. 11
• A capped-restart version executes a fallback policy if the restart threshold is reached, while the threshold is exceeded only with low probability.The analysis bounds the number of cuts and shows that the repeat count is below the cap with high probability.Source: §6 · p. 11
• APPROXLO runs in poly(d, H, K, A) time, even though the displayed algorithm enumerates state-action updates.The paper notes that an efficient implementation is described separately.Source: §6 · p. 11

A.1 Learning Adversarial MDPs with Linear Structure

• Without a simulator, efficient bandit-feedback regret bounds for adversarial linear MDPs progressed from K14/15 to K3/4, while Liu et al. [2024a] also achieved the optimal K rate with inefficient computation.The paper’s contribution is polynomial computation at the square-root rate and use of cumulative rather than per-step losses.Source: §A.1 · p. 16

A.2 Adversarial RL beyond Linear MDPs

• The reviewed adversarial-RL results extend beyond linear MDPs, but do not provide the polynomial-time square-root guarantee studied here.The appendix discusses low-rank and bilinear classes, among other settings.Source: §A.2 · p. 17

B Complete Algorithm

• Algorithm 4 caps restarts and uses a fallback policy to ensure termination; with high probability, the cap is not reached.The rare bad event contributes negligible expected regret in the analysis.Source: B Complete Algorithm · p. 18

C.1 Properties of continuous exponential weights

• The entropic barrier’s convex conjugate is self-concordant, providing the local Taylor bound used in the continuous-exponential-weights analysis.The proof cites Chewi (2023) and Nemirovski and Todd (2008) for these properties.Source: §C.1 · p. 19

C.2 Bounding bias and bonus

• Under the covariance sandwich assumption, Lemma C.2 bounds loss-estimator bias and local norm, and Lemma C.3 establishes bias–bonus compensation.The proof derives these bounds using the estimator definition and the entropic-barrier identities.Source: §C.2 · pp. 19, 21

• The indicators χk mark whether confidence and moment-estimation guarantees have held, and the valid episodes form a prefix on every sample path.The analysis defines xk as the expected feature vector of the episode policy and sets auxiliary quantities to zero when χk = 0.Source: §C.3 · p. 22
• A nested-region potential bound controls cumulative estimated loss on the realized valid prefix, after which expectations are taken.The regions shrink over time, and the argument uses the potential’s monotonicity together with the tower property.Source: §C.3 · pp. 22–23
• The learning rate is chosen to balance two η-dependent terms while satisfying the local-norm stability condition.The proof absorbs the ηEK term into the d²H²√KEK term; when K < d²H, the trivial regret bound HK is no larger than the target expression.Source: §C.3 · p. 24
• Together, these steps complete the stated regret analysis in Lemma 4.1.Source: §C.3 · p. 24

• The averaging recursion is proved by multiplying by the index and telescoping the resulting terms.Source: D Omitted Proofs in Section 5 · p. 25
• Theorem D.2 provides simultaneous Bellman confidence over episodes, layers, functions, and state-action pairs when its stated condition holds.Source: D Omitted Proofs in Section 5 · p. 25
• The proof of Theorem 5.3 analyzes three least-squares value-iteration tasks using separate function classes and backward-induction arguments.The proof applies uniform Bellman confidence to the three classes and then relates the planning recursion to the returned Gibbs policy.Source: D Omitted Proofs in Section 5 · pp. 25–27
• The proof uses covering-number and Lipschitz bounds to verify the conditions for applying uniform confidence to the three task classes.It bounds the classes’ parameters and uses a parameter grid to construct a cover.Source: D Omitted Proofs in Section 5 · pp. 26–27
• The analysis proves the first bound in (9), bounds the normalized optimization gap, and uses the resulting inequalities to establish the final bound.The supplied proof passages identify these conclusions but do not give their complete expressions.Source: D Omitted Proofs in Section 5 · pp. 27–28

E.1 Moment Estimates

• MOMENTESTIMATE computes approximate mean and covariance for a log-concave density over a convex body in polynomial time.Its guarantee bounds the covariance between one-half and twice the true covariance and controls the mean error in the covariance norm.Source: §E.1 · p. 29

E.2 Number of cuts

• Each target used for a cut lies in the current region and within the stated covariance-norm distance of the distribution mean; each cut removes at least a 1/(2e) fraction of the current mass.The proof uses these properties to bound the number of cuts over episodes.Source: §E.2 · pp. 29–30

E.3 Implementation of Algorithm 3

• Algorithm 3 can be executed without enumerating states or state-action pairs by maintaining the specified value-function parameter vectors and computing them by backward induction.The proof describes this implementation for the planning task and says the other two tasks follow the same manner.Source: §E.3 · pp. 30–31