PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

Shinsaku Sakaue

arXiv:2609.26978v1stat.MLcs.DScs.LG

TL;DR

In online inverse linear optimization, the learner sees optimal actions but no numerical utility values, and must control regret as the number of rounds grows. The paper uses multiscale matrix weights and obtains expected regret at most 221√d for every horizon.

  • Problem

    The question is how regret grows with dimension when a learner observes optimal actions but no numerical utility values over an unrestricted number of rounds.

    Source: §1 · p. 1

  • Method

    The algorithm uses pairwise action comparisons and matrix weights on polynomial feature spaces at geometrically spaced scales to choose recommendation distributions.

    Source: §2.3 · p. 6

  • Results

    Expected regret is at most 221√d for every horizon; the minimax rate is Θ(√d), matching the lower bound for T≥d.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    Under unit-ball normalization, the dimension dependence is optimal up to a constant factor for horizons T≥d.

    Source: §1 · pp. 1–2

    Whether the same regret order is achievable in time polynomial in dimension, horizon, and input length remains open.

    Source: §7 · p. 15

Abstract

from arXiv · show

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the $d$-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is $O(\sqrt d)$ in expectation for every time horizon, without knowledge of the horizon. The dependence on $d$ is optimal up to a constant factor by the known $\Omega(\sqrt d)$ lower bound for horizons $T\ge d$. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the $O(\sqrt d)$ regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.

1 Introduction

The paper studies online inverse linear optimization, where decisions reveal an optimal action but not utility values, and establishes a horizon-independent expected-regret bound with optimal dimension dependence under unit-ball normalization. It situates this result among prior online-learning guarantees and related inverse-optimization settings.

1 Introduction

  • Each round presents an action set; the learner recommends an action, then receives an action maximizing the same fixed unknown linear utility, without numerical utility values.The paper asks how cumulative utility shortfall scales with dimension when the number of rounds is unrestricted.Source: §1 · p. 1
  • The algorithm achieves O(√d) expected regret for every horizon, matching the Ω(√d) lower bound for T ≥ d and improving on prior O(d) upper bounds.The guarantee assumes the utility vector and actions have Euclidean norm at most one.Source: §1 · pp. 1–2
  • With rational oracle outputs and feedback actions, an oracle-relative implementation preserves the regret bound and terminates each round, but polynomial running time remains open.The implementation accesses action sets through a linear-optimization oracle.Source: §1 · p. 3

1.1 Related Work

  • Prior online inverse-optimization bounds include O(d log T) and O(d^4 log T), while horizon-independent guarantees have also been obtained with exponential dependence on dimension.The paper contrasts these results with its horizon-independent O(√d) expected-regret guarantee.Source: §1 · p. 2, §1.1 · p. 3
  • Unlike some prior horizon-independent guarantees, this result permits arbitrary compact action sets and ties without positive-margin or common integer-lattice assumptions.It does not claim finitely many suboptimal recommendations.Source: §1.1 · p. 3
  • Contextual search predicts hidden-function values from revealed directions, whereas this learner recommends an action before the comparison direction is known.The paper also distinguishes its adaptive action sets from an online guarantee under i.i.d. contexts.Source: §1.1 · p. 4

1 Introduction

  • The learner uses pairwise action comparisons and polynomial comparison matrices across scales, rather than recommending a maximizer of an estimated utility vector.The comparisons depend on actions; the unknown utility enters their quadratic forms only in the analysis.Source: §1 · p. 3, §1.1 · p. 4

2 Model and Main Results

The section defines an online protocol in which the learner recommends from compact action sets and receives an optimal action as feedback, and measures regret as cumulative utility shortfall. It establishes a horizon-independent expected-regret bound and outlines a multiscale matrix approach.

2.1 Protocol and Regret

  • In each round, the environment reveals a nonempty compact action set, the learner publishes and samples a recommendation law, and the environment returns an action maximizing the fixed utility.The instantaneous regret is the utility gap between the best action and the recommendation.Source: §2.1 · pp. 4–5

2.2 Main Results

  • Expected regret is at most 221√d for every horizon, for a randomized learner that does not know the horizon.The guarantee holds for every d ≥ 1 and every environment.Source: §2.2 · p. 5

2.3 Technical Overview

  • The learner uses pairwise action comparisons to choose its recommendation distribution, then updates score matrices after observing the feedback action.The distribution is chosen by solving a linear program, and the updates use a fixed learning rate.Source: §2.3 · pp. 6–7
  • Polynomial-feature comparison matrices are combined across geometrically spaced scales to estimate utility differences between actions.Their quadratic forms have the sign of the utility difference, and the weighted sum approximates its magnitude up to a cutoff error.Source: §2.3 · p. 6
  • The scales activate over time so cutoff errors are summable without a known horizon; with rational oracle outputs and feedback, an oracle-relative implementation preserves the regret bound.Each round of that implementation terminates for every realization of the learner’s randomness.Source: §2.3 · p. 6, §2.2 · p. 6

3 Comparison Matrices on Polynomial Features

The section constructs polynomial-feature comparison matrices whose quadratic forms at the utility feature vector track action utility differences across scales. The construction is designed to control both the linear and squared terms used in the update, including for small positive differences.

3 Comparison Matrices on Polynomial Features

  • The weighted comparison forms are designed to make the update’s linear contribution dominate its quadratic correction, up to a scale-cutoff error, even for arbitrarily small positive utility differences.The features and degrees are chosen to meet these bounds.Source: §3 · p. 8

3.1 Features and Comparison Matrices

  • At scale k, the utility feature vector uses a degree-m_k Taylor polynomial of the exponential and is a unit vector in a feature space of dimension d_k.The feature space contains coordinates indexed by multiindices of degree at most m.Source: §3.1 · p. 8
  • The comparison matrix B_k(x, y) is built from a symmetric operator for the direction of y − x; it has operator norm at most one and reverses sign when x and y are exchanged.The directional operator is constructed through orthogonal transformations of the polynomial feature space.Source: §3.1 · p. 9

3.2 Quadratic Forms at Utility Feature Vectors

  • At the utility feature vector, the first and squared directional forms equal scaled functions of the utility projection ⟨u, v⟩, with a common factor bounded between 1/2 and 2.The first form has the sign of the projection, and both forms vanish when it is zero.Source: §3.2 · pp. 9–10

4 Multiscale Matrix-Weights Algorithm

The learner combines matrix weights across geometrically spaced accuracy scales and selects its recommendation distribution by a linear program. After observing the optimal feedback action, it updates the active score matrices using the published distribution.

4 Multiscale Matrix-Weights Algorithm

  • At round t, scales 0 through K_t are active, where K_t = ⌈2 log2(t + 1)⌉, and newly active scales receive zero score matrices.Each active scale has a symmetric score matrix whose normalized exponential is a density matrix.Source: §4 · p. 10
  • The learner forms a skew-symmetric comparison matrix from the current density matrices and chooses recommendation probabilities p satisfying C^T p ≤ 0.Such a distribution exists for every real skew-symmetric C.Source: §4 · p. 10
  • The learner publishes the distribution over the finite action list, samples a recommended action, observes the feedback action, and updates every active score matrix.The update averages over the published law rather than using only the sampled action.Source: §4 · p. 11
  • Under the balance condition, the update does not increase the weighted sum of log-trace-exponential scores, even when ties are broken after the sampled action is revealed.The stated potential is the sum over active scales weighted by 2^-k.Source: §4 · p. 11

5 Regret Analysis

The regret analysis first controls the comparison and matrix-update terms, then telescopes the resulting potential bounds for finite action sets. The finite-set analysis assumes a fixed utility and optimal feedback actions.

5.1 Comparison Inequalities

  • Across scales, weighted comparison inequalities control the update’s quadratic forms while allowing a cutoff error, so a fixed learning rate handles arbitrarily small positive utility differences.When the feedback action is optimal, the negative-part term in the bound vanishes.Source: §5.1 · pp. 11–12

5.2 One Matrix Update

  • A one-matrix-update bound controls the log-trace-exponential potential; convexity allows the bound to extend to updates averaged over matrices.The single-matrix argument uses a scalar exponential inequality and the Golden–Thompson inequality.Source: §5.2 · pp. 12–13

5.3 Regret Bound for Finite Action Sets

  • Zero initialization and nonnegativity of the potential support telescoping across rounds, while the weighted initial values across scales are finite.The initial potential at scale k is log d_k, weighted by 2^-k.Source: §5.3 · p. 13
  • The finite-action-set analysis gives expected regret at most 221√d for every horizon, and its bound holds for every sequence of optimal feedback actions, including ties broken after observing the recommendation.The inequality is converted to the expected-regret bound using (2.2).Source: §5.3 · p. 13

6 Compact Action Sets

For compact action sets, the learner works with a finite list of actions and approximates the optimal feedback action by a convex combination from that list. The section extends the regret guarantee and describes an oracle-based implementation.

6 Compact Action Sets

  • The learner approximates the feedback action with a convex combination of listed actions, chosen so the approximation error is at most δ_t.The list is formed using a compact-set approximation, and the convex-combination weights can be found by linear programming.Source: §6 · p. 14
  • The averaged update controls the weighted log-trace-exponential potential, with δ_t accounting for feedback approximation error and the associated quadratic-form term.The proof then applies the matrix-update bound and telescopes as in the finite-set analysis.Source: §6 · pp. 14–15
  • The compact-action-set learner achieves expected regret at most 221√d for every dimension d ≥ 1, every environment, and every horizon T ≥ 1.The randomized learner is independent of the horizon.Source: §6 · p. 15
  • With rational oracle outputs and feedback actions, a finite-precision implementation preserves the regret bound and terminates each round; for T ≥ 2, each round uses (dT)^O(d) oracle calls.The stated oracle-call count is for the implementation described in Appendix F.Source: §6 · p. 15

7 Conclusion and Discussion

The paper presents a multiscale matrix-weights algorithm with O(√d) expected regret. Its rational implementation terminates under the stated oracle assumptions, while polynomial-time computation and robustness to suboptimal feedback remain open directions.

7 Conclusion and Discussion

  • The multiscale matrix-weights algorithm achieves O(√d) expected regret for online inverse linear optimization.Its rational implementation terminates each round under the stated oracle assumptions.Source: §7 · p. 15
  • Whether the same regret order can be achieved in time polynomial in dimension, horizon, and input length remains open.Source: §7 · p. 15
  • Extending the dimension dependence to regret guarantees robust to suboptimal feedback remains a direction for future work.Source: §7 · p. 15

AI Usage

The main result was obtained through extended discussions with GPT-6 Astra in ChatGPT. GPT-6 Astra in ChatGPT, OpenAI Codex, and Claude Fable 5.1 were also used to improve the presentation.

AI Usage

  • Extended discussions with GPT-6 Astra in ChatGPT contributed to obtaining the main result.Source: AI Usage · p. 15
  • GPT-6 Astra in ChatGPT, OpenAI Codex, and Claude Fable 5.1 were used to improve the presentation.Source: AI Usage · p. 15
  • GPT-6 Astra in ChatGPT was used both in discussions about the result and to improve the presentation.Source: AI Usage · p. 15

A Proof of the Lower Bound

The proof constructs an environment that hides independent utility signs across the first d rounds, yielding a lower bound of order √d that persists for every T ≥ d.

A Proof of the Lower Bound

  • Every randomized learner faces an Ω(√d) expected-regret lower bound for every T ≥ d.Source: A Proof of the Lower Bound · p. 17
  • The construction uses independent uniform signs for the utility coordinates and two-action sets {−e_i, e_i} in the first d rounds.Source: A Proof of the Lower Bound · p. 17
  • Before each recommendation in those rounds, the corresponding sign is independent of the learner's available information, so expected utility is zero while the optimal value is d^-1/2.Source: A Proof of the Lower Bound · p. 17
  • Averaging over signs yields a fixed utility vector with the lower bound, and nonnegative instantaneous regret preserves it for later horizons.Source: A Proof of the Lower Bound · p. 17

B Proofs for Section 3

The appendix establishes structural properties of H_m(v) and relates its quadratic forms at utility feature vectors to two scalar functions, up to a bounded common factor.

B.1 Properties of Hm(v)

  • The construction pairs feature-space basis vectors across degrees, with H_m(e1) interchanging each pair and vanishing outside those pairs.Source: §B.1 · p. 18
  • H_m(v) is independent of the choice of orthogonal Q mapping e1 to v, symmetric, norm one, and negated when v is reversed.Source: §B.1 · p. 18

B.2 Quadratic Forms at Utility Feature Vectors

  • The scale parameters are α_k = 2^k and m_k = 2α_k^2 + 2 for integers k ≥ 0.Source: §B.2 · p. 19
  • For a unit vector v, the two quadratic forms of ϕ_k(u) with H_mk(v) and its square equal θ times b1(α_k r) and b2(α_k r), respectively.Here r = ⟨u, v⟩ and θ lies in [1/2, 2].Source: §B.2 · p. 19
  • The proof evaluates the forms in coordinates aligned with v and bounds their common factor using truncated exponential-series estimates.Source: §B.2 · p. 19

C Proof for Section 4

The proof establishes that the probability constraints in (4.3) are feasible whenever the comparison matrix is real and skew-symmetric. It uses the finite-game minimax theorem and compactness of the probability simplex.

C Proof for Section 4

  • Every real skew-symmetric matrix C admits a probability vector p satisfying C⊤p ≤ 0.This is Lemma 4.1, giving feasibility of condition (4.3).Source: C Proof for Section 4 · p. 20
  • The minimax theorem bounds the game value by zero because choosing p = q gives q⊤Cq = 0 for skew-symmetric C.The quadratic form vanishes for every q in the simplex.Source: C Proof for Section 4 · p. 20
  • A minimizing probability vector exists because the objective is continuous on the compact simplex, and its minimizing condition gives C⊤p ≤ 0 coordinatewise.The objective is the maximum coordinate of C⊤p.Source: C Proof for Section 4 · p. 20

D Proofs for Section 5

The proofs bound the multiscale scalar terms used in Section 5 and establish the comparison and initial-potential bounds. The algebraic appendix also gives a terminating rational approximation procedure for the comparison matrices.

D Proofs for Section 5

  • For r≥εK=2^(−K+1), the lower-bound argument chooses the smallest k∈{0,...,K} with 2^k r≥1/2; minimality and r≤1 then give rk∈[1/2,1].For r<εK, nonnegativity of b1 on [0,∞) suffices.Source: D Proofs for Section 5 · p. 20
  • The comparison proof handles both signs of the utility-direction inner product using the fixed learning rate η = 2−9.For nonnegative and negative inner products, the proof applies the scalar bounds separately to establish (5.2).Source: D Proofs for Section 5 · pp. 20–21
  • A binomial-theorem estimate and geometric ordering of the scales bound the sum used for the initial-potential estimate.The proof bounds the scale terms on either side of µ = 1 and sums the resulting geometric bounds.Source: D Proofs for Section 5 · pp. 21–22

E Algebraic Computation of the Comparison Matrices

  • For rational actions, the comparison matrices can be expressed using rational operations and square roots, then approximated by terminating rational interval arithmetic.The resulting symmetric rational matrix can be made arbitrarily accurate in operator norm.Source: E Algebraic Computation of the… · pp. 22–24

F Rational Implementation

The appendix constructs a rational-oracle implementation of the learner and controls its numerical errors. It proves a horizon-independent expected-regret guarantee, with every round terminating using finitely many fair random bits.

F.1 Oracle Model and Computational Guarantee

  • Theorem F.1 gives a horizon-independent randomized learner in the rational oracle model with expected regret at most 2^21√d for every T ≥ 1.Each round terminates for every realization of the learner’s randomness.Source: §F.1 · p. 24

F.2 Accuracy Requirements and Regret

  • Per-round feedback, balance, and update errors are controlled by tolerances, and Lemma F.2 carries those errors into the regret bound.The rational implementation uses δt = ξt = ζt = (t + 1)−2.Source: §F.2 · p. 25

F.3 Oracle Calls and Approximation of Feedback

  • A finite rational grid of oracle queries yields an action list whose convex hull approximates every feedback action within the prescribed distance.The grid construction uses (2Mt + 1)d oracle calls in round t.Source: §F.3 · p. 26

F.4 Matrix Exponentials and Entries of C

  • Taylor sums and rational approximations produce the density matrices and comparison entries used to compute the learner’s matrix C.The matrix-exponential approximation is evaluated in rational arithmetic, with the comparison matrices approximated in operator norm.Source: §F.4 · pp. 26–27

F.5 Published Law and Stored Update

  • A feasible linear program supplies the recommendation law, which is rounded for exact sampling and reused in the stored update.The rounded law is sampled using a fixed finite number of fair bits for that round.Source: §F.5 · pp. 27–28

F.6 Termination and Regret Bound

  • Every round terminates using finitely many fair bits, and the learner makes each round’s oracle calls during that round.The construction uses finite grids, terminating matrix approximations, and terminating rational linear programs.Source: §F.6 · p. 28
  • The rational procedure uses neither the utility nor the horizon, while its stored score matrices remain rational and symmetric.The construction starts with zero score matrices and preserves its error bound inductively.Source: §F.6 · p. 28
Loading 2609.26978v1…