Feasible Action Search for Bandit Linear Programs via Thompson Sampling

Our thanks for your work.

Comparison to Gangrade et al 2024b. Thanks for pointing out these omissions, which we will fix.

• Theoretical: Gangrade et al 2024b only study testing. We can extend it to FAS via something like our Lemma 7. In this case, the bound is a) $O(d^2/\varepsilon^2 M_*^2)$ for their Algorithm 1, and b) $O(d^3/\varepsilon^2 M_*^2)$ for the $(2d)^m$-game relaxation proposed on their page 9.
  • These are similar to Thm 9, up to a factor of $d$ for us relative to a). This shows up in all known efficient methods (line 347, col 2).
  • While they don't talk about safety costs, similar bounds to ours should also hold for them.
• Experimental: As discussed starting line 150 col 1, the method of Gangrade et al. is inefficient. In particular, they propose choosing actions by solving $(2d)^m$ matrix games in each round (page 9 of their paper). The simulations in Appendix A work with $d = m = 9,$ and our method takes milliseconds for each round on a laptop. However, their proposal would need to solve $(18)^9>10^{11}$ games per round, which would literally take years!
  • We will include a comparison for small $d,m$.
  • However, making their method practical for nontrivial $d,m$ is an open problem beyond the scope of our submission. This would require studying how to appropriately relax and solve the optimisation problem described in (our) line 160 col 1.
    • In particular, we want to point out that even simple ideas like nets don't work, since one would need a net of resolution $t^{-1/2},$ meaning $\Omega(t^{d/2})$ games per round, which is prohibitive even for $t\approx 100, d = 10.$

Claims & Evidence: We disagree that terms are not defined, but are happy to clarify.

• $\omega_t$. This is defined on line 184 col 2 and used throughout the paper. It is the standard radius of the confidence ellipsoid.
• Noise distribution: The underlying noise distribution is stated as $\mathrm{Unif}(\sqrt{3d} \cdot \mathbb{S}^d)$ in Theorem 9. This is indeed "inflated" in the sense of the common terminology for linTS (although our paper is not about linTS).
• $m$: Recall that $\Phi_* \in \mathbb{R}^{m \times d}$ (line 30 col 2, line 162 col 2). So $m$ is the number of rows of $\Phi_*$, or equivalently, the number of unknown constraints. Line 334, col 1 (just before Theorem 8) actually explicitly says this.
• Theorem 8: We disagree. This theorem first describes a condition on a measure $\nu$. Then it defines a measure $\mu$ as the law of $\mathbf{1}_m \zeta^\top$ when $\zeta \sim \nu$ (equivalently, a pushforward of $\nu$ under the map $\zeta \mapsto \mathbf{1}_m \zeta^\top$), and says that $\mu$ follows a $(B,\pi)$-CO condition with instantiations of $B,\pi$ in terms of the condition on $\nu$. The CO-condition itself is described in Def. 4, and forms one of the central technical concepts of the paper.

Theoretical Claims:

• "Under $\mathsf{Ball}_t$": as stated on line 154 col 1, "An inequality $a \le b$ is said to hold under an event $E$ if $a {1}_E \le b {1}_E$, where ${1}_E$ indicates $E$.'' The statement of the lemma defines the event $\mathsf{Ball}_t$, and the inequality of line 267 col 2 holds once multiplied by an appropriate indicator. This "under an event" terminology is used to lighten the visual load of expressions in the cramped two-column format.

  • Line 858: by definition, $\bar{\Phi}_t$ minimises $K(\Phi)$ over $\mathcal{E}_t$. Under $\mathsf{Ball}_t,$ $\tilde\Phi_t \in \mathcal{E}_t,$ so this inequality is trivial.

• Theorem 8 proof, line 1019 - 1025: There is a typo in line 995: as stated in the statement of Theorem 8, $H = \mathbf{1}_m \zeta^\top,$ so there is an extra $-$ sign in this line. If this is corrected, things should make sense.

  • The display in 1019-1021 is opens up $H_t$. Then, by the discussion previous to 1019, if $\zeta^\top u\_t \ge \\|u\_t\\|,$ we find that $\tilde{\Phi}\_t a\_{\*} \ge M\_{\*} \mathbf{1}\_m,$ which implies local optimism (the event $\mathsf{L}\_t$). But the condition on $\nu$, and the independence of $\zeta$ from the history directly means that this even has chance at least $p$ given the history (which fixes $u_t$). Finally, the norm of the rows of $H$ is just the norm of $\zeta$, which is also controlled by the condition on $\nu$.

• Typo in Lemma 11: thanks. It should read $\\| (\Phi - \Psi) a\\|_\infty$.

• We will make sure to proofread the paper closely, and ensure that symbols are reiterated in their context to smooth over the issues you describe.

Relation to broader literature:

• Line 55: This is the work of Gangrade et al. 2024b (discussed line 150 col 1).
• Theoretical bounds of Gangrade et al. 2024b: see above.

Rationale of the experiments: In a nutshell, appendix A attempts to build and study a practical methodology out of the theoretical study in the main text. The plan is discussed in detail on page 11. We will both discuss the early stopping trick in the main text, and include plots without it.

Our thanks for your work.

Questions:

• Corollary 10: This is indeed an important point, thanks for your careful reading. The issue is resolved by Remark 11 (page 8) and Appendix F.1 (page 47) of the paper of Pacchiano et al. (https://arxiv.org/pdf/2401.08016).

  • In short, remark 11 summarises how it is enough for them to have a lower bound on the safety margin of the safe action that is a constant factor away. In our case, the margin of the output $\langle a\rangle_\tau$ is bounded between $L_\tau$ and $U_\tau$, and by the stopping condition, with $\varepsilon = 1/2,$ we have $L_\tau > U_\tau/2 > M(\langle a\rangle_\tau)/2$, so we get exactly such an approximation. There is however, a small modification needed (as discussed by Pacchiano et al.) in that the orthogonal projection stuff in LC-LUCB cannot be carried out with only a lower-bound. This does not affect the regret bounds.
  • We will expand upon the discussion of section B.4 to discuss this aspect.
  • We also wanted to point out that in fact most such methods for SLBs only really need a lower bound on the margin of the safe action (and the regret then scales with this bound). Intuitively, the point is just that this bound yields an initial exploratory set, and determines the rate of expansion of the safe set estimate. LC-LUCB is a bit of a special case because of the orthogonal projection step they take.

• $M_* = 0$: We will be happy to discuss this. Short answer is that in this case no method can operate in finite time.

  • As an example, consider the case $m = 1, d = 1$, and $\mathcal{A} = \{ 1\},$ with standard Gaussian feedback noise. Then the questions becomes one of testing if $\phi_* = 0$ or $< 0$ using samples from $\mathcal{N}(\phi_*,1)$. But with any finite number of samples $n$, we cannot reliably distinguish between $\phi_* = 0$ and $\phi_* \in (-O(1/\sqrt{n}),0)$, and so we can never reliably conclude the procedure in finite time. This simple scenario embeds into more rich situations, and so if the optimal margin is exactly $0$, we can never be $\delta$-sure of this fact, and so never stop in finite time. This is also reflected in the $\Omega(d^2/M\_{\*}^2)$ lower bound (line 340 col 2), which diverges to $\infty$ as $M\_{\*} \to 0$.

• Rows instead of $\lambda$: Yes, we can write things in this way with no change. The reason why $\lambda$ was introduced was to give ourselves the option of using the minimax theorem when working the results out. This (surprisingly) ended up not being needed, but by the time we figured this out, much of the paper was already written in this language, and it was too late to rewrite all of it.

Relation to broader literature: while we mostly agree with your reading, we would like to point out that while yes, an extension of Gangrade et al. 2024b along the lines of our submission would do this job, this method is completely impractical.

• Their proposed relaxation (page 9 of their ICML paper) requires solving $(2d)^m$ matrix games in each round. With $d = m = 9$ (the setting studied in our Appendix A), this requires $>10^{11}$ games in each round, and so each round would take years on a laptop, while our method runs in milliseconds.

Our thanks for your work.

• Max-safety-margin v/s only feasible. Thanks for bringing up this important point. The short answer is that our setup already accomodates the viewpoint you express through our use of the multiplicative approximation.

  • Indeed, any feasible point would have a safety margin of at least $0$, and so would satisfy our notion of approximation with $\varepsilon = 1$ (since $0 \ge (1-1)M_*)$. So, if we just run FAST with $\varepsilon = 1,$ we will stop with a feasible action in $\tilde{O}(d^3/M_*^2)$ time, gaining a factor of $\varepsilon^2$.
    • We note that the stopping time bound above is just as tight as the general bound in Theorem 9. By the same reasoning as in line 340 col 2, if $m = 1,$ then finding a feasible point is equivalent to finding an $M_*$-approximate optimum in a low-regret problem, and so needs $\Omega(d^2/M_*^2)$ samples. We lose a factor of $d$, which appears in all known efficient methods (line 346 col 2).
  • Finding a point with near-maximum margin of course has practical applications, mainly in terms of building resiliency. For instance, a manufacturer balancing various quality and cost constraints would want the solution to be remain feasible under small perturbations of the process (translating to perturbations of $\Phi\_*$ in our setting). This would be true for a point with positive safety margin, but not so if the margin is close to zero. $\varepsilon$ captures a tradeoff between the costs of identifying such a point, and its resilience.
    • The application of optimising a different objective later is captured well by the low-regret SLB problem discussed in section 4. Here, in fact, positive margin is a necessity, since this margin determines the rate at which information can be accrued in the early rounds (also see the lower bound due to Pacchiano et al. 2021). This is reflected in the regret bounds scaling with $M(a\_{\mathsf{safe}})^{-1}.$ Our proposed solution improves upon this general bound: we pay an extra constant factor in the exploration costs to end up with a point with close to optimal margin, which in turn improves the regret by a potentially large factor of $M_*/M(a\_{\mathrm{safe}})$ (Line 80, Col 1). If instead we had stopped with near-zero margin, the regret would suffer.
      • Of course, here exact optimal margin is not necessary, which is why Corollary 10 sets $\varepsilon = 1/2$ for this application.
  • We do want to say that your point is well-taken, and these aspect should indeed have be clarified and discussed in more detail in the paper. If accepted, we will include something like the above to clarify these issues in the paper.

• UCB version: yes, this works, but is computationally infeasible.

  • This method was proposed as a test by Gangrade et al 2024b (and can be extended to FAS via a tracking result similar to our Lemma 7).
  • However, as discussed in the paragraph starting line 150, col 1, for continuous $\mathcal{A}$, this technique needs to solve $(2d)^{m}$ games in each round. This makes it completely impractical even in the setting we simulated in section A (since for $d = m = 9, (2d)^m > 10^{11})$. For instance, our method runs in milliseconds per round, but this method would take years. Finding an efficient UCB-version of such algorithms is an open problem.

• Does local optimism lead to over exploration? This may indeed be true, which is why the main CO condition (Def. 4) is formulated in terms of global optimism.

  • However, we note that our bounds on the optimism rate match those of prior work on single-objective TS, even though they are studying global optimism.
  • To be explicit: under the same conditions on the noise in which prior work shows $\pi$-global optimism, our coupled construction gives $\pi$-local optimism. This suggests that new techniques are needed to control global optimism rates well not only for FAST, but for linTS in general. This is beyond the scope of our submission.

• Relation to online linear programming: while interesting, this appears to be a quite different problem. In the setup in the reference, the constraints are revealed one-by-one (and completely), while in our case, constraints are never directly revealed, but we can noisily measure (all of) their values at various $a_t$. Of course, the other important difference is that they are aiming to optimise, while we are aiming at maximin points. Nevertheless, we will read this thoroughly to see if it is appropriate to discuss.

Our thanks for your work. Thanks also for the interesting reference. The section 8 of this paper certainly describes a related idea, although there is no real adaptation to the value of the Slater parameter ($\equiv$ margin), which is an important aspect of our study. We will both try to carefully work out the concrete implications (by working out the primal/dual regrets appropriate here), and of course discuss this paper in the related work section.