- Rating
- 3
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies adversarial linear MDPs with unknown transitions and aggregate bandit feedback, where the learner observes only the total episode loss. It obtains expected regret with polynomial computation. Previous work by Liu et al. achieves either regret with an inefficient algorithm or regret with an efficient algorithm.
At a high level, the algorithm represents each policy by its expected feature vector, reducing the problem to a linear bandit problem over an unknown feasible set. It runs a linear bandit algorithm over an outer convex approximation of this set and refines the approximation using separating cuts. To do this, the authors develop ApproxSep, which either returns a certified cut or constructs a policy mixture approximating a queried feature vector.
Critical strengths
The main result addresses a significant gap in prior work by achieving the optimal dependence on with polynomial computation.
I also find the techniques interesting. The method combines approximate linear optimization from transition data, certified cuts, policy mixtures, and bias correction to avoid enumerating an exponentially large policy class. In particular, the analysis connects the approximation certificates to uncertainty under the policies actually executed, allowing accumulated error to be controlled through an elliptical-potential argument.
Critical weaknesses
Some algorithmic choices are insufficiently motivated. The paper provides formal guarantees, but more intuition would help explain why the finite-support exploration distribution and the particular Frank–Wolfe update in ApproxSep are appropriate. The limited explanation makes the algorithm harder to understand and assess.
Questions for authors
Why use the particular support points instead of sampling directly from ? A finite batch sampled from could also be processed by ApproxSep. Could the authors explain which properties of the support construction are needed for the regret and cut-complexity analyses, and clarify its connection to SCRiBLe?
Could the authors provide intuition for choosing the step size in the ApproxSep update ?
Although Liu et al. assume per-step bandit feedback, their inefficient exponential-weights algorithm appears to use losses only through . Their transition estimation uses the observed trajectory. Does any component require observing individual per-step losses? If not, please clarify in the introduction that their inefficient algorithm is also compatible with aggregate feedback, while the present contribution achieves this regret rate with polynomial computation.
Could the authors explain which steps in the analysis lead to the large dependence on and ?
Could the authors provide an explicit bound on the total computational complexity in , including moment estimation, repeated cuts, and LSVI calls?
3 comments
Question 4:
Could the authors explain which steps in the analysis lead to the large dependence on and ?
Answer:
The large dimension and horizon factors mainly come from computing reliable bounds on policy-feature estimation errors and correcting the resulting bias in loss estimation.
First, Algorithm 3 incurs a confidence factor for planning and feature estimation, and an additional factor to obtain a computable upper bound on the uncertainty encountered by the returned policy. Squaring the resulting error bounds and summing over executed trajectories gives as shown in Section 5.3.
Second, the bias-correction analysis in Lemma 4.1 contributes a factor , giving the dominant regret term
Question 5:
Could the authors provide an explicit bound on the total computational complexity in , including moment estimation, repeated cuts, and LSVI calls?
Answer:
Let . Algorithm 4 limits each episode to at most preparation attempts. Thus, over episodes, there are at most preparation attempts, hence at most moment-estimation calls, calls to ApproxSep, and calls to ApproxLO.
All ApproxLO calls within an episode use the same transition data, so we can reuse the matrices across these calls. Each ApproxLO call then costs including vector-valued feature evaluation.
Moment estimation uses batches of samples from to estimate its mean and covariance. Theorem 4 of Ito et al. (2019) gives a sampler with total-variation error and cost per sample. Taking gives per batch. In our implementation, checking whether means checking the stored cut inequalities and the initial bounding ball, costing . Evaluating is a length- inner product, costing . Thus, the total moment-estimation cost is Rank-one updates to the covariance inverses cost per observed transition, hence in total. Combining the three contributions gives the conservative total arithmetic bound
I thank the authors for their detailed response. The authors' response has addressed my concerns regarding several motivations behind the algorithmic design. In my opinion, achieving optimal guarantees for adversarial linear MDPs under bandit feedback with a computationally efficient algorithm is a meaningful contribution to RL theory. Therefore, I would like to maintain my positive assessment of this paper.
We thank the reviewer for the valuable feedback. You questions are elaborated below.
Question 1:
Answer:
Following Ito et al. (2019), we use the 2p symmetric points Yi,±=μk±c0Σk1/2ei,,p=dH. These perturbations explore all feature directions around the estimated mean, with scales determined by the covariance of qk, enabling loss estimation from bandit feedback. The symmetric construction provides two properties needed in our analysis.
First, conditional on the moment estimates, uniform sampling over these points gives exactly mean μk and covariance (c02/p)Σk. These identities let us compute the expected loss estimator and control its bias (Lemma B.2). Using a random batch with the same estimator would introduce additional errors from the batch's empirical moments.
Second, when the moment estimates are accurate, every point is close to the mean of qk in its covariance norm. Any certified cut excluding such a point therefore removes a constant fraction of the current probability mass, yielding the cut bound in Lemma D.3. Direct samples from qk can lie far from the mean, so excluding one need not remove a constant fraction of the mass.
SCRiBLe explores using perturbations scaled by the inverse of a Hessian matrix. For the entropic barrier FO, ∇2FO(μk)=Σk−1. We implement the inverse-Hessian using the estimated covariance Σk.
Question 2:
Answer:
The choice γj=1/j makes the iterate a uniform average and matches the uniform sampling of policies for execution:
xM=M1∑j=1Mϕj,EJ∼Unif[M][ΔJ2]=M1∑j=1MΔj2.
Lemma 5.2 bounds the mixture's feature error using this same average of squared estimation error. Thus the error weights in the analysis are exactly the execution probabilities, allowing collected trajectories to control the cumulative error through exploration.
Similar step size is used in the standard Frank-Wolfe algorithm [1]. They choose γj=2/(j+2), which is of the same order as ours. Theirs allows a slightly better convergence rate (in terms of log-terms), while we use the 1/j for simplicity, as it leads to a uniform sampling as discussed above.
[1] Bubeck, S., 2015. Convex Optimization: Algorithms and Complexity.
Question 3:
Answer:
Liu et al.'s algorithm can also handle aggregate-feedback. We will acknowledge its aggregate-feedback compatibility in the introduction and identify polynomial computation with K regret as our contribution.