PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition

Long-Fei Li, Peng Zhao, Zhi-Hua Zhou

arXiv:2403.04568v1cs.LGstat.ML

TL;DR

This paper studies adversarial linear mixture MDPs with bandit feedback and unknown transitions. It proposes an all-state least-squares transition estimator and a concentration result for non-independent noises, and reports a strict improvement over Zhao et al. (2023a).

  • Problem

    The paper studies learning in adversarial MDPs, where losses may change arbitrarily, with bandit feedback and unknown transitions.

    Source: §1 · pp. 1–2

  • Method

    A new least-squares estimator uses visitation information from all states, paired with self-normalized concentration tailored to non-independent noises.

    Source: §1 · p. 2

  • Results

    The proposed algorithm strictly improves the previously best-known result of Zhao et al. (2023a).

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The result makes a step toward closing the gap between upper and lower bounds.

    Source: §1 · p. 2

    Regret remains suboptimal in its dependence on S, and closing that gap is left as an open question.

    Source: §5.1 · p. 7

Abstract

from arXiv · show

We study reinforcement learning with linear function approximation, unknown transition, and adversarial losses in the bandit feedback setting. Specifically, we focus on linear mixture MDPs whose transition kernel is a linear mixture model. We propose a new algorithm that attains an $\widetilde{O}(d\sqrt{HS^3K} + \sqrt{HSAK})$ regret with high probability, where $d$ is the dimension of feature mappings, $S$ is the size of state space, $A$ is the size of action space, $H$ is the episode length and $K$ is the number of episodes. Our result strictly improves the previous best-known $\widetilde{O}(dS^2 \sqrt{K} + \sqrt{HSAK})$ result in Zhao et al. (2023a) since $H \leq S$ holds by the layered MDP structure. Our advancements are primarily attributed to (i) a new least square estimator for the transition parameter that leverages the visit information of all states, as opposed to only one state in prior work, and (ii) a new self-normalized concentration tailored specifically to handle non-independent noises, originally proposed in the dynamic assortment area and firstly applied in reinforcement learning to handle correlations between different states.

1 INTRODUCTION

Adversarial losses and large state or action spaces motivate studying linear-function-approximation MDPs with unknown transitions and bandit feedback. The paper introduces an algorithm for linear mixture MDPs, using all-state visitation data and a concentration result for correlated state information.

1 INTRODUCTION

  • Linear mixture MDPs are a focus because adversarial-MDP research largely studies tabular settings, despite large or even infinite state and action spaces.The model uses a linear mixture transition kernel and is distinct from linear MDPs.Source: §1 · p. 1
  • Prior work on unknown-transition linear mixture MDPs with bandit feedback leaves a gap to the lower bound, while full-information results address a different feedback setting.Cai et al. (2020) and He et al. (2022) study full-information feedback; Zhao et al. (2023a) study bandit feedback.Source: §1 · pp. 1–2
  • The proposed algorithm strictly improves Zhao et al. (2023a) for unknown-transition, bandit-feedback linear mixture MDPs, using H ≤ S in the layered setting.The authors also describe the result as a step toward closing the upper- and lower-bound gap.Source: §1 · p. 2
  • A new least-square estimator uses visitation information from all states rather than only the single state used by Zhao et al. (2023a).The accompanying self-normalized concentration lemma is tailored to non-independent noises and adapts a result from dynamic assortment to state correlations.Source: §1 · p. 2

2 RELATED WORK

Related work spans adversarial MDPs with varied transition knowledge and feedback, as well as linear-function-approximation models. This paper focuses on the unknown-transition, bandit-feedback linear mixture setting.

RL with adversarial losses

  • Adversarial tabular MDP studies include policy-optimization and occupancy-measure approaches, with results varying by transition knowledge and feedback.The literature also contains an unknown-transition, bandit-feedback result without the reachability assumption used in an earlier approach.Source: §2 · p. 3

RL with adversarial losses and linear function approximation

  • Prior adversarial-RL work with linear function approximation divides between linear MDPs and linear mixture MDPs, with different transition parameterizations.Linear MDPs parameterize transitions and losses using a state-action feature map; linear mixture MDPs parameterize the transition kernel using a state-action-next-state feature map.Source: §2 · p. 3
  • For linear mixture MDPs with unknown transitions and bandit feedback, Zhao et al. (2023a) provide the prior upper bound, which this paper improves toward the lower bound.Earlier linear-mixture results consider full-information feedback, including a minimax-optimal result by He et al. (2022).Source: §2 · p. 3

3 PROBLEM SETUP

The setup is episodic adversarial reinforcement learning with bandit feedback, unknown transitions, and a layered state space. The paper models transitions as a linear mixture and uses occupancy measures to express the learning objective as online linear optimization.

3 PROBLEM SETUP

  • The MDP has H + 1 disjoint layers, singleton initial and terminal layers, and transitions only between adjacent layers.The episode length is H.Source: §3 · p. 4
  • The learner interacts for K episodes, observes losses only for visited state-action pairs, and seeks to minimize regret against the optimal policy.Loss functions may be chosen adversarially; transitions and policy choices contribute randomness to expected loss.Source: §3 · p. 4
  • In a linear mixture MDP, the transition kernel is linear in a known feature mapping, with unknown parameter vectors.The feature mapping has norm at most 1, and the parameter vectors are bounded by B.Source: §3 · p. 4
  • An occupancy measure records state-action visitation probabilities, and the paper uses it to rewrite expected loss and regret as online linear optimization.Valid occupancy measures obey layer-wise flow constraints and induce policies.Source: §3 · p. 4

4 THE PROPOSED ALGORITHM

VLSUOB-REPS estimates the unknown transition and maintains confidence sets, constructs bandit loss estimators, and updates occupancy measures with online mirror descent.

4.1 Transition Estimator

  • Because occupancy measures depend on the transition, value-targeted regression is insufficient; the estimator uses all-state visit data and concentration tailored to correlated noise.The resulting transition confidence set is tighter than Zhao et al. (2023a)'s, as M_k,h ⪯ Λ_k,h.Source: §4.1 · pp. 5–6

4.2 Loss Estimator

  • The bandit loss estimator uses an upper occupancy bound and an exploration adjustment, yielding an underestimate of the loss with high probability.The estimator replaces the unknown occupancy with its upper bound and adds γ to the denominator.Source: §4.2 · p. 7

4.3 Online Mirror Descent

  • Online mirror descent updates occupancy measures over the space induced by the transition confidence set, using the estimated losses to form the next policy.The update uses unnormalized negative entropy as its regularizer.Source: §4.3 · p. 7

5 REGRET GUARANTEE

The regret analysis establishes an upper bound that improves on Zhao et al. (2023a) under the layered-MDP condition H ≤ S. It attributes the occupancy-measure bound to using transition information from all states and develops the corresponding regret proof.

5.1 Regret Upper Bound

  • The algorithm’s high-probability regret upper bound improves on Zhao et al. (2023a) because H ≤ S in layered MDPs.The supplied theorem passage gives probability at least 1 − 5ζ but does not include the bound’s expression.Source: §5.1 · p. 7

5.2 Occupancy Measure Difference

  • The occupancy-measure bound improves on Zhao et al. (2023a) by replacing an S dependence with H, where H ≤ S.The analysis uses transition information from all states rather than only the next-layer state with maximum uncertainty; it still retains dependence on S.Source: §5.2 · p. 8
  • The proof relates occupancy-measure error to transition-estimation error, whose cumulative bound is the main difference from Zhao et al. (2023a).The prior analysis bounds other states’ estimation errors using the most uncertain next-layer state; this work bounds the cumulative error directly using all states.Source: §5.2 · p. 8

5.3 Proof Sketch of Theorem 1

  • The regret proof decomposes regret into four terms: online optimization regret, Error, Bias-I, and Bias-II.Online Mirror Descent controls the optimization term, implicit-exploration concentration bounds Bias-II, and occupancy-measure differences inform Error and Bias-I.Source: §5.3 · p. 9
  • The analysis bounds Error using the occupancy-measure lemma and bounds Bias-I through loss-estimation accuracy on frequently visited state-action pairs.The proof also uses Azuma-Hoeffding concentration for a remaining term in Bias-I.Source: §5.3 · p. 9

6 CONCLUSION

The paper studies adversarial linear mixture MDPs with bandit feedback and unknown transitions, proposing an algorithm with a high-probability regret guarantee. Its estimator uses all-state visitation information, while a new self-normalized concentration handles non-independent noises; dependence on S remains suboptimal.

6 CONCLUSION

  • The proposed algorithm achieves a high-probability regret bound that strictly improves on the previously best-known result of Zhao et al. (2023a).The conclusion also reports a byproduct improvement over the best-known tabular-MDP result when d ≤ sqrt(HA/S).Source: §6 · p. 9
  • A new least-squares estimator uses visitation information from all states, paired with self-normalized concentration for non-independent noises.The comparison is with Zhao et al. (2023a), whose estimator uses only a single state’s visitation information.Source: §6 · p. 9
  • The dependence on S remains suboptimal, and closing that gap is an open problem.The conclusion also identifies extending dynamic-regret results from full-information to bandit feedback as future work.Source: §6 · p. 9

A Proof of Lemma 1

  • The appendix presents a proof of Lemma 1 as a simplified version of P´erivier and Goyal (2022, Theorem C.6).Source: A Proof of Lemma 1 · p. 12

A.1 Main Proof

The appendix proof establishes a supermartingale argument for concentration with non-independent variables, then derives the stated probability bound. A separate proof treats Lemma 8 using one-hot observations and conditional variance bounds.

A.1 Main Proof

  • The proof’s key step is showing that M_t(ξ) remains a supermartingale despite z_i combining non-independent variables.The appendix states that M_t is a non-negative supermartingale and uses this property in the concentration proof.Source: §A.1 · p. 12
  • The proof introduces truncated normal densities and a lemma bounding their normalization-constant ratio before obtaining a probability bound for all t.The density supports are balls of radii 1/2 and 1/4; the proof concludes with probability at least 1 − ζ.Source: §A.1 · pp. 12–13

A.2 Proof of Lemma 8

  • For Lemma 8, the proof uses that δ_i is one-hot, with conditional selection probabilities p_i,j, to express the conditional variance of ξᵀz_i.Source: §A.2 · p. 13
  • The argument bounds the exponential term using |ξᵀz_t| ≤ 1 and conditional variance control, then completes the supermartingale proof.The bound uses ∥ξ∥ ≤ 1/2 and ∥x_t,j∥ ≤ 1.Source: §A.2 · p. 14

B Proof of Lemma 2

The proof constructs the transition-parameter estimator by aggregating observed next-state indicators and feature mappings across states. Self-normalized concentration and a determinant-trace inequality establish confidence-set coverage; the following section begins the proof of Lemma 3.

B Proof of Lemma 2

  • The estimator’s covariance matrix aggregates feature outer products across observed next states, while its parameter estimate combines transition probabilities and noise-weighted features.The supplied display defines Λ_k,h and θ̂_k,h using sums over next-layer states and previous episodes.Source: B Proof of Lemma 2 · p. 14
  • Self-normalized concentration and the determinant-trace inequality establish that θ*_h belongs to C_k,h with probability at least 1 − ζ/H.A union bound over h = 1, …, H completes the confidence-set argument.Source: B Proof of Lemma 2 · p. 15

C Proof of Lemma 3

C.1 Main Proof

The proof bounds transition error using auxiliary lemmas and norm inequalities. The cited prior proof of Lemma 4 is reproduced for self-containedness.

C.1 Main Proof

  • The transition-kernel difference has L1 norm at most 2, by bounding each kernel's L1 norm.The proof attributes the step to the fact that both distributions have L1 norm 1.Source: §C.1 · p. 15
  • The final bound uses Lemma 5, an elliptical potential lemma, and the condition S ≤ K; otherwise the HSAK bound is vacuous.The proof also uses λK+1 = d log((K + 1)S) and βK = O(d log(KS)).Source: §C.1 · p. 16

C.2 Proof of Lemma 4

  • The proof of Lemma 4 follows Zhao et al. (2023a, Lemma 3) and is included for self-containedness.Its final inequality uses Holder’s inequality, Lemma 2, and the bound on the pointwise transition difference.Source: §C.2 · p. 16

C.3 Proof of Lemma 5

The proof develops bounds by relating transition-error terms to visits and applying a martingale concentration argument across layers.

C.3 Proof of Lemma 5

  • The proof treats Ik(s, a) as the indicator that state-action pair (s, a) is visited in episode k.This indicator is used when bounding Term-I.Source: §C.3 · p. 18
  • The observations oi,j define the filtration Fk,h used in the proof, and Yk,m is bounded above by 1.The passage identifies observations as state, action, and observed loss tuples.Source: §C.3 · p. 18
  • A martingale bound is applied for each layer, then a union bound gives probability at least 1 − ζ across m = 1, . . . , H.The resulting inequality includes a 4Sm+1 log(H/ζ) term.Source: §C.3 · p. 18

D Proof of Theorem 1

Section D introduces the proof of Theorem 1.

D Proof of Theorem 1

D.1 Main Proof

The proof decomposes regret into error, bias, and regret terms, then bounds the latter two with separate lemmas. Supporting arguments include occupancy bounds and an exponential update analysis.

D.1 Main Proof

  • Regret is written as the sum of occupancy-measure differences against losses and decomposed into Error and Bias-I, Bias-II, and Regret terms.The Error and Bias-I bounds are given in Section 5; Lemmas 10 and 11 bound Bias-II and Regret.Source: §D.1 · p. 19

D.2 Proof of Lemma 10

  • Under the event θ∗h ∈ Ck,h, the proof uses qk(s, a) ≤ uk(s, a) to bound the Bias-II term.The argument applies a union bound over state-action pairs.Source: §D.2 · p. 19

D.3 Proof of Lemma 11

  • The update analysis writes the next estimate as bqk+1(s, a) exp(−ηbℓk(s, a)) and bounds the cumulative terms by telescoping.The proof invokes the three-point equality and generalized Pythagorean theorem.Source: §D.3 · p. 20

E Supporting Lemmas

  • The supporting lemmas include martingale and self-normalized concentration results, a determinant-trace bound, and a generalized elliptical potential lemma designed for the analysis.The generalized lemma is introduced after the standard supporting concentration and determinant-trace results.Source: E Supporting Lemmas · p. 21

Related papers

Loading 2403.04568v1…