Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel$-$Young Loss Perspective and Gap-Dependent Regret Analysis

Han Bao; Shinsaku Sakaue; Taira Tsuchiya

Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel$-$Young Loss Perspective and Gap-Dependent Regret Analysis

T0 review · 0 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read For online inverse linear optimization, the paper proves a regret bound of O(1/Δ²) that is independent of the time horizon, provided the agent's decision problems satisfy a Δ-gap condition.

desk verdict A careful, genuinely novel gap-dependent regret bound for inverse linear optimization, with an honest framing of the strong and untested margin assumption that powers it. read the letter →

arxiv 2501.13648 v3 pith:OIUIWV7Y submitted 2025-01-23 cs.LG

Shinsaku Sakaue , Han Bao , Taira Tsuchiya This is my paper · ORCID

classification cs.LG

keywords agentlinearonlineoptimizationapproachemphinverselearning

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

This is a theoretical paper, so the results are mathematical bounds rather than experiments. The main limitation is the gap condition: it must hold for every alternative in every round, which is reasonable for problems with integer-valued scores, like shortest paths, but may fail in other settings.

Extended reading notes

Core claim

Theorem 5.2: Under the Δ-gap condition (Definition 5.1) and the assumption that the agent's choices are optimal for c*, the FTRL algorithm in Algorithm 1 achieves R_T ≤ 2^{5/4} E G^3 / (λ^{3/2} Δ^2), an upper bound on the cumulative total loss that is independent of the time horizon T. If correct, this shows that a structural property of the agent's decision problems, not strong convexity of the losses, can remove the √T dependence.

Load-bearing premise

The Δ-gap condition in Definition 5.1: for every round t and every alternative ŷ in the feasible set B_t, the true objective satisfies ⟨c*, y* − ŷ⟩ ≥ Δ ‖y* − ŷ‖, where y* is the optimal choice for c*. This sharpness condition must hold uniformly across all rounds and all alternatives; it fails when optimal solutions are non-unique or when the objective-value gap grows only sublinearly in the distance to the optimum. The paper argues it holds for integral polytopes and for c* in the interior of a normal cone, but it is not verified for general inverse optimization instances.

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

I read through the paper and the stress-test note, and I agree with the positive verdict. The main result is real: under the Δ-gap condition on the agent's decision problems, the FTRL algorithm in Algorithm 1 achieves a total-loss bound of O(1/Δ²) that does not depend on the horizon T, and the algorithm never needs to know Δ. I checked the key steps — Proposition 3.1 and 3.3, Lemma 5.3, and the self-bounding argument in Theorem 5.2 — and the algebra is consistent. Lemma 5.3, which turns the gap condition into a bound on ‖y_t − ŷ_t‖² by the per-round total loss, is the load-bearing piece, and it works as stated.

The Fenchel–Young perspective is the right way to see why this goes through: the suboptimality loss is a Fenchel–Young loss with Ω the indicator of the feasible set, and the total loss is exactly the linearized regret. This is not a deep new framework, but it is a useful simplification that makes the existing O(√T) bound and the new gap-dependent bound drop out of standard OCO machinery. The offline guarantee in Theorem 4.3, which removes the agent-optimality assumption, is a small but genuine extension over Bärmann et al. (2020), and the online-to-batch proof is clean.

Where I am more cautious than the authors: the Δ-gap condition is strong. It requires every agent problem to have a unique optimal solution and a uniform margin between the optimal and all suboptimal alternatives, across all rounds. Section 5.2 gives two plausible settings — integral polytopes with integral c*, and c* in the interior of a normal cone — but these are narrowly structured. The paper does not test the condition on any real inverse-optimization instance, and it gives no lower bound, so the tightness of O(1/Δ²) is open. These are limitations of scope, not hidden flaws; the assumption is stated explicitly and the analysis is honest about what it needs.

This paper is for readers working on inverse optimization, online learning, or fast rates with structured feedback. It is a serious theoretical contribution that deserves peer review. I would send it out rather than desk-reject, and I expect it to be accepted after the authors clarify the reach of the gap condition and perhaps add a short discussion of lower bounds.

Good to bring to the next group meeting.

Referee Report

0 major / 5 minor

Summary. The paper revisits the online learning formulation of inverse linear optimization introduced by Bärmann et al. (2017). It first shows that the suboptimality loss coincides with a Fenchel–Young loss whose regularizer is the indicator function of the agent's feasible set, and that the cumulative total loss equals the linearized regret of this loss. This perspective immediately yields the standard O(√T) bound for FTRL and, via online-to-batch conversion, an offline guarantee on the suboptimality loss that does not require the agent's observed choices to be optimal for the true objective. The main new result is the gap-dependent analysis: under the Δ-gap condition of Definition 5.1 and the assumption that the agent always chooses an optimal action, the same FTRL algorithm achieves a cumulative total-loss bound of order E D^3/(λ^{3/2}Δ^2), independent of the time horizon T, through a self-bounding argument that combines the adaptive FTRL regret bound with a squared-residual control derived from the gap condition.

Significance. If the results are correct, the paper provides a clean conceptual unification of inverse linear optimization with Fenchel–Young losses, a genuinely broader offline guarantee, and a novel T-independent regret bound that is obtained from a structural property of the agent's optimization problems rather than from strong convexity of the losses. The proofs are detailed and the constants are explicit; I checked the key steps in Lemma 5.3 and Theorem 5.2 and found no gap. The Δ-gap condition is explicitly strong—it forces a unique optimal solution and a uniform margin over all feasible alternatives—and the paper's discussion in Section 5.2 identifies sufficient conditions rather than claiming empirical universality. This limits the practical reach of the result but does not undermine the conditional theorem. The paper is a solid theoretical contribution appropriate for the journal; the only substantive caveat is that the prevalence of the Δ-gap condition on real inverse-optimization instances is not demonstrated.

minor comments (5)

[Section 5.2] In the sentence 'The is nothing but the boundary of normal cones, ...' the word 'The' should be 'This'; the same paragraph contains an ungrammatical fragment and should be rewritten for clarity.
[Definition 5.1] The quantifier structure of the definition is awkward: the condition is written as 'for every t ... it holds that ... for y = arg max ...'; please restate it by first letting y_t be an optimal solution for θ*, then quantifying over ŷ ∈ B_t, and add a sentence noting that the condition forces y_t to be the unique optimal solution.
[Section 5.2] The sufficient conditions for the Δ-gap condition (integral polytopes and normal-cone interiors) are stated in prose and rely on an external lemma; a short formal statement of at least the integral-polytope case, including the resulting value of Δ (e.g., Δ ≥ 1/E), would make the applicability claim easier to verify.
[Proposition 4.1] The formula for the FTRL step-size β_t is difficult to parse in the typeset version, in particular the placement of the factor 2^{1/4} relative to the square root and the division by λ; please restate it as a single explicit expression in both Algorithm 1 and the proposition.
[Section 5.2] The paper would benefit from an explicit acknowledgment that the Δ-gap condition is a strong assumption whose prevalence on real inverse-optimization instances is not demonstrated; the current discussion identifies sufficient conditions but does not quantify how restrictive the uniform margin is.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the gap-dependent bound is a conditional result derived from an explicit Δ-gap assumption via a standard self-bounding FTRL argument.

full rationale

The paper's main result, Theorem 5.2, is a conditional statement: given the Δ-gap condition (Definition 5.1) and optimal agent choices, Algorithm 1's FTRL linearized regret is bounded by 2^{5/4} E G^3/(λ^{3/2}Δ^2). The derivation is self-contained: Lemma 5.3 follows algebraically from optimality of y_t for c* and optimality of ŷ_t for θ̂_t, plus the gap inequality and diameter bounds; Theorem 5.2 combines this with the standard FTRL bound of Proposition 4.1, whose proof is given in Appendix A. Nothing is fitted from the observations and then reported as a prediction; the total loss (5) is defined from the observed (B_t, y_t) and the algorithm's outputs, and the bound holds for all such sequences meeting the stated assumptions. The Fenchel–Young identification in Proposition 3.1 is a reformulation (ℓsub equals the FY loss with Ω = indicator_B), not a circular derivation, and it is used to obtain standard OCO tools. The offline guarantee in Theorem 4.3 is a standard online-to-batch conversion with the proof included. The only self-citations (Sakaue et al. 2024, 2025) are used for comparisons and for a geometric sufficient condition illustrating when the gap assumption may hold; they do not contain the target regret bound, and Theorem 5.2 does not depend on them. The Δ-gap condition is explicitly assumed, not derived, so its strength is a matter of applicability rather than circularity. I find no circular step.

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

No free parameters are fitted to data; the algorithm's λ is a design choice and Δ is an assumed environment parameter, not an estimate. The central claims rest on the Δ-gap condition, a domain assumption introduced for this analysis, plus standard convex analysis and standard OCO tools. No new entities, such as forces, particles, or dimensions, are postulated.

assumptions (4)

domain assumption Each feasible set B_t is non-empty, compact, and has diameter at most E; an oracle can compute argmax_{y in B_t} <c, y> for any c.
Section 2.1 and Theorem 5.2. Needed to define the suboptimality loss and FTRL iterates, and to bound the subgradient norms.
domain assumption The prediction space Θ is a closed convex set containing c*, and in the offline setting 0 is not in Θ.
Section 2.1. Required by the FTRL analysis and to avoid the trivial all-zero prediction that makes the suboptimality loss degenerate.
domain assumption The Δ-gap condition (Definition 5.1) and agent optimality y_t in argmax_{y in B_t} <c*, y>.
Section 5. These structural assumptions produce the T-independent bound in Theorem 5.2; the paper provides examples but no empirical verification.
standard math Standard convex analysis facts: Fenchel-Young inequality, convexity of the conjugate, and Danskin's theorem.
Used in Propositions 2.2, 3.1, and 3.3 to establish convexity of the suboptimality loss and the residual-subgradient property.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel$-$Young Loss Perspective and Gap-Dependent Regret Analysis." pith.science (2026). https://pith.science/paper/OIUIWV7Y

@misc{pith2026250113648,
  author       = {Pith},
  title        = {Pith review of: Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel$-$Young Loss Perspective and Gap-Dependent Regret Analysis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OIUIWV7Y}},
  note         = {Machine review of arXiv:2501.13648}
}

abstract

This paper revisits the online learning approach to inverse linear optimization studied by B\"armann et al. (2017), where the goal is to infer an unknown linear objective function of an agent from sequential observations of the agent's input-output pairs. First, we provide a simple understanding of the online learning approach through its connection to online convex optimization of \emph{Fenchel--Young losses}. As a byproduct, we present an offline guarantee on the \emph{suboptimality loss}, which measures how well predicted objectives explain the agent's choices, without assuming the optimality of the agent's choices. Second, assuming that there is a gap between optimal and suboptimal objective values in the agent's decision problems, we obtain an upper bound independent of the time horizon $T$ on the sum of suboptimality and \emph{estimate losses}, where the latter measures the quality of solutions recommended by predicted objectives. Interestingly, our gap-dependent analysis achieves a faster rate than the standard $O(\sqrt{T})$ regret bound by exploiting structures specific to inverse linear optimization, even though neither the loss functions nor their domains enjoy desirable properties, such as strong convexity.

Figures

Figures reproduced from arXiv: 2501.13648 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 15 canonical work pages

[1]

Inverse optimization

Ahuja, R. K. and Orlin, J. B. (2001). “Inverse optimization” . In: Operations Research 49.5, pp. 771–783 (cited on page 1). Auer, P ., Cesa-Bianchi, N., and Fischer, P . (2002). “Finite-time analysis of the multiarmed bandit problem”. In: Machine Learning 47.2, pp. 235–256 (cited on page 3). Bärmann, A., Martin, A., Pokutta, S., and Schneider, O. (2020). ...

arXiv 2001
[2]

□ B Recovering the Same Bound as Bärmann et al

Therefore, Algorithm 1 with/u1D6FD/u1D461 = 21/4 /u1D435 √ /summationtext.1/u1D461−1 /u1D456=1 ‖/u1D454 /u1D456‖2 /u1D706 attains/u1D445 /u1D447 ≤ 25/4/u1D435 √ 1 /u1D706 /summationtext.1/u1D447 /u1D461=1‖/u1D454/u1D461‖2. □ B Recovering the Same Bound as Bärmann et al. ( 2017, Theorem 3.3) As with Bärmann et al. ( 2017, Theorem 3.3), we assume that the d...

work page 2017
[13]

Inverse problem theory: Methods for data ﬁtting and model parameter estimation

Curran Associates, Inc., pp. 19738–19749 (cited o n page 3). Tarantola, A. (1988). “Inverse problem theory: Methods for data ﬁtting and model parameter estimation”. In: Geophys- ical Journal International 94.1, pp. 167–167 (cited on page 1). Weed, J. (2018). “An explicit analysis of the entropic penal ty in linear programming”. In: Proceedings of the 31st...

work page 1988
[15]

Also, as in Orabona ( 2023, Section 7.6), we have /u1D439 /u1D461( ˆ/u1D450/u1D461) −/u1D439 /u1D461+1 ( ˆ/u1D450/u1D461+1) + ⟨/u1D454/u1D461, ˆ/u1D450/u1D461⟩ ≤ /u1D439 /u1D461( ˆ/u1D450/u1D461+1) −/u1D439 /u1D461+1 ( ˆ/u1D450/u1D461+1) + ⟨/u1D454/u1D461, ˆ/u1D450/u1D461⟩ =/u1D713 /u1D461( ˆ/u1D450/u1D461+1) + /u1D461−1/summationdisplay.1 /u1D456=1 ⟨/u1D...

work page 2023
[17]

We let /u1D6FD/u1D447 +1 = /u1D6FD/u1D447 , which does not aﬀect the analysis (Orabona, 2023, Remark 7.3)

with the following choice of /u1D6FD/u1D461: /u1D6FD/u1D461 = 1 /u1D43B √ /u1D706 /radicaltp /radicalvertex √ /u1D43E 2 + /u1D461−1/summationdisplay.1 /u1D456=1 ‖/u1D454/u1D456‖2, which is also non-decreasing. We let /u1D6FD/u1D447 +1 = /u1D6FD/u1D447 , which does not aﬀect the analysis (Orabona, 2023, Remark 7.3). From (9), (10), and /u1D6FD/u1D447 +1 = ...

work page 2023
[18]

15 C Proof of Theorem 4.3 Proof. Since the suboptimality loss ℓsub is convex due to Propositions 2.2 and 3.1, the claim follows from the standard online-to-batch conversion scheme (e.g., Orabona 2023, Theorem 3.1), which we detail below for completeness. Sinc e ˆ/u1D450/u1D461 is independent of {(/u1D44B /u1D456,/u1D465/u1D456)}/u1D456≥/u1D461, E [ ℓsub /...

work page 2023
[31]

Smart “predict, th en optimize

Curran Associates, Inc., pp. 86–95 (cited on page 3). Elmachtoub, A. N. and Grigas, P . (2022). “Smart “predict, th en optimize””. In: Management Science 68.1, pp. 9–26 (cited on page 3). Gaillard, P ., Stoltz, G., and van Erven, T. (2014). “A second -order bound with excess losses”. In: Proceedings of the 27th Conference on Learning Theory . Vol

work page 2022
[33]

Online learn ing from optimal actions

Curran Associates, Inc., pp. 9508– 9519 (cited on page 3). Besbes, O., Fonseca, Y ., and Lobel, I. (2021). “Online learn ing from optimal actions”. In: Proceedings of the 34th Conference on Learning Theory . Vol

work page 2021

Show all 18 references

[35]

Logarithmic re gret algorithms for online convex optimization

PMLR, pp. 176–196 (cited on page 10). Hazan, E., Agarwal, A., and Kale, S. (2007). “Logarithmic re gret algorithms for online convex optimization”. In: Machine Learning 69.2, pp. 169–192 (cited on pages 3, 8). Heuberger, C. (2004). “Inverse combinatorial optimizatio n: A surve...

2007
[37]

Onlin e structured prediction with Fenchel–Young losses and improved surrogate regret for online multiclass classi ﬁcation with logistic loss

Curran Associates, Inc., pp. 79381–79409 (cited o n page 11). Sakaue, S., Bao, H., Tsuchiya, T., and Oki, T. (2024). “Onlin e structured prediction with Fenchel–Young losses and improved surrogate regret for online multiclass classi ﬁcation with logistic loss”. In: Proceedings...

2024
[70]

Learning with diﬀerentiable pertub ed optimizers

PMLR, pp. 400–410 (cited on pages 1– 7, 9, 15). Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J.-P., and Bach, F. (2020). “Learning with diﬀerentiable pertub ed optimizers”. In: Advances in Neural Information Processing Systems . Vol

2020
[75]

Melding the d ata-decisions pipeline: Decision-focused learning for combinatorial optimization

PMLR, pp. 1841–1855 (cited on page 10). Wilder, B., Dilkina, B., and Tambe, M. (2019). “Melding the d ata-decisions pipeline: Decision-focused learning for combinatorial optimization”. In: Proceedings of the 33rd AAAI Conference on Artiﬁcial Intell igence. Vol. 33, pp. 1658–16...

2019
[97]

The theory of max-min, with applicat ions

PMLR, pp. 1446–1454 (cited on page 8). Danskin, J. M. (1966). “The theory of max-min, with applicat ions”. In: SIAM Journal on Applied Mathematics 14.4, pp. 641–664 (cited on page 4). Dong, C., Chen, Y ., and Zeng, B. (2018). “Generalized invers e optimization through online l...

1966
[134]

Contextual inverse optimization: Oﬄine and onli ne learning

PMLR, pp. 586–586 (cited on page 3). – (2023). “Contextual inverse optimization: Oﬄine and onli ne learning”. In: Operations Research 0.0, null (cited on pages 3, 9). Blondel, M., Martins, A. F. T., and Niculae, V . (2020). “Learning with Fenchel–Y oung losses”. In: Journal of...

2023 arXiv
[139]

Asymptotically eﬃcient a daptive allocation rules

PMLR, pp. 4687–4697 (cited on page 8). Lai, T. L. and Robbins, H. (1985). “Asymptotically eﬃcient a daptive allocation rules”. In: Advances in Applied Mathematics 6.1, pp. 4–22 (cited on page 3). Mishra, S. K., Raj, A., and Vaswani, S. (2024). “From inverse optimization to fea...

1985
[202]

Learning line ar programs from optimal decisions

PMLR, pp. 32886–32912 (cited on pages 2, 3). Tan, Y ., Terekhov, D., and Delong, A. (2020). “Learning line ar programs from optimal decisions”. In: Advances in Neural Information Processing Systems. Vol

2020
[235]

Data-driven inverse optimization with imperfect information

PMLR, pp. 35805–35828 (cited on pages 2, 3). Mohajerin Esfahani, P ., Shaﬁeezadeh-Abadeh, S., Hanasusa nto, G. A., and Kuhn, D. (2018). “Data-driven inverse optimization with imperfect information”. In: Mathematical Programming 167, pp. 191–234 (cited on page 2). Orabona, F. (...

2018 arXiv
[247]

Onlin e inverse linear optimization: Improved regret bound, robustness to suboptimality, and toward tight regret analy sis

PMLR, pp. 4458–4486 (cited on pages 3, 11). Sakaue, S., Tsuchiya, T., Bao, H., and Oki, T. (2025). “Onlin e inverse linear optimization: Improved regret bound, robustness to suboptimality, and toward tight regret analy sis”. In: arXiv:2501.14349 (cited on page 3). Sun, C., Liu...

2025 arXiv

Pith tools

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

[1] [1]

Inverse optimization

Ahuja, R. K. and Orlin, J. B. (2001). “Inverse optimization” . In: Operations Research 49.5, pp. 771–783 (cited on page 1). Auer, P ., Cesa-Bianchi, N., and Fischer, P . (2002). “Finite-time analysis of the multiarmed bandit problem”. In: Machine Learning 47.2, pp. 235–256 (cited on page 3). Bärmann, A., Martin, A., Pokutta, S., and Schneider, O. (2020). ...

arXiv 2001

[2] [2]

□ B Recovering the Same Bound as Bärmann et al

Therefore, Algorithm 1 with/u1D6FD/u1D461 = 21/4 /u1D435 √ /summationtext.1/u1D461−1 /u1D456=1 ‖/u1D454 /u1D456‖2 /u1D706 attains/u1D445 /u1D447 ≤ 25/4/u1D435 √ 1 /u1D706 /summationtext.1/u1D447 /u1D461=1‖/u1D454/u1D461‖2. □ B Recovering the Same Bound as Bärmann et al. ( 2017, Theorem 3.3) As with Bärmann et al. ( 2017, Theorem 3.3), we assume that the d...

work page 2017

[3] [13]

Inverse problem theory: Methods for data ﬁtting and model parameter estimation

Curran Associates, Inc., pp. 19738–19749 (cited o n page 3). Tarantola, A. (1988). “Inverse problem theory: Methods for data ﬁtting and model parameter estimation”. In: Geophys- ical Journal International 94.1, pp. 167–167 (cited on page 1). Weed, J. (2018). “An explicit analysis of the entropic penal ty in linear programming”. In: Proceedings of the 31st...

work page 1988

[4] [15]

Also, as in Orabona ( 2023, Section 7.6), we have /u1D439 /u1D461( ˆ/u1D450/u1D461) −/u1D439 /u1D461+1 ( ˆ/u1D450/u1D461+1) + ⟨/u1D454/u1D461, ˆ/u1D450/u1D461⟩ ≤ /u1D439 /u1D461( ˆ/u1D450/u1D461+1) −/u1D439 /u1D461+1 ( ˆ/u1D450/u1D461+1) + ⟨/u1D454/u1D461, ˆ/u1D450/u1D461⟩ =/u1D713 /u1D461( ˆ/u1D450/u1D461+1) + /u1D461−1/summationdisplay.1 /u1D456=1 ⟨/u1D...

work page 2023

[5] [17]

We let /u1D6FD/u1D447 +1 = /u1D6FD/u1D447 , which does not aﬀect the analysis (Orabona, 2023, Remark 7.3)

with the following choice of /u1D6FD/u1D461: /u1D6FD/u1D461 = 1 /u1D43B √ /u1D706 /radicaltp /radicalvertex √ /u1D43E 2 + /u1D461−1/summationdisplay.1 /u1D456=1 ‖/u1D454/u1D456‖2, which is also non-decreasing. We let /u1D6FD/u1D447 +1 = /u1D6FD/u1D447 , which does not aﬀect the analysis (Orabona, 2023, Remark 7.3). From (9), (10), and /u1D6FD/u1D447 +1 = ...

work page 2023

[6] [18]

15 C Proof of Theorem 4.3 Proof. Since the suboptimality loss ℓsub is convex due to Propositions 2.2 and 3.1, the claim follows from the standard online-to-batch conversion scheme (e.g., Orabona 2023, Theorem 3.1), which we detail below for completeness. Sinc e ˆ/u1D450/u1D461 is independent of {(/u1D44B /u1D456,/u1D465/u1D456)}/u1D456≥/u1D461, E [ ℓsub /...

work page 2023

[7] [31]

Smart “predict, th en optimize

Curran Associates, Inc., pp. 86–95 (cited on page 3). Elmachtoub, A. N. and Grigas, P . (2022). “Smart “predict, th en optimize””. In: Management Science 68.1, pp. 9–26 (cited on page 3). Gaillard, P ., Stoltz, G., and van Erven, T. (2014). “A second -order bound with excess losses”. In: Proceedings of the 27th Conference on Learning Theory . Vol

work page 2022

[8] [33]

Online learn ing from optimal actions

Curran Associates, Inc., pp. 9508– 9519 (cited on page 3). Besbes, O., Fonseca, Y ., and Lobel, I. (2021). “Online learn ing from optimal actions”. In: Proceedings of the 34th Conference on Learning Theory . Vol

work page 2021