Proof.: Algorithm 3 maintains the invariant that \(\mathsf{logit}_{i}-\mathsf{logit}_{0}\in[\alpha_{i},\beta_{i}]\) in each round. We will prove by induction that this is true and that the true vector of logits always lies in \(\mathcal{C}\). Note that by the assumption stated in the Lemma, this is clearly true at the beginning of the first round. Suppose that this is true after \(K<T\) rounds. Then, in the \(K+1\)-th round, the constraints added are all valid constraints for the true logit vector, since the API returning token \(k\) guarantees that \(\mathsf{logit}_{k}+b_{k}\geq\mathsf{logit}_{j}+b_{j}\) for all \(j\neq k\). Hence, by induction, the algorithm always ensures that \(\mathsf{logit}_{i}-\mathsf{logit}_{0}\in[\alpha_{i},\beta_{i}]\).