Feature-Based Online Bilateral Trade

## Abstract

Abstract Bilateral trade models the problem of facilitating trades between a seller and a buyer having private valuations for the item being sold.
In the online version of the problem, the learner faces a new seller and buyer at each time step, and has to post a price for each of the two parties without any knowledge of their valuations.
We consider a scenario where, at each time step, before posting prices the learner observes a context vector containing information about the features of the item for sale. The valuations of both the seller and the buyer follow an unknown linear function of the context. In this setting, the learner could leverage previous transactions in an attempt to estimate private valuations.
We characterize the regret regimes of different settings, taking as a baseline the best context-dependent prices in hindsight. First, in the setting in which the learner has two-bit feedback and strong budget balance constraints, we propose an algorithm with O ​ ( log ⁡ T ) 𝑂 𝑇 O(\log T) regret. Then, we study the same set-up with noisy valuations, providing a tight \symlargesymbols Γ ​ 065 ​ O ​ ( T 2 / 3 ) Γ \symlargesymbols 065 𝑂 superscript 𝑇 2 3 \mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{2}}{{3}}}) regret upper bound.
Finally, we show that loosening budget balance constraints allows the learner to operate under more restrictive feedback. Specifically, we show how to address the one-bit, global budget balance setting through a reduction from the two-bit, strong budget balance setup.
This established a fundamental trade-off between the quality of the feedback and the strictness of the budget constraints.

## 1 Introduction

Bilateral trade models scenarios in which a seller and a buyer, both having a private valuation for a good, are interested in trading it in an attempt to maximize their respective utilities [, ].
We study the online bilateral trade problem introduced by Cesa-Bianchi et al. []. At each time $t$, a new seller and buyer arrive, each with private valuations $s_{t}$ and $b_{t}$, respectively. The seller’s valuation $s_{t}$ is the lowest price they are willing to accept for the item. Analogously, the buyer’s valuation $b_{t}$ represents the highest price they are willing to pay for the item.
The learner, without any knowledge about the private valuations at the current time $t$, posts two (possibly randomized) prices: $p_{t}$ to the seller and $q_{t}$ to the buyer. A trade happens when $s_{t}\leq p_{t}$ and $q_{t}\leq b_{t}$, so both agents agree to trade.
The gain from trade for a pair of prices $(p,q)$ at time $t$ is

$$ $\textnormal{GFT}_{t}(p,q)\coloneqq\mathbb{I}{\left\{s_{t}\leq p\right\}}\mathbb{I}{\left\{q\leq b_{t}\right\}}(b_{t}-s_{t}).$ (1) $$

This corresponds to the increase in social welfare generated by the trade. The goal of the learner is to maximize the overall gain from trade or, equivalently, minimize the regret with respect to the best policy in hindsight.
A key challenge in the online bilateral trade problem is the inherently limited nature of the feedback: under two-bit feedback, the learner receives feedback $(\mathbb{I}{\left\{s_{t}\leq p_{t}\right\}},\mathbb{I}{\left\{b_{t}\geq q_{t}\right\}})$, and under one-bit feedback the learner only observes whether the trade happened or not, that is $\mathbb{I}{\left\{s_{t}\leq p_{t}\right\}}\cdot\mathbb{I}{\left\{b_{t}\geq q_{t}\right\}}$. Both types of feedback are significantly less informative than the traditional bandit feedback, since the learner cannot even reconstruct the GFT received for the prices it posted.

In the standard model of bilateral trade, the platform lacks information about the seller, buyer, or the item being sold. However, this scenario is unrealistic in practice, where some information is usually available to the learner. In contexts like online marketplaces, products are often highly differentiated, and the learner can observe some product features upfront. Then, the learner could base pricing decisions on the features of the current product. This would enable the learner to utilize past price and trade data to estimate the values associated with each feature, informing future pricing decisions.

We introduce the feature-based online bilateral trade problem, in which the learner observes a feature vector $x_{t}\in\mathbb{R}^{d}$ before posting prices for round $t$. Following the classic feature-based dynamic pricing set-up (see, e.g., [, , , , ]), we study the setting in which private valuations are of the form $x_{t}^{\top}\theta+\xi_{t}$, where $\theta\in\mathbb{R}^{d}$ is an unknown vector denoting the importance of each feature, and $\xi_{t}$ is an i.i.d. noise term. Feature vectors $x_{t}$ are chosen adversarially. This ensures that our solution is robust to scenarios where features are correlated and where the set of relevant features evolves over time.

### 1.1 Our contributions

In this paper, we introduce the feature-based online bilateral trade model, and characterize the regret for various scenarios with adversarially generated feature vectors. We provide the following results for the case in which the learner has two-bit feedback and strong budget balance constraints (the learner has to set the same price to the seller and to the buyer, i.e., $p_{t}=q_{t}$ at each round $t$):

- $\bullet$
First, we consider the deterministic setup where, at each $t$, the seller’s valuation is $s_{t}=x_{t}^{\top}\theta^{s}$ and the buyer’s valuation is $b_{t}=x_{t}^{\top}\theta^{b}$. We show that in this case, it is possible to adapt techniques proposed by Cohen et al. [] in the context of feature-based dynamic pricing. The main difference here is that we need to maintain separate ellipsoidal uncertainty sets for the seller and the buyer, respectively. Our analysis yields a regret of order $O(\log T)$ ([Theorem 1](#Thmtheorem1)).
- $\bullet$
Second, we consider the case of noisy valuations in which $s_{t}=x_{t}^{\top}\theta^{s}+\xi_{t}^{s}$ and $b_{t}=x_{t}^{\top}\theta^{b}+\xi_{t}^{b}$, where $\xi_{t}^{s}$ and $\xi_{t}^{b}$ are i.i.d. noise terms independent from $x_{t}$, with bounded support and densities.
We start by decomposing the expected gain-from-trade into components that can be individually estimated using two-bit feedback ([Lemma 1](#Thmlemma1)). Then, we describe an explore-*or*-commit (EOC) algorithm with regret $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{3}}{{4}}})$ ([Theorem 2](#Thmtheorem2)) (this algorithm will be employed in the subsequent reduction to the one-bit setting).
Finally, we devise a Scouting Bandits with Information Pooling algorithm, which makes a more efficient use of the information collected during the learning phase. This algorithms achieves a regret $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{2}}{{3}}})$([Theorem 3](#Thmtheorem3)),
which is minimax optimal up to poly-logarithmic factors and dependence on $d$. Indeed, there exists a matching $\Omega(T^{\nicefrac{{2}}{{3}}})$ lower bound for the stochastic bilateral trade problem without features in the case of independent valuations with bounded densities and support [].

Finally, we provide a general reduction that demonstrates how the difficulty of maintaining a per-round budget balance can be traded for the ability to operate under more demanding feedback conditions.
In particular, given a two-bit explore-or-commit algorithm guaranteeing strong budget balance and sublinear regret, we show that it is possible to construct a no-regret algorithm that works under one-bit feedback, and is global budget balanced ([Theorem 4](#Thmtheorem4)). The one-bit regret guarantees are dependent on a natural measure of the social welfare generated by the market.

### 1.2 Related works

Bilateral trade. In the offline setting, Myerson and Satterthwaite [] showed the existence of instances where a fully efficient mechanism that satisfies incentive compatibility, individual rationality, and budget balance does not exist. Subsequent research focused on finding approximately efficient mechanisms in the Bayesian setting [, , , , , , ].

Online bilateral trade. Cesa-Bianchi et al. [, ] study the case in which valuations are drawn i.i.d. from some fixed unknown distribution and the learner has to enforce strong budget balance. They provide sublinear regret guarantees in the full-feedback setting, and under partial feedback when valuations are i.i.d. samples from a smooth distribution, independently for the seller and the buyer.
If the learner is only required to enforce weak budget balance (i.e., $p_{t}\leq q_{t}$ for each $t$), then Azar et al. [] provide an algorithm achieving a tight sublinear $2$-regret when the sequence of valuation is generated by an oblivious adversary.
Cesa-Bianchi et al. [] show that sublinear regret can be achieved beyond the i.i.d. stochastic setting under a $\sigma$-smooth adversary model. Bernasconi et al. [] show that sublinear regret can be achieved in the fully adversarial setting if the learner enforces global budget balance constraints (i.e., the constraint has to hold over the entire time horizon).

Feature-based pricing. The one-dimensional version of the problem was introduced by Kleinberg and Leighton [], while Amin et al. [] introduced the problem in the contextual, multi-dimensional set-up under i.i.d. contexts. Cohen et al. [] study a model with adversarial contexts for which they provide $\mathaccent 0{\symlargesymbols}065{O}(d^{2}\log T)$ regret guarantees in the noiseless setting, improving over the $\mathaccent 0{\symlargesymbols}065{O}(\sqrt{T})$ guarantees obtainable with general-purpose contextual bandits algorithms []. Moreover, they provide $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{2}}{{3}}})$ regret guarantees for scenarios with adversarial contexts and additive noise generated from a known sub-Gaussian distribution.
Further improvements in the achievable rates were later provided by Lobel et al. [], Leme and Schneider [], Liu et al. []. Further instantiations of the feature-based pricing model can be found in the survey of Den Boer [].

## 2 Preliminaries

Notations.
For any $k\geq 1$, we compactly denote the set $\{1,2,\ldots,k\}$ as $\llbracket k\rrbracket$.
We denote by $\text{LJ}(H)$ the Löwner-John ellipsoid of a convex body $H$ (i.e., the minimal volume ellipsoid that contains $H$). For a positive definite matrix $\mathbf{M}\in\mathbb{R}^{d\times d}$ and $x\in\mathbb{R}^{d}$, we denote $\sqrt{x^{\top}\mathbf{M}x}$ by $\|x\|_{\mathbf{M}}$.
In our proof sketches, we write $A_{T}\lesssim B_{T}$ if there exists a problem-dependent constant $c$ such that $A_{T}\leq cB_{T}$.

Learning protocol.
At each round $t$, a new buyer and a seller arrive, characterized by private valuations $b_{t}$ and $s_{t}$, respectively. After observing a feature vector $x_{t}\in\mathbb{R}^{d}$, the learner posts two prices: $p_{t}$ to the seller and $q_{t}$ to the buyer. The trade happens if both agents accept the proposed prices, that is $s_{t}\leq p_{t}$ and $q_{t}\leq b_{t}$. When the trade happens the learner is awarded the gain from trade $\textnormal{GFT}_{t}(p_{t},q_{t})$, defined as per [Equation 1](#S1.E1). Feature vectors $x_{t}$ are generated by an oblivious adversary.

Valuations. We consider two models to describe how features impact on the seller’s and buyer’s valuations. In the first setting, valuations are a deterministic function of the context. In particular, at each round $t\in\llbracket T\rrbracket$, the valuations of the seller and of the buyer are given by

$$ $s_{t}=x_{t}^{\top}\theta^{s}\quad\textnormal{ and }\quad b_{t}=x_{t}^{\top}\theta^{b},$ (2) $$

respectively, where $\theta^{s},\theta^{b}\in\mathbb{R}^{d}$ are unknown to the learner. We assume that both the contexts $x_{t}$ and the parameters $\theta^{b}$ and $\theta^{s}$ are bounded.

###### Assumption 1 .

There exist $A,B\geq 0$ such that $\max(\Vert\theta^{s}\Vert,\Vert\theta^{b}\Vert)\leq A$, and $\Vert x_{t}\Vert\leq B$.

In the second setting, we consider noisy valuations. In particular, we assume that at each round $t$ the valuations are given by

$$ $b_{t}=x_{t}^{\top}\theta^{b}+\xi_{t}^{b}\quad\text{ and }\quad s_{t}=x_{t}^{\top}\theta^{s}+\xi_{t}^{s},$ (3) $$

where $\xi_{t}^{b}$ and $\xi_{t}^{s}$ are i.i.d. centered noise terms independent from the context $x_{t}$, with densities $f^{b}$ and $f^{s}$, respectively. We denote by $F^{s}$ the c.d.f. of $\xi_{t}^{s}$, and by $D^{b}$ the demand function of $\xi_{t}^{b}$: for all $x\in\mathbb{R}$, $D^{b}(x)\coloneqq\mathbb{P}\left(\xi_{t}^{b}\geq x\right)$. We make the following assumption on the densities of $\xi^{s}_{t}$ and $\xi^{b}_{t}$.

###### Assumption 2 .

Both $\xi_{t}^{s}$ and $\xi_{t}^{b}$ have bounded support in $[-C,C]$, and have densities bounded by $L$.

We observe that under Assumption [1](#Thmassumption1) and [2](#Thmassumption2), the valuations of the seller and the buyer are bounded in $[-P,P]$, where $P\coloneqq C+AB$.(^1^11 For simplicity, we work within $[-P,P]$. If non-negative prices are required, a translation is sufficient.) The bounded densities assumption is standard in repeated bilateral trade problems with stochastic valuations, and there exists linear regret lower bounds for the case in which this assumption is lifted (see Cesa-Bianchi et al. [, Theorem 6]).

Feedback models. After posting prices $(p_{t},q_{t})$, the learner does not observe directly the GFT or the valuations, but receives some feedback $z_{t}$ about the transaction. We focus on two feedback models: (i) Two-bit feedback, where both the buyer and the seller reveal their willingness to accept the prices offered by the learner (i.e., $z_{t}$ is composed by the two bits $(\mathbb{I}{\left\{s_{t}\leq p_{t}\right\}},\mathbb{I}{\left\{q_{t}\leq b_{t}\right\}})$); (ii) One-bit feedback: the learner only observes whether the trade happened or not (i.e., $z_{t}=\mathbb{I}{\left\{s_{t}\leq p_{t}\right\}}\cdot\mathbb{I}{\left\{q_{t}\leq b_{t}\right\}}$). Both feedback models have the desirable property of revealing minimal information about agent’s private valuations.

Regret. Our objective is to develop dynamic policies that perform well in terms of minimizing regret. In the deterministic setting, the worst-case regret for learning algorithm $\mathcal{A}$ is defined as

$$ $R_{T}(\mathcal{A})\coloneqq\max_{\begin{subarray}{c}(\theta^{s},\theta^{b})\in[-A,A],\bm{x}\in[-C,C]^{T}\end{subarray}}\sumop\slimits@_{t\in\llbracket T\rrbracket}\left(\left[x_{t}^{\top}(\theta^{b}-\theta^{s})\right]^{+}-\textnormal{GFT}_{t}(p_{t},q_{t})\right).$ $$

In the noisy model, we compare against a benchmark that maximizes the expected gain from trade. Let $\textnormal{EGFT}(x,p,q)\coloneqq\mathbb{E}\left[\textnormal{GFT}_{t}(p,q)\,|\,x_{t}=x\right]$. The pseudo-regret for the noisy setting is defined as

$$ $R_{T}(\mathcal{A})\coloneqq\sumop\slimits@_{t\in\llbracket T\rrbracket}\max_{\begin{subarray}{c}(p,q)\in[-P,P]^{2}\\ p\leq q\end{subarray}}\textnormal{EGFT}(x_{t},p,q)-\sumop\slimits@_{t\in\llbracket T\rrbracket}\textnormal{EGFT}(x_{t},p_{t},q_{t}).$ $$

A property that directly follows by definition is that, for any feature vector, there exists a pair of identical prices that maximize the expected gain from trade. To simplify the notation, we omit the argument $q$ of $\textnormal{GFT}_{t}$ and EGFT if the same price is posted to both agents.

###### Assumption 1 .

###### Assumption 2 .

## 3 Warm-up: two-bit feedback, strong budget balance, no noise

In this section, we consider the simplest set-up in terms of the information available to the learner, by focusing on the setting with two-bit feedback and deterministic valuations following [Equation 2](#S2.E2). We show that it is possible to adapt the EllipsoidPricing algorithm, originally proposed by Cohen et al. [] for feature-based dynamic pricing, to our bilateral trade problem. The key distinction lies in managing separate uncertainty sets for the seller and the buyer, while carefully setting prices consistent with both estimations. In this set-up, we can update these uncertainty sets separately.

[Algorithm 1](#alg1) describes the main step of EllipsoidPricing for Bilateral Trade (EP-BT).
The algorithm maintains two ellipsoidal uncertainty sets $E^{s}_{t}$ and $E^{b}_{t}$ (see [Appendix A](#A1) for some basic facts about ellipsoids). The key idea is that, at each update, the volume of an uncertainty shrinks “fast enough” to yield a good estimate of the true parameter in a small number of iterations.
The problems of computing the maximum and minimum possible valuations of the seller and buyer (Line [4](#alg1.l4)) admit a simple closed-form solution (see, e.g., , Grötschel et al. [, Chapter 3]).
If the smallest possible valuation for the buyer $\underline{b_{t}}$ is above the highest possible valuation for the seller $\overline{s_{t}}$ (Line [5](#alg1.l5)), the algorithm can post any price between these two values, ensuring that the trade will occur.
If $\overline{s_{t}}$ and $\underline{s_{t}}$ are far apart (Line [6](#alg1.l6)), the algorithm performs a binary search step (a.k.a. “explore” step), and posts a price $p_{t}$ which is halfway between the seller’s minimum and the maximum possible valuations.
Then, we update the seller’s uncertainty set as follows: if the seller accepts the sale, it implies that $x_{t}^{\top}\theta^{s}\leq p_{t}$, and we define the half-ellipsoid $K_{t+1}^{s}=E^{s}_{t}\cap\{\theta:x_{t}^{\top}\theta^{s}\leq p_{t}\}$. Otherwise, we set $K_{t+1}^{s}=E^{s}_{t}\cap\{\theta:x_{t}^{\top}\theta^{s}>p_{t}\}$. Finally, we round this half-ellipsoid by replacing it by its Löwner-John ellipsoid, i.e., the ellipsoid containing $K_{t+1}^{s}$ with the smallest volume. We proceed similarly for the buyer (Line [9](#alg1.l9)).
If the highest and lowest possible valuations of both the buyer and seller are close to each other, and the buyer’s minimum valuation is lower than the seller’s maximum valuation, then the difference of valuations between the two parties is small, resulting in a negligible gain from trade. Therefore, in this case, we can safely post an arbitrary price (Line [12](#alg1.l12)).

Figure: Algorithm 1 EllipsoidPricing for Bilateral Trade (EP-BT)

###### Theorem 1 .

Assume that the seller’s and buyer’s valuations follow [Equation 2](#S2.E2). Under [1](#Thmassumption1), [Algorithm 1](#alg1) with $\epsilon=ABd^{2}/T$ has regret bounded by
$R_{T}\leq 10ABd^{2}\log\left(20(d+1)Td^{-2}\right).$

We observe that the algorithm explores only whenever the estimations are not precise enough. In the proof ([Appendix B](#A2)), we show that this happens in at most $O(\log T)$ rounds.

###### Theorem 1 .

## 4 Noisy valuations with two-bit feedback

In this section, we consider bilateral trade with two-bit feedback and noisy valuations. We introduce key components that we exploit in the analysis, before integrating them into an explore-*or*-commit framework which that ensures a regret $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{3}}{{4}}})$. Finally, we show a careful re-design of the last phase of the algorithm yields a tight regret upper bound of $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{2}}{{3}}})$.

We rely on the following decomposition lemma, which extends Lemma 1 of Cesa-Bianchi et al. [] to contextual settings. The proof can be found in [Section E.1](#A5.SS1).

###### Lemma 1 .

Under Assumptions [1](#Thmassumption1) and [2](#Thmassumption2), the expected gain from trade for $x$ at price $p$ is given by

$$ $\displaystyle\textnormal{EGFT}(x,p)=I(\delta^{b})F^{s}(\delta^{s})+J(\delta^{s})D^{b}(\delta^{b}),$ (4) $$

where $\delta^{s}\coloneqq p-x_{t}^{\top}\theta^{s}$, $\delta^{b}\coloneqq p-x_{t}^{\top}\theta^{b}$, $I(\delta)\coloneqq\intslop\ilimits@_{\delta}^{C}D^{b}(u)du$, and $J(\delta)\coloneqq\intslop\ilimits@_{-C}^{\delta}F^{s}(u)du$.

[Lemma 1](#Thmlemma1) highlights the principal difficulties of our setting.
It emphasizes that the expected gain from trade for a price $p$ depends on the pair of price increments $(\delta^{s},\delta^{b})$, or equivalently, on the pair $(\delta^{s},{}_{t})$, where the difference in average valuations t is defined as ${}_{t}\coloneqq x_{t}^{\top}(\theta^{b}-\theta^{s})$.
This shows that items with the same t have the same optimal seller’s price increment $\delta^{\ast}_{t}$: if $p=x^{\top}_{t}\theta^{s}+\delta^{*}_{t}$ maximizes $\textnormal{EGFT}(x_{t},\cdot)$, and if $x_{t^{\prime}}^{\top}(\theta^{b}-\theta^{s})=x_{t}^{\top}(\theta^{b}-\theta^{s})$, then $p^{\prime}=x_{t^{\prime}}^{\top}\theta^{s}+\delta^{*}_{t}$ maximizes $\textnormal{EGFT}(x_{t^{\prime}},\cdot)$.
However, knowing the optimal increment $\delta^{\ast}_{t}$ for a specific t is not sufficient to determine the optimal increment for a different t (see [Appendix F](#A6)). Thus, finding the optimal price increment across various t values might require us to precise estimate the reward function over a broad range of increments.
This is a notable departure from the non-contextual stochastic bilateral trade problem discussed in Cesa-Bianchi et al. [], where precise estimation of the reward function around the optimal price suffices.
Since accurately estimating functions such as $F^{s}$, $D^{b}$, $I$, and $J$ across a wide range of arguments complicates the problem, the regret might be higher than the $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{2}}{{3}}})$ rate achieved in Cesa-Bianchi et al. []. Surprisingly, we show that with careful coordination of the various estimation procedures, the optimal rate for the non-contextual case can still be attained.

###### Lemma 1 .

### 4.1 Building blocks: subroutines for learning parameters

We begin by presenting the sub-routines to estimate the parameters $\theta^{s}$ and $\theta^{b}$, as well as the functions $F^{s}$, $D^{b}$, $I$ and $J$ used in the EGFT decomposition of [Lemma 1](#Thmlemma1). These sub-routines serve as the base components for the subsequent algorithms.

Figure: Algorithm 2 Estimation Subroutines

The first sub-routine, Est-Par, estimates the parameters $\theta^{s}$ and $\theta^{b}$. It relies on the fact that, if $p_{t}\sim\mathcal{U}([-P,P])$, then $2P\left(\mathbb{I}\{p_{t}\geq s_{t}\}-1/2\right)$ is an unbiased estimate of $x_{t}^{\top}\theta^{s}$ (the case of $\theta^{b}$ is analogous). Then, we can rely on classical results to estimate the parameters (see Lattimore and Szepesvári [, Chapter 19]). The second sub-routine, Est-Int, estimates the integrals $I(\delta)$ and $J(\delta)$ over a grid of price increments $\{k\epsilon:k\in\mathcal{K}\}$. The third and fourth sub-routines, Est-F and Est-D, provide estimates of the c.d.f. $F^{s}$ and the demand function $D^{b}$ at $k\epsilon$ for a given increment level $k\in\mathcal{K}$, respectively.

### 4.2 Explore-Or-Commit framework

First, we consider a natural Explore-*Or*-Commit (EOC) algorithm which uses each round *either* to compute estimates for the terms in [Equation 4](#S4.E4), *or* to greedily play the empirical best action. This strategy is described in [Algorithm 3](#alg3).
Our algorithm is not a standard Explore-Then-Commit algorithm. Indeed, it resorts to the estimation subroutine Est-Par (Line [4](#alg3.l4)) whenever the estimation is not “good enough” and not only in the first rounds.
The other estimation subroutines are executed until a certain number of updates is reached.
We show that the number of necessary exploration rounds is upper bounded by $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{3}}{{4}}})$. This will be useful in section [Section 5](#S5) to handle one-bit feedback.
Finally, in Lines [10](#alg3.l10) and [11](#alg3.l11) the algorithm selects the best price increments according to the current estimates (i.e., “commit” rounds), and posts price $p_{t}$ build accordingly to both agents.

Figure: Algorithm 3 Explore-Or-Commit for Bilateral Trade (EOC-BT)

The following theorem bounds the regret of [Algorithm 3](#alg3). Its proof can be found in Appendix [C](#A3).

###### Theorem 2 .

Set $\epsilon=(\log(T)/T)^{1/4}$, $\delta=\left(T(74+32P\epsilon^{-1})\right)^{-1}$, $\mu=\epsilon\big{(}P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A\big{)}^{-1}$, $\textnormal{T}^{\textnormal{int}}=\lceil 8P^{2}\log(1/\delta)\epsilon^{-2}\rceil$, and $\textnormal{T}^{\textnormal{FD}}=\lceil 2\log(1/\delta)\epsilon^{-2}\rceil$. Then, under Assumptions [1](#Thmassumption1) and [2](#Thmassumption2), there exist a constant $\mathaccent 0{\symlargesymbols}065{T}$ such that, if $T\geq\mathaccent 0{\symlargesymbols}065{T}$,
$R_{T}\leq\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{3}}{{4}}})$
with probability at least $1-T^{-1}$.

###### Sketch of the proof.

For some $\epsilon>0$ to be chosen later, let $K\approx P/\epsilon$. Using standard arguments [, ], we can show that $\mathaccent 0{\symlargesymbols}065{O}(\epsilon^{-2})$ samples are sufficient for Est-Par to ensure that, with high probability, for all $t\notin\mathcal{T}^{\textnormal{par}}$ the errors $|x_{t}^{\top}(\theta^{s}-\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t})|$ and $|x_{t}^{\top}(\theta^{b}-\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t})|$ are smaller than $\epsilon$. When this happens, classical concentration arguments ensure that $\mathaccent 0{\symlargesymbols}065{O}(\epsilon^{-2})$ samples are sufficient for Est-Int to estimate $I(k\epsilon)$ and $J(k\epsilon)$ with precision $\epsilon$ uniformly for $k\in\mathcal{K}$. By contrast, $\mathaccent 0{\symlargesymbols}065{O}(|\mathcal{K}|\epsilon^{-2})$ samples are necessary for Est-F and Est-F to estimate $F^{s}(k\epsilon)$ and $D^{b}(k\epsilon)$ with precision $\epsilon$ uniformly for $k\in\mathcal{K}$.
Therefore, with high probability, after approximately $\mathaccent 0{\symlargesymbols}065{O}(|\mathcal{K}|\epsilon^{-2})$ rounds of exploration, the expected gain from trade for prices $x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon$ is estimated with precision $O(\epsilon)$ uniformly for $k\in\mathcal{K}$. Furthermore, Assumption [2](#Thmassumption2) ensures that the reward function is Lipschitz-continuous, thus the discretization error is also of order $\mathaccent 0{\symlargesymbols}065{O}(\epsilon)$. By choosing $\epsilon=T^{\nicefrac{{-1}}{{4}}}$, we balance the estimation and discretization errors with the regret of the exploration phase, thereby obtaining a regret $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{3}}{{4}}})$.
∎

The regret of Algorithm [3](#alg3) is primarily driven by the estimation of the c.d.f. $F^{s}$ and demand function $D^{b}$ uniformly over a grid of increments. We now present an alternative sub-optimal approach, which allows us to introduce key concepts useful in the following section.
Specifically, to leverage the fact that the optimal increment $\delta^{s}$ only depends on the difference in average valuations t, we could first execute the sub-routines Est-Par and Est-Int, yielding estimates of $x_{t}^{\top}\theta^{s}$, $x_{t}^{\top}\theta^{b}$, $I$ and $J$ up to precision $\epsilon$ using $\mathaccent 0{\symlargesymbols}065{O}(\epsilon^{-2})$ samples. Then, we could round the value of t on a grid of size $\epsilon^{-1}$, and run independent Scouting Bandit algorithms (as described in []) for each of the $\epsilon^{-1}$ rounded values.
The grid size implies a discretization error of order $O(\epsilon)$. The highest regret occurs when each of the $\epsilon^{-1}$ independent Scouting Bandit algorithms runs for the same number of rounds $T_{\epsilon}=T\epsilon$. Each algorithm incurs a regret $\mathaccent 0{\symlargesymbols}065{O}(T_{\epsilon}^{\nicefrac{{2}}{{3}}})$, so their combined regret is
$\mathaccent 0{\symlargesymbols}065{O}(T_{\epsilon}^{\nicefrac{{2}}{{3}}}\cdot\epsilon^{-1})=\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{2}}{{3}}}\epsilon^{\nicefrac{{-1}}{{3}}})$. By selecting $\epsilon=T^{\nicefrac{{-1}}{{4}}}$, this strategy also results in a regret of order $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{3}}{{4}}})$.

###### Theorem 2 .

###### Sketch of the proof.

### 4.3 Closing the gap: scouting bandits with information pooling

Both the EOC strategy—where the reward function for all potential values of $(\delta^{s},{}_{t})$ is learned before committing to posting greedy prices—and strategies that use independent scouting bandit algorithms for each (rounded) value of t result in the same regret.
Surprisingly, we show that by combining the strengths of both strategies, it is possible to design an algorithm that achieves the optimal regret rate of $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{2}}{{3}}})$. To do this, we design a scouting bandit strategy with information pooling across different values of t. This idea is related to cross-learning, developed for bandits with graph feedback []. In particular, after having estimated $x_{t}^{\top}\theta^{s}$, $x_{t}^{\top}\theta^{b}$, $I$ and $J$, we run a successive elimination algorithm for each value of t. Then, to estimate the reward of a price corresponding to increments $\delta^{s}$ and $\delta^{b}$, we use the feedback from rounds where these increments have been selected across all values of t. This strategy, called Scouting Bandit with Information Pooling (SBIP), is described in Algorithm [4](#alg4) (a detailed description of the algorithm and proofs are deferred to [Appendix D](#A4)).

Figure: Algorithm 4 Scouting Bandit with Information Pooling (SBIP)

###### Theorem 3 .

Assume that the valuations of the buyer and the seller follow the noisy linear model in Equation ([3](#S2.E3)). Let $\epsilon=(d^{2}\log(T)^{2}/T)^{\nicefrac{{1}}{{3}}}$, $\delta=\left((38+16P\epsilon^{-1})(T+1)^{2}\right)^{-1}$, $\mu=\epsilon\,\big{(}P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A\big{)}^{-1}$, and $\textnormal{T}^{\textnormal{int}}=\lceil 8P^{2}\log(1/\delta)/\epsilon^{2}\rceil$. Then, under Assumptions [1](#Thmassumption1) and [2](#Thmassumption2), with probability at least $1-1/T$, [Algorithm 4](#alg4) has a regret bounded by
$R_{T}\leq\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{2}}{{3}}}).$

###### Sketch of the proof.

Let $r(x,p)\coloneqq\max_{p^{\prime}}\textnormal{EGFT}(x,p^{\prime})-\textnormal{EGFT}(x,p)$, and $\textnormal{T}^{\textnormal{par}}=|\mathcal{T}^{\textnormal{par}}|$.
The regret is bounded by $2P\textnormal{T}^{\textnormal{par}}+2P\textnormal{T}^{\textnormal{int}}+\sumop\slimits@_{t\notin\mathcal{T}^{\textnormal{par}}\cup\mathcal{T}^{\textnormal{int}}}r(x_{t},p_{t})$. The elliptical potential Lemma [] implies that $\textnormal{T}^{\textnormal{par}}\lesssim d^{2}\log(T)^{2}\epsilon^{-2}$, so $\textnormal{T}^{\textnormal{par}}+\textnormal{T}^{\textnormal{int}}\lesssim d^{2}\log(T)^{2}\epsilon^{-2}$.
By using concentration arguments and exploiting the Lipschitz continuity of the reward, we can show that, for all $t\notin\mathcal{T}^{\textnormal{par}}\cup\mathcal{T}^{\textnormal{int}}$ and $(k,k^{\prime})\in\mathcal{A}_{t}$, $[{\textnormal{LCB}}_{t}(k,k^{\prime}),{\textnormal{UCB}}_{t}(k,k^{\prime})]$ is a valid confidence interval for $\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}+k\epsilon)$. Now, we want to show that $r(x_{t},p_{t})\lesssim\mathaccent 0{\symlargesymbols}065{O}\big{(}\sqrt{\nicefrac{{1}}{{N^{k_{t},s}}}}+\sqrt{\nicefrac{{1}}{{N^{k^{\prime}_{t},b}}}}+\epsilon\big{)}$.
To prove this claim, we define $(k^{*}_{t},k_{t}^{{}^{\prime}*})\in\operatorname*{arg\,max}_{(k,k^{\prime})\in\mathcal{A}_{t}}\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}+k\epsilon)$. The Lipschitz-continuity of the reward ensures that the discretization error
is of order $O(\epsilon)$. Moreover, $[{\textnormal{LCB}}_{t}(k_{t},k^{\prime}_{t}),{\textnormal{UCB}}_{t}(k_{t},k^{\prime}_{t})]$ and $[{\textnormal{LCB}}_{t}(k^{*}_{t},k_{t}^{{}^{\prime}*}),{\textnormal{UCB}}_{t}(k^{*}_{t},k_{t}^{{}^{\prime}*})]$ are confidence intervals for $\textnormal{EGFT}(x_{t},p_{t})$ and $\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta^{s}}+k_{t}^{*}\epsilon)$, respectively, and ${\textnormal{LCB}}_{t}(k^{*}_{t},k_{t}^{{}^{\prime}*})\leq{\textnormal{UCB}}_{t}(k_{t},k^{\prime}_{t})$ by Line [13](#alg4.l13).
Then, it holds that $\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta^{s}}+k_{t}^{*}\epsilon)-\textnormal{EGFT}(x_{t},p_{t})$ is of order ${\textnormal{UCB}}_{t}(k_{t},k^{\prime}_{t})-{\textnormal{LCB}}_{t}(k_{t},k^{\prime}_{t})+{\textnormal{UCB}}_{t}(k^{*}_{t},k_{t}^{{}^{\prime}*})-{\textnormal{LCB}}_{t}(k^{*}_{t},k_{t}^{{}^{\prime}*})$. Our choice of $(k_{t},k^{\prime}_{t})$ ensures that $\min\{N^{k_{t},s},N^{k^{\prime}_{t},b}\}\leq\min\{N^{k^{*}_{t},s},N^{k_{t}^{{}^{\prime}*},s}\}$ (Line [14](#alg4.l14)).
Then, by definition of UCB and LCB, and since the discretization is at most $O(\epsilon)$, we get $r(x_{t},p_{t})\lesssim\mathaccent 0{\symlargesymbols}065{O}\big{(}\sqrt{\nicefrac{{1}}{{N^{k_{t},s}}}}+\sqrt{\nicefrac{{1}}{{N^{k^{\prime}_{t},b}}}}+\epsilon\big{)}$.

To bound the regret of the Successive Elimination phase, we consider separately the rounds (indexed by $\mathcal{T}^{s}_{k}$) where this bound is dominated by $\sqrt{\nicefrac{{1}}{{N^{k,s}}}}$ and $k_{t}=k$, and the rounds (indexed by $\mathcal{T}^{b}_{k^{\prime}}$) where it is dominated by $\sqrt{\nicefrac{{1}}{{N^{k^{\prime},b}}}}$ and $k_{t}^{\prime}=k^{\prime}$. Then, we decompose the regret of the Successive Elimination phase as $\sumop\slimits@_{t\notin\mathcal{T}^{\textnormal{par}}\cup\mathcal{T}^{\textnormal{int}}}r(x_{t},p_{t})=\sumop\slimits@_{k\in\mathcal{K}}(\sumop\slimits@_{t\in\mathcal{T}^{s}_{k}}r(x_{t},p_{t})+\sumop\slimits@_{t\in\mathcal{T}^{b}_{k}}r(x_{t},p_{t})).$
Choosing $r_{a}=2^{-a}$ and $r_{\overline{a}}\approx\epsilon$, we consider the decreasing sequence of intervals $(r_{a})_{a\leq\overline{a}}$. The previous result implies that if $N^{k,s}\in[\mathaccent 0{\symlargesymbols}065{O}(\nicefrac{{1}}{{r_{a}^{2}}}),\mathaccent 0{\symlargesymbols}065{O}(\nicefrac{{1}}{{r_{a+1}^{2}}})]$, then $r(x_{t},p_{t})\lesssim r_{a}$. This implies that

$$ $\sumop\slimits@_{t\in\mathcal{T}^{s}_{k}}r(x_{t},p_{t})\lesssim\mathaccent 0{\symlargesymbols}065{O}\bigg{(}r_{1}^{2}+\sumop\slimits@_{1\leq a\leq\overline{a}-1}r_{a}\left(r_{a+1}^{2}-r_{a}^{2}\right)+r_{\overline{a}}|\mathcal{T}_{k}^{s}|\bigg{)}.$ $$

This sum is of order $\textnormal{T}^{s}_{k}\epsilon+\nicefrac{{\log(\nicefrac{{1}}{{\delta}})}}{{\epsilon}}$. We sum over $(k,k^{\prime})\in\mathcal{K}$, and use the fact that $\sumop\slimits@_{k\in\mathcal{K}}\textnormal{T}^{s}_{k}+\textnormal{T}^{b}_{k}\leq T$ while $|\mathcal{K}|\approx\epsilon^{-1}$, to conclude that $R_{T}=\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{2}}{{3}}})$.
∎

###### Remark 1 .

Cesa-Bianchi et al. [] studied the related problem of non-contextual stochastic bilateral trade under similar assumptions (independent valuations with bounded densities and support). They obtain a lower bound on the regret of order $\Omega(T^{\nicefrac{{2}}{{3}}})$. This shows that, up to the constant $\mathaccent 0{\symlargesymbols}065{C}^{\prime}$, the dependence on the dimension $d$, and logarithmic factors, [Algorithm 4](#alg4) enjoys minimax optimal regret.

###### Theorem 3 .

###### Sketch of the proof.

###### Remark 1 .

## 5 Trading off budget balance constraints for feedback

In this section, we show that it is possible to relax the budget balance constraints in order to handle scenarios with limited feedback. In particular, we show that any EOC-like algorithm for two-bit feedback (for instance, [Algorithms 1](#alg1) and [3](#alg3)) can be suitably adapted to handle settings with one-bit feedback. To achieve this, we resort to the notion of global budget balance recently introduced by Bernasconi et al. [] and we show that budget can be exploited to compensate for the lack of feedback.
The notion of global budget balance requires the learner to be budget balanced only “overall” (i.e., over the whole time horizon). In particular, let $\textsc{Profit}_{t}(p,q)\coloneqq\mathbb{I}{\left\{s_{t}\leq p\right\}}\mathbb{I}{\left\{q\leq b_{t}\right\}}(q-p)$ be the profit extracted by the learner at time $t$ by posting prices $(p,q)$. Then, the learning algorithm is global budget balanced if the following inequality holds: $\sumop\slimits@_{t=1}^{T}\textsc{Profit}(p_{t},q_{t})\geq 0$.

Given an EOC-like algorithm for the two-bit strong budget balance set-up, the idea is to simulate its exploration rounds by doing separate updates for the seller and the buyer, each using a single bit of feedback. In particular, each time in which the two-bit algorithm uses the seller’s feedback $\mathbb{I}{\left\{s_{t}\leq p\right\}}$, the one-bit algorithm needs to actively collect that information by posting $(p,-P)$ instead of $(p,p)$.
Notice that, even under one-bit feedback, if the learner posts price $(p,-P)$ it is able to observe $\mathbb{I}{\left\{s_{t}\leq p\right\}}$ since the buyer is always going to accept the trade.
Analogously, when the two-bit algorithm would employ $\mathbb{I}{\left\{b_{t}\geq p\right\}}$, the one-bit algorithm has to collect that information by posting $(P,p)$.
For instance, instead of executing Est-Par, the one-bit algorithm runs two exploration phases: one in which it updates only $\mathaccent 0{\symlargesymbols}062{\theta}^{s}$ (Line [4](#alg2.l4) of Est-Par) by posting $(p_{t},-P)$, and one in which it updates only $\mathaccent 0{\symlargesymbols}062{\theta}^{b}$ by posting $(P,p_{t^{\prime}})$. The same happens for the other estimation subroutines.

The one-bit algorithm simulates access to finer-grained feedback by posting pairs of prices $(P,p)$, $(p,-P)$. These prices result in a negative GFT. By enforcing global budget balance, we allow the learning algorithm to set prices that are not budget balanced individually, as long as the overall budget balance is maintained. To do that, we add an initial “budget-collection” phase where the learning algorithm builds up enough profit to be able to sustain the following exploration round.
We demonstrate that sufficient profit can be accumulated during the budget-collection phase without incurring excessive regret relative to GFT. This allows us to provide sublinear regret guarantees under one-bit feedback, with rates depending on some natural characteristics of the underlying market.

Collecting budget. Let $\mathcal{B}$ be the budget required by the one-bit algorithm to cover the rounds in which it must post either $(P,p)$ or $(p,-P)$ to collect information (the value of $\mathcal{B}$ will be set later). Therefore, the budget collection phase ends as soon as $\sumop\slimits@_{t}\textsc{Profit}(p_{t},q_{t})\geq\mathcal{B}$. We denote by $\tau$ the random variable indicating the last round of the budget-collection phase. Moreover, let $\mathcal{T}^{\textnormal{B}}\coloneqq\llbracket\tau\rrbracket$ be the random set of rounds designated for budget collection.
For each round $t\in\mathcal{T}^{\textnormal{B}}$, the algorithm samples a price $p_{t}$ uniformly from $[-P,P]$, and a value $i_{t}$ uniformly from $[0,\log T]$. Then, it posts a pair of prices $(p_{t},q_{t})$, where $q_{t}=p_{t}+2^{-i_{t}}$.
We start by providing a lower bound to the per-round expected profit obtained by posting $(p_{t},p_{t}+2^{-i_{t}})$.

###### Lemma 2 .

For each round $t\in\mathcal{T}^{\textnormal{B}}$ such that $b_{t}\geq s_{t}$, it holds:
$\mathbb{E}\left[\textsc{Profit}_{t}(p_{t},q_{t})\right]\geq\frac{(b_{t}-s_{t})^{2}}{8P\log T}-\frac{2}{T},$
where the expectation is with respect to the choice of $(p_{t},q_{t})$.

The guarantees provided by the one-bit algorithm depend on how “active” is the market. We start by assuming that the market is well-behaved, meaning that trade opportunities arise frequently enough. Formally, we require that for a sufficiently long time $t^{\prime}$, the cumulative social welfare is $\Omega(t^{\prime})$.

###### Assumption 3 .

Given $\alpha\in(0,1)$, for each $t^{\prime}\geq\log(T)$, it holds $\sumop\slimits@_{t\in\llbracket t^{\prime}\rrbracket}(b_{t}-s_{t})\geq\alpha t^{\prime}$.(^2^22The case in which the condition holds with high probability can be addressed with minor variations.)

[Remark 2](#Thmremark2) described the guarantees that can be obtained in the absence of this assumption.
We observe that the budget-collection phase will have at least length $\log T$ since $\tau\in[\nicefrac{{\mathcal{B}}}{{2P}},T]$, and $\mathcal{B}=\Omega(\log T)$ even in the setting without noise. Then, assuming the environment allows for enough budget to be collected during the first phase, we can show that the profit accumulated by time $\tau$ is at least a factor of $1/\log T$ of the cumulative GFT up to that point, assuming all trades up to $\tau$ had occurred.

###### Lemma 3 .

Under [3](#Thmassumption3), for $\tau\geq\log T$, it holds with probability at least $1-1/T$ that

$$ $\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\textsc{Profit}_{t}(p_{t},q_{t})\geq\frac{\alpha}{8P\log(T)}\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}-\sqrt{4P^{2}\log(T)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}}-2.$ $$

Given a two-bit algorithm $\mathcal{A}$ such that, with probability at least $1-1/T$, it requires at most $T^{\textnormal{E}}$ exploration rounds, and has regret for the commit phase of $R_{T}^{(\textnormal{2 bit})}$, by setting the overall budget to $\mathcal{B}=\max\left\{2048P^{4}\alpha^{-2}\log^{3}T,\,2PT^{\textnormal{E}}\right\}$, the one-bit learning algorithm has the following guarantees.(^3^33We observe that, with probability at most $1/T$, the budget $\mathcal{B}$ is not sufficient to cover $T^{\textnormal{E}}$ exploration rounds. When this occurs, we stop the exploration and start posting arbitrary strong budget balanced prices.)

###### Theorem 4 .

Under [3](#Thmassumption3), given the two-bit algorithm $\mathcal{A}$, the corresponding one-bit learning algorithm satisfies global budget balance and, with probability at least $1-1/T$, has regret

$$ $R_{T}^{(\textnormal{1 bit})}\leq O(T^{\textnormal{E}})\cdot\textnormal{polylog}(T)+R_{T}^{(\textnormal{2 bit})}.$ $$

For instance, under the set-up of [Section 4](#S4), we can use [Algorithm 3](#alg3) as $\mathcal{A}$. Then, $\mathcal{B}\leq 4PT^{\textnormal{E}}=4P\cdot 2P\left(|\mathcal{T}^{\textnormal{par}}_{T+1}|+\textnormal{T}^{\textnormal{int}}+2|\mathcal{K}|\textnormal{T}^{\textnormal{FD}}\right)$, which is of order $\mathaccent 0{\symlargesymbols}065{O}(P^{4}dT^{\nicefrac{{3}}{{4}}})$. Therefore, the final regret bound in the noisy, one-bit setting with global budget balance is of order $\mathaccent 0{\symlargesymbols}065{O}(T^{3/4})$. A similar argument shows that in the noiseless setting of [Section 3](#S3) the regret is of order $\textnormal{polylog}(T)$.

###### Remark 2 .

In the absence of [3](#Thmassumption3), we can still establish sublinear regret guarantees under one-bit feedback and global budget balance. The main modification to the previous analysis is halting the proof of [Lemma 3](#Thmlemma3) prior to employing [3](#Thmassumption3). This results in the following bound:

$$ $\textstyle\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\textsc{Profit}_{t}(p_{t},q_{t})\geq\Omega\left(\tau^{-1}\left(\sumop\slimits@_{t\in\llbracket\tau\rrbracket}([b_{t}-s_{t})]^{+}\right)^{2}\right)-\mathaccent 0{\symlargesymbols}065{O}(\sqrt{T}).$ $$

By selecting an appropriate duration for the exploration phase of the two-bit algorithm, we can employ this inequality to bound the regret during the budget-collection phase. For example, by setting $\mathcal{T}^{\textnormal{E}}\approx\log T$, we achieve a regret of $\mathaccent 0{\symlargesymbols}065{O}(T^{3/4})$ in the deterministic set-up of [Section 3](#S3), and by setting $T^{\textnormal{E}}\approx T^{\nicefrac{{3}}{{4}}}$ we achieve a regret of $\mathaccent 0{\symlargesymbols}065{O}(T^{\nicefrac{{7}}{{8}}})$ in the noisy set-up of [Section 4](#S4).

###### Lemma 2 .

###### Assumption 3 .

###### Lemma 3 .

###### Theorem 4 .

###### Remark 2 .

## Acknowledgments

MB, MC, and AC are partially supported by the FAIR (Future Artificial Intelligence Research) project PE0000013, funded by the NextGenerationEU program within the PNRR-PE-AI scheme (M4C2, investment 1.3, line on Artificial Intelligence). MC is also partially supported by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainability, No. 101120237). AC is partially supported by MUR - PRIN 2022 project 2022R45NBB funded by the NextGenerationEU program. VP acknowledges support from the French National Research Agency (ANR) under grant number ANR-19-CE23- 0026 as well as from the grant “Investissements d’Avenir” (LabEx Ecodec/ANR-11-LABX-0047). SG gratefully acknowledges funding from the Hadamard Doctoral School of Mathematics (EDMH).

## Appendix A Basic facts about ellipsoids

An ellipsoid $E$ with center $c\in\mathbb{R}^{d}$ and positive definite matrix $\mathbf{M}\in\mathbb{R}^{d\times d}$ is defined as

$$ $E(\mathbf{M},c)\coloneqq\left\{x\in\mathbb{R}^{d}:\|x-c\|_{\mathbf{M}^{-1}}\leq 1\right\}.$ $$

Given an hyperplane $H(a,c)\coloneqq\{x\in\mathbb{R}^{d}:a^{\top}(x-c)\leq 0\}$, the minimal volume ellipsoid containing $K=E(\mathbf{M},c)\cap H(a,c)$ can be computed in closed form as follows. The new center is

$$ $c^{\prime}=c-\frac{1}{d+1}\cdot\frac{1}{\sqrt{a^{\top}\mathbf{M}a}}\mathbf{M}a,$ $$

and the new positive definite matrix is

$$ $\mathbf{M}^{\prime}=\frac{d^{2}}{d^{2}-1}\left(\mathbf{M}-\frac{2}{d+1}\cdot\frac{\mathbf{M}aa^{\top}\mathbf{M}}{a^{\top}\mathbf{M}a}\right).$ $$

Then, the Löwner-John ellipsoid $\text{LJ}(K)$ of the half ellipsoid $K$ is the ellipsoid $E(\mathbf{M}^{\prime},c^{\prime})$.

Going from $E(\mathbf{M},c)$ to $E(\mathbf{M}^{\prime},c^{\prime})$ the volume shrinks by the following amount:

$$ $\textnormal{vol}(E(\mathbf{M}^{\prime},c^{\prime}))\leq e^{\nicefrac{{-1}}{{2d}}}\textnormal{vol}(E(\mathbf{M},c)).$ $$

An in-depth analysis of these results can be found in Grötschel et al. [].

## Appendix B Proof of Theorem 1

See [1](#Thmtheorem1)

###### Proof.

The proof of [Theorem 1](#Thmtheorem1) relies on the fact that when the algorithm updates $E^{s}_{t}$ or $E^{b}_{t}$, it behaves as the EllipsoidPricing algorithm of Cohen et al. []. More precisely, we first note that under [1](#Thmassumption1), $E^{s}_{1}$ and $E^{b}_{1}$ contain $\theta^{s}$ and $\theta^{b}$, respectively. Moreover, straightforward induction shows that if $E^{s}_{t}$ contains $\theta^{s}$, then $K^{s}_{t+1}$ also contains $\theta^{s}$, and so does $E^{s}_{t+1}$ (similar reasoning applies to $\theta^{b}$ and $E^{b}_{t}$).

This implies that for all rounds, $\underline{s_{t}}\leq s_{t}\leq\overline{s_{t}}$, and $\underline{b_{t}}\leq b_{t}\leq\overline{b_{t}}$. In particular, if the condition in Line [5](#alg1.l5) is verified, we have $s_{t}\leq p_{t}\leq b_{t}$, and so the instantaneous regret at that round is 0.

We also underline that [Algorithm 1](#alg1) only explores to estimate $\theta^{s}$ (Line [6](#alg1.l6)) if the condition

$$ $\max_{\theta\in E^{s}_{t}}x_{t}^{\top}\theta-\min_{\theta\in E^{s}_{t}}x_{t}^{\top}\theta\geq\epsilon$ $$

is verified, or equivalently if

$$ $\max_{\theta\in E^{s}_{t}}\frac{x_{t}^{\top}}{B}\theta-\min_{\theta\in E^{s}_{t}}\frac{x_{t}^{\top}}{B}\theta\geq\frac{\epsilon}{B}.$ $$

Since the normalized contexts $\frac{x_{t}^{\top}}{B}$ are bounded in norm by 1 by [1](#Thmassumption1), we can apply Lemma 1 by Cohen et al. []. This Lemma states that [Algorithm 1](#alg1) will execute the steps in Lines [7](#alg1.l7)-[8](#alg1.l8) at most $2d^{2}\log(20A(d+1)/\frac{\epsilon}{B})$ times, after which the condition in Line [6](#alg1.l6) will never be verified again. A similar reasoning allows us to bound the number of exploration rounds for the buyer’s parameter $\theta^{b}$ (Line [9](#alg1.l9)). Therefore, the total number of exploration rounds is bounded by $2\times 2d^{2}\log(20A(d+1)/\frac{\epsilon}{B})$. We notice that [1](#Thmassumption1) also implies that the valuations are in $[-AB,AB]$, and so the instantaneous regret is bounded by $2AB$. Thus, the regret of the exploration phase (Lines [6](#alg1.l6) and [9](#alg1.l9)) is bounded by $8ABd^{2}\log(20A(d+1)/\frac{\epsilon}{B})$.

Finally, if the conditions on Lines [5](#alg1.l5), [6](#alg1.l6) and [9](#alg1.l9) are not verified, it implies that

$$ $\displaystyle b_{t}-s_{t}$ $\displaystyle\leq\overline{b}_{t}-\underline{s_{t}}$ $\displaystyle\leq\underline{b}_{t}+\epsilon-\overline{s_{t}}+\epsilon$ $\displaystyle\leq 2\epsilon.$ $$

Then, the instantaneous regret at that round is at most $2\epsilon$, and the total regret for these steps is at most $2\epsilon T$. Choosing $\epsilon=\frac{ABd^{2}}{T}$ yields the result.
∎

###### Proof.

## Appendix C Proof of Theorem 2

In order to prove Theorem [2](#Thmtheorem2), we provide a more detailed version of the Explore-Or-Commit algorithm in Algorithm [5](#alg5). Note that we adopt the convention $1/0=+\infty$.

Figure: Algorithm 5 Explore-Or-Commit (detailed version)

Before analyzing the Explore-Or-Commit algorithm, we define the various quantities used within it. Specifically, $\mathcal{T}^{\textnormal{par}}_{t}$ represents the set of indices from previous rounds that were dedicated to estimating the parameters $\theta^{s}$ and $\theta^{b}$ (Line [8](#A3.Ex17)).
We denote by $\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}$ and $\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}$ the estimates for the parameters, and $\mathbf{V}_{t}$ is the corresponding empirical covariance matrix at the beginning of round $t$.
The set $\mathcal{T}^{\textnormal{int}}$ contains the indices of the rounds used to estimate the integrals $I$ and $J$ (Line [13](#alg5.l13)). Moreover, $\mathaccent 0{\symlargesymbols}062{I}^{k}$ is the estimate of $I(k\epsilon)$, and $\mathaccent 0{\symlargesymbols}062{J}^{k}$ is the estimate of $J(k\epsilon)$. The quantities $\mathaccent 0{\symlargesymbols}062{F}^{k}$ and $\mathaccent 0{\symlargesymbols}062{D}^{k}$ represent our estimates of $F^{s}(k\epsilon)$ and $D^{b}(k\epsilon)$, respectively.

We use the following lemma to bound the total duration of the parameter exploration phase (the proof can be found in [Section E.2](#A5.SS2)).

###### Lemma 4 .

Almost surely, the length of exploration phase $\mathcal{T}^{\textnormal{par}}_{T+1}$ is bounded as

$$ $|\mathcal{T}^{\textnormal{par}}_{T+1}|\leq\frac{d\log\left(\frac{T+d}{d}\right)}{\mu^{2}}.$ $$

The following lemma provides bounds on the estimation errors for $\theta^{s}$, $\theta^{b}$, $I$, $J$, $F^{s}$, and $D^{b}$ for the values of $\mu$, $\textnormal{T}^{\textnormal{int}}$, and $\textnormal{T}^{\textnormal{FD}}$ specified in Theorem [3](#Thmtheorem3).
Let $\mathcal{E}$ be the event

$$ $\displaystyle\mathcal{E}\coloneqq\Big{\{}\forall k\in\mathcal{K},\ \forall t\notin\mathcal{T}^{\textnormal{par}}_{T}\cup\mathcal{T}^{\textnormal{int}}\,\,$ $\displaystyle\left|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b})\right|\leq\epsilon\textnormal{ and }$ $\displaystyle\left|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s})\right|\leq\epsilon\textnormal{ and }$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{I}^{k}-I\left(k\epsilon\right)\right|\leq 2\epsilon\textnormal{ and }$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{J}^{k}-J(k\epsilon)\right|\leq 2\epsilon\Big{\}}.$ $$

Let us define the exploitation (i.e., commit) phase as

$$ $\mathcal{T}^{\textnormal{C}}\coloneqq\llbracket T\rrbracket\setminus\left(\mathcal{T}^{\textnormal{par}}_{T}\cup\mathcal{T}^{\textnormal{int}}\underset{k\in\mathcal{K}}{\bigcupop\slimits@}\left(\mathcal{T}^{\textnormal{F}}_{k}\cup\mathcal{T}^{\textnormal{D}}_{k}\right)\right).$ $$

Moreover, let $\mathcal{E}^{\textnormal{EOC}}$ be the event

$$ $\displaystyle\mathcal{E}^{\textnormal{EOC}}\coloneqq\mathcal{E}\cap\left\{\forall k\in\mathcal{K},\ \forall t\in\mathcal{T}^{\textnormal{C}},\left|\mathaccent 0{\symlargesymbols}062{F}^{k}-F^{s}(k\epsilon)\right|\leq(L+1)\epsilon\text{ and }\left|\mathaccent 0{\symlargesymbols}062{D}^{k}-D^{s}(k\epsilon)\right|\leq(L+1)\epsilon\right\}.$ $$

Then, we can lower bound the probability of event $\mathcal{E}^{\textnormal{EOC}}$ as follows (the proof is postponed to [Section E.3](#A5.SS3)).

###### Lemma 5 .

For the choice $\mu=\epsilon\left(P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A\right)^{-1}$, $\textnormal{T}^{\textnormal{int}}=8P^{2}\log(1/\delta)/\epsilon^{2}$, and $\textnormal{T}^{\textnormal{FD}}=2\log(1/\delta)\epsilon^{-2}$, it holds that

$$ $\mathbb{P}\left(\mathcal{E}^{\textnormal{EOC}}\right)\geq 1-2\delta-8\delta(2K+1).$ $$

Note that the choice $\delta=\left(T(74+32P\epsilon^{-1})\right)^{-1}$ ensures that the event $\mathcal{E}^{\textnormal{EOC}}$ happens with probability at least $1-T^{-1}$.

The following Lemma bounds the error for estimating the gain from trade of a price $p=x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon$ on the high-probability event $\mathcal{E}^{\textnormal{EOC}}$ (the proof is presented in [Section E.4](#A5.SS4)).

###### Lemma 6 .

On the event $\mathcal{E}^{\textnormal{EOC}}$, for all $t\in\mathcal{T}^{\textnormal{C}}$, and all $(k,k^{\prime})\in\mathcal{A}_{t}$,

$$ $\left|\mathaccent 0{\symlargesymbols}062{I}^{k^{\prime}}\mathaccent 0{\symlargesymbols}062{F}^{k}+\mathaccent 0{\symlargesymbols}062{J}^{k}\mathaccent 0{\symlargesymbols}062{D}^{k^{\prime}}-\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon)\right|\leq(10PL+4P+7)\epsilon.$ $$

Next, we bound the discretization error. Let us define

$$ $(k^{*}_{t},k^{\prime*}_{t})\in\operatorname*{arg\,max}_{(k,k^{\prime})\in\mathcal{A}_{t}}\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k\epsilon).$ $$

Then, the following result holds (see [Section E.5](#A5.SS5) for its proof).

###### Lemma 7 .

On the event $\mathcal{E}^{\textnormal{EOC}}$, we have that

$$ $\left|\max_{p}\textnormal{EGFT}(x_{t},p)-\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k_{t}^{*}\epsilon)\right|\leq 2LP\epsilon.$ $$

We are now ready to prove Theorem [2](#Thmtheorem2). For $p\in\mathbb{R}$, $x\in\mathbb{R}^{d}$, we define

$$ $\Delta(x,p)\coloneqq\max_{p^{\prime}}\textnormal{EGFT}(x,p^{\prime})-\textnormal{EGFT}(x,p).$ $$

We begin by decomposing the regret as

$$ $\displaystyle R_{T}=$ $\displaystyle\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{par}}_{T+1}}\Delta(x_{t},p_{t})+\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{int}}}\Delta(x_{t},p_{t})+$ $\displaystyle\sumop\slimits@_{k\in\mathcal{K}}\left(\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{F}}_{k}}\Delta(x_{t},p_{t})+\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{D}}_{k}}\Delta(x_{t},p_{t})\right)+\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{C}}}\Delta(x_{t},p_{t}).$ $$

Using the fact that $\Delta(x_{t},p_{t})\leq 2P$, we obtain

$$ $\displaystyle R_{T}\leq$ $\displaystyle 2P\left(|\mathcal{T}^{\textnormal{par}}_{T+1}|+\textnormal{T}^{\textnormal{int}}+2|\mathcal{K}|\textnormal{T}^{\textnormal{FD}}\right)+\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{C}}}\Delta(x_{t},p_{t}).$ $$

On the one hand, Lemma [4](#Thmlemma4) implies that $|\mathcal{T}^{\textnormal{par}}_{T+1}|\leq\frac{d\log\left(\frac{T+d}{d}\right)}{\mu^{2}}.$ For the choice $\mu=\epsilon\left(P\left(d\log\left(\frac{1+B^{2}T}{\delta}\right)\right)^{\nicefrac{{1}}{{2}}}+A\right)^{-1}$, $\textnormal{T}^{\textnormal{int}}=8P^{2}\log(1/\delta)\epsilon^{-2}$, and $\textnormal{T}^{\textnormal{FD}}=2\log(1/\delta)\epsilon^{-2}$, this implies that

$$ $\displaystyle R_{T}\leq$ $\displaystyle 2Pd\log\left(\frac{T+d}{d}\right)\left(P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A\right)^{2}\epsilon^{-2}+16P^{3}\log(1/\delta)\epsilon^{-2}+$ $\displaystyle 8P\left(\frac{4P}{\epsilon}+9\right)\log(1/\delta)\epsilon^{-2}+\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{C}}}\Delta(x_{t},p_{t}).$ $$

Note that the first term is of order $\epsilon^{-3}$ when $\epsilon$ is small enough. On the other hand, on the event $\mathcal{E}^{\textnormal{EOC}}$, by Lemma [7](#Thmlemma7) we have

$$ $\displaystyle\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{C}}}\Delta(x_{t},p_{t})$ $\displaystyle=\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{C}}}\Delta(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k^{*}_{t}\epsilon)+\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{C}}}\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k_{t}^{*}\epsilon)-\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k_{t}\epsilon)$ $\displaystyle\leq 2TLP\epsilon+\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{C}}}\left(\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k_{t}^{*}\epsilon)-\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k_{t}\epsilon)\right),$ $$

Moreover, our choice of $k_{t}$ ensures that for $k^{\prime}_{t}$ such that $(k_{t},k^{\prime}_{t})\in\mathcal{A}_{t}$,

$$ $\displaystyle\mathaccent 0{\symlargesymbols}062{I}^{k^{\prime}_{t}}\mathaccent 0{\symlargesymbols}062{F}^{k_{t}}+\mathaccent 0{\symlargesymbols}062{J}^{k_{t}}\mathaccent 0{\symlargesymbols}062{D}^{k^{\prime}_{t}}$ $\displaystyle\geq\mathaccent 0{\symlargesymbols}062{I}^{k_{t}^{{}^{\prime}*}}\mathaccent 0{\symlargesymbols}062{F}^{k^{*}_{t}}+\mathaccent 0{\symlargesymbols}062{J}^{k^{*}_{t}}\mathaccent 0{\symlargesymbols}062{D}^{k_{t}^{{}^{\prime}*}}.$ $$

By Lemma [6](#Thmlemma6), this implies that, on event $\mathcal{E}^{\textnormal{EOC}}$,

$$ $\displaystyle\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k_{t}^{*}\epsilon)-\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k_{t}\epsilon)\leq(20PL+8P+14)\epsilon.$ $$

Thus, on the event $\mathcal{E}^{\textnormal{EOC}}$,

$$ $\displaystyle R_{T}\leq$ $\displaystyle 2Pd\log\left(\frac{T+d}{d}\right)\left(P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A\right)^{2}\epsilon^{-2}+16P^{3}\log(1/\delta)/\epsilon^{2}$ $\displaystyle+8P\left(\frac{P}{\epsilon}+3\right)\log(1/\delta)\epsilon^{-2}+2TLP\epsilon+T(20PL+8P+14)\epsilon.$ $$

Substituting the values of $\epsilon$ and $\delta$ as per Theorem [2](#Thmtheorem2) and using Lemma [5](#Thmlemma5) allows us to conclude the proof.

###### Lemma 4 .

###### Lemma 5 .

###### Lemma 6 .

###### Lemma 7 .

## Appendix D Proof of Theorem 3

### D.1 Detailed Algorithm

In order to prove Theorem [3](#Thmtheorem3), we provide a more detailed version of the Scouting Bandit with Information Pooling algorithm in Algorithm [6](#alg6). Note that in Lines 16 an 17, we adopt the convention $1/0=+\infty$ when computing the upper- and lower- confidence bounds for increment levels $k,k^{\prime}$ that have not yet been selected.

Figure: Algorithm 6 Scouting Bandits with Information Pooling (SBIP) (detailed version)

Before analyzing the SBIP algorithm, we introduce the different quantities appearing in the algorithm.
In words, $\mathcal{T}^{\textnormal{par}}_{t}$ is the set of indices of the previous rounds that have been spent estimating the parameters $\theta^{s}$ and $\theta^{b}$ at the beginning of round $t$. Similarly, $\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}$, $\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}$, and $\mathbf{V}_{t}$ are the estimates of the parameters and the corresponding empirical covariance matrix at the beginning of round $t$. The set $\mathcal{T}^{\textnormal{int}}$ consists of the indices of the rounds used to estimate the integrals $I$ and $J$. Moreover, $\mathaccent 0{\symlargesymbols}062{I}^{k}$ estimates $I(k\epsilon)$, and $\mathaccent 0{\symlargesymbols}062{J}^{k}$ estimates $J(k\epsilon)$. The quantities $\mathaccent 0{\symlargesymbols}062{F}^{k}_{t}$ and $\mathaccent 0{\symlargesymbols}062{D}^{k}_{t}$ represent our estimates of $F^{s}(k\epsilon)$ and $D^{b}(k\epsilon)$ at the beginning of round $t$.
Similarly, $N^{s,k}_{t}$ (resp., $N^{b,k}_{t}$) counts the number of rounds in the successive elimination phase where the increment $p_{l}-x_{l}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{l}$ was equal to $k\epsilon$ (resp., where the increment $p_{l}-x_{l}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{l}$ was close to $k\epsilon$), and where we gained information on $F^{s}(k\epsilon)$ (resp., on $D^{b}(k\epsilon)$). The set $\mathcal{A}_{t}$ collects the pairs $(k,k^{\prime})\in\mathcal{K}$ such that $x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon\approx x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}+k^{\prime}\epsilon$ is a possible price (within $[-P,P]$). Then, for $(k,k^{\prime})\in\mathcal{A}_{t}$, the quantities ${\textnormal{UCB}}_{t}(k,k^{\prime})$ and ${\textnormal{LCB}}_{t}(k,k^{\prime})$ provide upper and lower confidence bounds on the expected gain from trade corresponding to this price.

The third phase is a *successive elimination phase*: at each round, we consider a set of possible optimal prices, with corresponding upper confidence bound larger than the highest lower confidence bound. This set is denoted by $\mathcal{K}_{t}$.
In order to ensure sufficient exploration of all potentially optimal price increments $(k\epsilon,k^{\prime}\epsilon)$ for $(k,k^{\prime})\in\mathcal{K}_{t}$, we choose the price increment with the widest confidence interval: this corresponds to choosing the pair $(k,k^{\prime})\in\mathcal{K}_{t}$ such that either $N_{t}^{s,k}$ or $N_{t}^{b,k^{\prime}}$ is the lowest of the set. We denote $(k_{t},k^{\prime}_{t})$ the pair of increments chosen in such way. In order to analyze this phase, we store the indexes of the rounds where we chose this pair because $N_{t}^{s,k_{t}}$ was the smallest in the set $\mathcal{T}^{\textnormal{SE}}_{s,k_{t}}$. Analogously, the rounds where we chose this pair because $N_{t}^{b,k^{\prime}_{t}}$ was the smallest are stored in the set $\mathcal{T}^{\textnormal{SE}}_{b,k^{\prime}_{t}}$).

### D.2 Regret Analysis

The beginning of the proof of Theorem [3](#Thmtheorem3) is similar to that of Theorem [2](#Thmtheorem2). As in the previous case, we define the event

$$ $\displaystyle\mathcal{E}\coloneqq\Big{\{}\forall k\in\mathcal{K},\ \forall t\notin\mathcal{T}^{\textnormal{par}}_{T+1}\cup\mathcal{T}^{\textnormal{int}},$ $\displaystyle\left|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b})\right|\leq\epsilon,\,\,\left|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s})\right|\leq\epsilon,$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{I}^{k}-I\left(k\epsilon\right)\right|\leq 2\epsilon,\,\,\left|\mathaccent 0{\symlargesymbols}062{J}^{k}-J(k\epsilon)\right|\leq 2\epsilon\Big{\}}.$ $$

Moreover, we define a new event $\mathcal{E}^{\textnormal{SBIP}}$ as

$$ $\displaystyle\mathcal{E}^{\textnormal{SBIP}}\coloneqq\mathcal{E}\bigcapop\slimits@\Big{\{}\forall k\in\mathcal{K},\ \forall t\notin\mathcal{T}^{\textnormal{par}}_{T+1}\cup\mathcal{T}^{\textnormal{int}},$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{F}^{k}_{t}-F^{s}(k\epsilon)\right|\leq\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}+L\epsilon,$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{D}^{k}-D^{s}(k\epsilon)\right|\leq\sqrt{\frac{2\log(1/\delta)}{N^{b,k}_{t}}}+2L\epsilon\Big{\}}.$ $$

The following Lemma shows that the event $\mathcal{E}^{\textnormal{SBIP}}$ happens with large probability. The detailed proof can be found in [Section E.6](#A5.SS6).

###### Lemma 8 .

For the choice $\mu=\epsilon\left(P\left(d\log\left(\frac{1+B^{2}T}{\delta}\right)\right)^{\nicefrac{{1}}{{2}}}+A\right)^{-1}$ and $\textnormal{T}^{\textnormal{int}}=8P^{2}\log(1/\delta)/\epsilon^{2}$, it holds that

$$ $\mathbb{P}\left(\mathcal{E}^{\textnormal{SBIP}}\right)\geq 1-2\delta-4\delta(2K+1)-4\delta(2K+1)T.$ $$

Note that the choice $\delta=\left(T(38+16P\epsilon^{-1}+16P\epsilon^{-1}T+36T)\right)^{-1}$ ensures that the event $\mathcal{E}^{\textnormal{SBIP}}$ happens with probability at least $1-T^{-1}$.

The following Lemma (whose proof is located in [Section E.7](#A5.SS7)) shows that the upper and lower confidence bounds used in Algorithm [6](#alg6) hold conditioned on the high-probability event $\mathcal{E}^{\textnormal{SBIP}}$.

###### Lemma 9 .

Under the assumptions of Lemma [8](#Thmlemma8) and conditioned on the event $\mathcal{E}^{\textnormal{SBIP}}$, we have that for all $t\notin\mathcal{T}^{\textnormal{par}}_{T+1}\cup\mathcal{T}^{\textnormal{int}}$, and all $(k,k^{\prime})\in\mathcal{A}_{t}$;

$$ $\displaystyle{\textnormal{LCB}}_{t}(k,k^{\prime})\leq\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k\epsilon)\leq{\textnormal{UCB}}_{t}(k,k^{\prime}).$ $$

Moreover, it holds that $(k^{*}_{t},k^{\prime*}_{t})\in\mathcal{K}_{t}$, where we recall that

$$ $(k^{*}_{t},k^{\prime*}_{t})\in\operatorname*{arg\,max}_{(k,k^{\prime})\in\mathcal{A}_{t}}\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k\epsilon).$ $$

Finally, we bound the number of times a sub-optimal price increment $k\epsilon$ can be selected. For $p\in\mathbb{R}$, $x\in\mathbb{R}^{d}$, recall that we defined

$$ $r(x,p)=\max_{p^{\prime}}\textnormal{EGFT}(x,p^{\prime})-\textnormal{EGFT}(x,p).$ $$

###### Lemma 10 .

Conditioned on the event $\mathcal{E}^{\textnormal{SBIP}}$, if $t\in\mathcal{T}^{\textnormal{SE}}_{s,k}$, then the following condition holds

$$ $\displaystyle r(x_{t},p_{t})\leq(50PL+28)\epsilon+16P\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}.$ $$

Similarly, if $t\in\mathcal{T}^{\textnormal{SE}}_{b,k^{\prime}}$, then the following condition holds

$$ $\displaystyle r(x_{t},p_{t})\leq(50PL+28)\epsilon+16P\sqrt{\frac{2\log(1/\delta)}{N^{b,k^{\prime}}_{t}}}.$ $$

The proof for this result can be found in [Section E.8](#A5.SS8).

We are now ready to bound the regret of SBIP. We begin by decomposing the regret as

$$ $\displaystyle R_{T}=\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{par}}_{T+1}}r(x_{t},p_{t})+\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{int}}}r(x_{t},p_{t})+\sumop\slimits@_{t\notin\mathcal{T}^{\textnormal{par}}_{T+1}\cup\mathcal{T}^{\textnormal{int}}}r(x_{t},p_{t}).$ $$

Since the gain from trade is bounded by $2P$, this implies

$$ $\displaystyle R_{T}\leq 2P|\mathcal{T}^{\textnormal{par}}_{T+1}|+2P|\mathcal{T}^{\textnormal{int}}|+\sumop\slimits@_{t\notin\mathcal{T}^{\textnormal{par}}_{T+1}\cup\mathcal{T}^{\textnormal{int}}}r(x_{t},p_{t}).$ $$

Then, using Lemma [4](#Thmlemma4), by setting $\mu=\epsilon\left(P\left(d\log\left(\frac{1+B^{2}T}{\delta}\right)\right)^{\nicefrac{{1}}{{2}}}+A\right)^{-1}$ and $\textnormal{T}^{\textnormal{int}}=8P^{2}\log(1/\delta)/\epsilon^{2}$ we have

$$ $R_{T}\leq\epsilon^{-2}\left(2Pd\log\left(\frac{T+d}{d}\right)\left(P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A\right)^{2}\right)+\\ 16\epsilon^{-2}P^{3}\log(1/\delta)+\sumop\slimits@_{t\notin\mathcal{T}^{\textnormal{par}}_{T+1}\cup\mathcal{T}^{\textnormal{int}}}r(x_{t},p_{t}).$ (5) $$

To bound the third term (i.e., the regret of the successive elimination phase), we decompose it as

$$ $\sumop\slimits@_{t\notin\mathcal{T}^{\textnormal{par}}_{T+1}\cup\mathcal{T}^{\textnormal{int}}}r(x_{t},p_{t}\epsilon)=\sumop\slimits@_{k\in\mathcal{K}}\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{SE}}_{s,k}}r(x_{t},p_{t})+\sumop\slimits@_{k^{\prime}\in\mathcal{K}}\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{SE}}_{b,k^{\prime}}}r(x_{t},p_{t}).$ $$

For $k\in\mathcal{K}$, let us partition $\mathcal{T}^{\textnormal{SE}}_{s,k}$ as follows. We denote by $T^{\textnormal{SE}}_{s,k}=|\mathcal{T}^{\textnormal{SE}}_{s,k}|$, and we define $t_{1},\ldots,t_{T^{\textnormal{SE}}_{s,k}}$ the rounds where $t\in\mathcal{T}^{\textnormal{SE}}_{s,k}$. More formally, we have $t_{1}<t_{2}<...<t_{T^{\textnormal{SE}}_{s,k}}$, and $\{t_{1},...,t_{T^{\textnormal{SE}}_{s,k}}\}=\mathcal{T}^{\textnormal{SE}}_{s,k}$. We define $\overline{a}=\left\lfloor-\log_{2}\left(2(50PL+28)\epsilon\right)\right\rfloor$, and for $a\in\llbracket 1,\overline{a}\rrbracket$, we define

$$ $\mathfrak{t}_{a}=2\log(1/\delta)\cdot\left(32P2^{a}\right)^{2}.$ $$

With these notation, we have

$$ $\displaystyle\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{SE}}_{s,k}}r(x_{t},p_{t})$ $\displaystyle=\sumop\slimits@_{i\leq\mathfrak{t}_{1}\land T^{\textnormal{SE}}_{s,k}}r(x_{t_{i}},p_{t_{i}})$ $\displaystyle+\sumop\slimits@_{a=1}^{\overline{a}-1}\,\,\sumop\slimits@_{\mathfrak{t}_{a}\land T^{\textnormal{SE}}_{s,k}<i\leq\mathfrak{t}_{a+1}\land T^{\textnormal{SE}}_{s,k}}r(x_{t_{i}},p_{t_{i}})+\sumop\slimits@_{(\mathfrak{t}_{\overline{a}}+1)\land T^{\textnormal{SE}}_{s,k}\leq i\leq T^{\textnormal{SE}}_{s,k}}r(x_{t_{i}},p_{t_{i}}).$ $$

For $1\leq a\leq\overline{a}$, if $\mathfrak{t}_{a}\leq i\leq T^{\textnormal{SE}}_{s,k}$, by definition of $\mathfrak{t}_{a}$, we have

$$ $(50PL+28)\epsilon\leq 16P\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t_{i}}}}\leq\frac{2^{-a}}{2},$ $$

and Lemma [10](#Thmlemma10) implies that, conditioned on the high-probability event $\mathcal{E}^{\textnormal{SBIP}}$,

$$ $r(x_{t_{i}},p_{t_{i}})\leq 2^{-a}.$ $$

Using the fact that $r(x_{t},p_{t})\leq 2P$, we obtain

$$ $\displaystyle\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{SE}}_{s,k}}r(x_{t},p_{t})$ $\displaystyle\leq 2P\mathfrak{t}_{1}+\sumop\slimits@_{a=1}^{\overline{a}-1}2^{-a}\left(\mathfrak{t}_{a+1}-\lceil\mathfrak{t}_{a}\rceil+1\right)+2^{-\overline{a}}\cdot T^{\textnormal{SE}}_{s,k}$ $\displaystyle\leq 2P\mathfrak{t}_{1}+\sumop\slimits@_{a=1}^{\overline{a}-1}2^{-a}\left(\mathfrak{t}_{a+1}-\mathfrak{t}_{a}+1\right)+2^{-\overline{a}}\cdot T^{\textnormal{SE}}_{s,k}.$ $$

Then,

$$ $\displaystyle\sumop\slimits@_{a=1}^{\overline{a}-1}2^{-a}\left(\mathfrak{t}_{a+1}-\mathfrak{t}_{a}\right)$ $\displaystyle=6\log(1/\delta)\cdot\left(32P\right)^{2}\sumop\slimits@_{a=1}^{\overline{a}-1}2^{a}$ $\displaystyle=6\log(1/\delta)\cdot\left(32P\right)^{2}2^{\overline{a}}$ $\displaystyle\leq\frac{3\log(1/\delta)\cdot\left(32P\right)^{2}}{(50PL+28)\epsilon}$ $$

Moreover, we have that

$$ $\displaystyle 2^{-\overline{a}}\cdot T^{\textnormal{SE}}_{s,k}\leq 2(50PL+28)\epsilon T^{\textnormal{SE}}_{s,k}.$ $$

Therefore,

$$ $\displaystyle\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{SE}}_{s,k}}r(x_{t},p_{t})\leq 4P\log(1/\delta)\cdot\left(128P\right)^{2}+\frac{3\log(1/\delta)\cdot\left(32P\right)^{2}}{(50PL+28)\epsilon}+1+2(50PL+28)\epsilon T^{\textnormal{SE}}_{s,k}.$ $$

We proceed similarly to bound $\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{SE}}_{b,k}}r(x_{t},p_{t})$, and we obtain that

$$ $\displaystyle\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{SE}}_{b,k}}r(x_{t},p_{t})\leq 4P\log(1/\delta)\cdot\left(128P\right)^{2}+\frac{3\log(1/\delta)\cdot\left(32P\right)^{2}}{(50PL+28)\epsilon}+1+2(50PL+28)\epsilon T^{\textnormal{SE}}_{b,k}.$ $$

Summing over $k\in\mathcal{K}$ and $k^{\prime}\in\mathcal{K}$, and using the fact that $\sumop\slimits@_{k\in\mathcal{K}}T^{\textnormal{SE}}_{s,k}+T^{\textnormal{SE}}_{b,k}\leq T$, we find

$$ $\displaystyle\sumop\slimits@_{t\notin\mathcal{T}^{\textnormal{par}}_{T+1}\cup\mathcal{T}^{\textnormal{int}}}r(x_{t},p_{t}\epsilon)$ $\displaystyle\leq 2|\mathcal{K}|\left(4P\log(1/\delta)\times\left(128P\right)^{2}+\frac{3\log(1/\delta)\times\left(32P\right)^{2}}{(50PL+28)\epsilon}+1\right)$ $\displaystyle+2(50PL+28)\epsilon T.$ (6) $$

Combining Equations ([5](#A4.E5)) and ([D.2](#A4.Ex75)), we find that, conditioned on the event $\mathcal{E}^{\textnormal{SBIP}}$,

$$ $\displaystyle R_{T}\leq$ $\displaystyle\frac{2Pd\log\left(\frac{T+d}{d}\right)\left(P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A\right)^{2}}{\epsilon^{2}}+\frac{18P^{3}\log(1/\delta)}{\epsilon^{2}}$ $\displaystyle+2|\mathcal{K}|\left(4P\log(1/\delta)\times\left(128P\right)^{2}+\frac{3\log(1/\delta)\times\left(32P\right)^{2}}{(50PL+28)\epsilon}+1\right)+2(50PL+28)\epsilon T.$ $$

By setting $\epsilon=(d^{2}\log(T)^{2}/T)^{\frac{1}{3}}$ and $\delta=T^{-3}$, and using the definition of $\mathcal{K}$, we find that there exists a constant $\mathaccent 0{\symlargesymbols}065{C}^{\prime}$ depending on $A$, $B$ $C$, and $L$ such that with probability $1-20T^{-2/3}$,

$$ $\displaystyle R_{T}\leq\mathaccent 0{\symlargesymbols}065{C}^{\prime}(d\log(T)T)^{\nicefrac{{2}}{{3}}}.$ $$

This concludes the proof of [Theorem 3](#Thmtheorem3).

###### Lemma 8 .

###### Lemma 9 .

###### Lemma 10 .

## Appendix E Proofs of auxiliary lemmas

### E.1 Proof of Lemma 1

See [1](#Thmlemma1)

###### Proof.

The proof relies on the characterization of the gain from trade given by Lemma 4.1 in []. Recall that, under Assumption [1](#Thmassumption1), we have $\xi_{t}^{s}\in[-C,C]$, and $\xi_{t}^{b}\in[-C,C]$. Then, denoting $f^{s}$ and $f^{b}$ the densities of $\xi_{t}^{s}$ and $\xi_{t}^{b}$, we have

$$ $\displaystyle\textnormal{EGFT}(x,p)$ $\displaystyle\hskip 14.22636pt=\intslop\ilimits@_{(s,b)\in[x^{\top}\theta^{s}-C,x^{\top}\theta^{s}+C]\times[x^{\top}\theta^{b}-C,x^{\top}\theta^{b}+C]}(b-s)\mathbb{I}\{s\leq p\leq b\}f^{b}(x^{\top}\theta^{b}-s)f^{s}(x^{\top}\theta^{s}-s)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b.$ $$

Let $\tilde{f}^{b}:b\mapsto f^{b}(x^{\top}\theta^{b}-s)$ and $\tilde{f}^{s}:s\mapsto f^{s}(x^{\top}\theta^{s}-s)$ be the densities of $s_{t}$ and $b_{t}$ conditionnally on $x_{t}=x$, and note that outside of $[x^{\top}\theta^{b}-C,x^{\top}\theta^{b}+C]\times[x^{\top}\theta^{s}-C,x^{\top}\theta^{s}+C]$, $\tilde{f}^{s}(s)\tilde{f}^{b}(b)=0$. With these notation, we have

$$ $\displaystyle\textnormal{EGFT}(x,p)$ $\displaystyle=\intslop\ilimits@_{(s,b)\in[-P,P]^{2}}(b-s)\mathbb{I}\{s\leq p\leq b\}\tilde{f}^{b}(b)\tilde{f}^{s}(s)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b$ $\displaystyle=\intslop\ilimits@_{(s,b)\in[-P,p]\times[p,P]}\left(\intslop\ilimits@_{-P}^{b}du-\intslop\ilimits@_{-P}^{s}du\right)\tilde{f}^{s}(s)\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b.$ $$

Thus,

$$ $\displaystyle\textnormal{EGFT}(x,p)=$ $\displaystyle\intslop\ilimits@_{[-P,P]}\left(\intslop\ilimits@_{(s,b)\in[-P,p]\times[p\lor u,P]}\tilde{f}^{s}(s)\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b\right)\mathop{}\!\mathrm{d}u$ $\displaystyle-\intslop\ilimits@_{[-P,p]}\left(\intslop\ilimits@_{(s,b)\in[u,p]\times[p,P]}\tilde{f}^{s}(s)\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b\right)\mathop{}\!\mathrm{d}u.$ $$

This yields

$$ $\displaystyle\textnormal{EGFT}(x,p)=$ $\displaystyle\intslop\ilimits@_{[-P,p]}\left(\intslop\ilimits@_{(s,b)\in[-P,p]\times[p,P]}\tilde{f}^{s}(s)\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b\right)\mathop{}\!\mathrm{d}u$ $\displaystyle+\intslop\ilimits@_{[p,P]}\left(\intslop\ilimits@_{(s,b)\in[-P,p]\times[u,P]}\tilde{f}^{s}(s)\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b\right)\mathop{}\!\mathrm{d}u$ $\displaystyle-\intslop\ilimits@_{[-P,p]}\left(\intslop\ilimits@_{(s,b)\in[u,p]\times[p,P]}\tilde{f}^{s}(s)\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b\right)\mathop{}\!\mathrm{d}u.$ $$

This, in turn, implies that

$$ $\displaystyle\textnormal{EGFT}(x,p)=$ $\displaystyle\intslop\ilimits@_{[-P,p]}\left(\intslop\ilimits@_{(s,b)\in[-P,u]\times[p,P]}\tilde{f}^{s}(s)\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b\right)\mathop{}\!\mathrm{d}u$ $\displaystyle+\intslop\ilimits@_{[p,P]}\left(\intslop\ilimits@_{(s,b)\in[-P,p]\times[u,P]}\tilde{f}^{s}(s)\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}b\right)\mathop{}\!\mathrm{d}u$ $\displaystyle=$ $\displaystyle\intslop\ilimits@_{[p,P]}\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}d\intslop\ilimits@_{[-P,p]}\intslop\ilimits@_{[-P,u]}\tilde{f}^{s}(s)\mathop{}\!\mathrm{d}s\mathop{}\!\mathrm{d}u$ $\displaystyle+\intslop\ilimits@_{[-P,p]}\tilde{f}^{s}(s)\mathop{}\!\mathrm{d}s\intslop\ilimits@_{[p,P]}\intslop\ilimits@_{[u,P]}\tilde{f}^{b}(b)\mathop{}\!\mathrm{d}b\mathop{}\!\mathrm{d}u.$ $$

By using the change in variables $\xi^{s}=s-x^{\top}\theta^{s}$, $u^{s}=u-x^{\top}\theta^{s}$, $\xi^{b}=b-x^{\top}\theta^{b}$, and $u^{b}=u-x^{\top}\theta^{b}$, and the definition of $\tilde{f}^{s}$ and $\tilde{f}^{b}$, we get

$$ $\displaystyle\textnormal{EGFT}(x,p)=$ $\displaystyle\intslop\ilimits@_{[p-x^{\top}\theta^{b},P-x^{\top}\theta^{b}]}f(\xi^{b})\mathop{}\!\mathrm{d}d\intslop\ilimits@_{[-P,p]}\intslop\ilimits@_{[-P-x^{\top}\theta^{s},u-x^{\top}\theta^{s}]}f(\xi^{s})\mathop{}\!\mathrm{d}\xi^{s}\mathop{}\!\mathrm{d}u$ $\displaystyle+\intslop\ilimits@_{[-P-x^{\top}\theta^{s},p-x^{\top}\theta^{s}]}f(\xi^{s})\mathop{}\!\mathrm{d}\xi^{s}\intslop\ilimits@_{[p,P]}\intslop\ilimits@_{[u-x^{\top}\theta^{b},P-x^{\top}\theta^{b}]}f(\xi^{b})\mathop{}\!\mathrm{d}\xi^{b}\mathop{}\!\mathrm{d}u$ $\displaystyle=$ $\displaystyle\intslop\ilimits@_{[p-x^{\top}\theta^{b},P-x^{\top}\theta^{b}]}f(\xi^{b})\mathop{}\!\mathrm{d}\xi^{b}\intslop\ilimits@_{[-P-x^{\top}\theta^{s},p-x^{\top}\theta^{s}]}\intslop\ilimits@_{[-P-x^{\top}\theta^{s},u^{s}]}f(\xi^{s})\mathop{}\!\mathrm{d}\xi^{s}\mathop{}\!\mathrm{d}u^{s}$ $\displaystyle+\intslop\ilimits@_{[-P-x^{\top}\theta^{s},p-x^{\top}\theta^{s}]}f(\xi^{s})\mathop{}\!\mathrm{d}\xi^{s}\intslop\ilimits@_{[p-x^{\top}\theta^{b},P-x^{\top}\theta^{b}]}\intslop\ilimits@_{[u^{b},P-x^{\top}\theta^{b}]}f(\xi^{b})\mathop{}\!\mathrm{d}\xi^{b}\mathop{}\!\mathrm{d}u^{b}.$ $$

Now, under Assumption [1](#Thmassumption1), $f^{b}$ and $f^{s}$ are null outside of $[-C,C]$. Moreover, $P-x^{\top}\theta^{b}\geq C$ and $-P-x^{\top}\theta^{s}\leq-C$. Thus,

$$ $\displaystyle\textnormal{EGFT}(x,p)=$ $\displaystyle\intslop\ilimits@_{[p-x^{\top}\theta^{b},C]}f(\xi^{b})\mathop{}\!\mathrm{d}d\intslop\ilimits@_{[-C,p-x^{\top}\theta^{s}]}\intslop\ilimits@_{[-C,u^{s}]}f(\xi^{s})\mathop{}\!\mathrm{d}\xi^{s}\mathop{}\!\mathrm{d}u^{s}$ $\displaystyle+\intslop\ilimits@_{[-C,p-x^{\top}\theta^{s}]}f(\xi^{s})\mathop{}\!\mathrm{d}\xi^{s}\intslop\ilimits@_{[p-x^{\top}\theta^{b},C]}\intslop\ilimits@_{[u^{b},C]}f(\xi^{b})\mathop{}\!\mathrm{d}\xi^{b}\mathop{}\!\mathrm{d}u^{b}$ $\displaystyle=$ $\displaystyle D^{b}(p-x^{\top}\theta^{b})\intslop\ilimits@_{-C}^{p-x^{\top}\theta^{s}}F^{s}(u^{s})\mathop{}\!\mathrm{d}u^{s}+F^{s}(p-x^{\top}\theta^{s})\intslop\ilimits@_{p-x^{\top}\theta^{b}}^{C}D^{b}(u^{b})\mathop{}\!\mathrm{d}u^{b}.$ $$

Using the definition of $\delta^{s}=p-x^{\top}\theta^{s}$ and $\delta^{b}=p-x^{\top}\theta^{b}$, we obtain the desired result.
∎

###### Proof.

### E.2 Proof of Lemma 4

See [4](#Thmlemma4)

###### Proof.

The elliptical potential Lemma (see, e.g., Proposition 1 in []) implies that almost surely,

$$ $\displaystyle\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{par}}_{T+1}}\Vert x_{t}\Vert_{\left(\sumop\slimits@_{l\in\mathcal{T}^{\textnormal{par}}_{t}}x_{l}x_{l}^{\top}+\textbf{I}_{d}\right)^{-1}}\leq\sqrt{|\mathcal{T}^{\textnormal{par}}_{T+1}|d\log\left(\frac{|\mathcal{T}^{\textnormal{par}}_{T+1}|+d}{d}\right)}.$ $$

Since for all $t\in\mathcal{T}^{\textnormal{par}}_{T+1}$, $\Vert x_{t}\Vert_{\left(\sumop\slimits@_{l\in\mathcal{T}^{\textnormal{par}}_{t}}x_{l}x_{l}^{\top}+\textbf{I}_{d}\right)^{-1}}\geq\mu$, this implies that

$$ $\displaystyle|\mathcal{T}^{\textnormal{par}}_{T+1}|\mu\leq\sqrt{|\mathcal{T}^{\textnormal{par}}_{T+1}|d\log\left(\frac{|\mathcal{T}^{\textnormal{par}}_{T+1}|+d}{d}\right)}.$ $$

Now, almost surely, $|\mathcal{T}^{\textnormal{par}}_{T+1}|\leq T$. This implies in particular that

$$ $\displaystyle|\mathcal{T}^{\textnormal{par}}_{T+1}|\leq\frac{d\log\left(\frac{T+d}{d}\right)}{\mu^{2}},$ $$

which concludes the proof.
∎

###### Proof.

### E.3 Proof of Lemma 5

See [5](#Thmlemma5)

###### Proof.

The Lemma is a consequence of the following two auxiliary results, bounding respectively the error for estimating the parameters $\theta^{s}$ and $\theta^{b}$, and the integrals $I$ and $J$.

###### Lemma 11 .

Let $\mathcal{E}_{1}$ be the event :

$$ $\displaystyle\mathcal{E}_{1}\coloneqq\left\{\forall t\notin\mathcal{T}^{\textnormal{par}}_{T+1},\quad\left|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b})\right|\leq\epsilon\quad\textnormal{ and }\quad\left|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s})\right|\leq\epsilon\right\}.$ $$

Then, for the choice $\mu=\epsilon\left(P\left(d\log\left(\frac{1+B^{2}T}{\delta}\right)\right)^{\nicefrac{{1}}{{2}}}+A\right)^{-1}$, we have $\mathbb{P}\left(\mathcal{E}_{1}\right)\geq 1-2\delta$.

The proof of the above lemma is deferred to [Section E.9](#A5.SS9).

###### Lemma 12 .

Let $\mathcal{E}_{2}$ be the event:

$$ $\displaystyle\mathcal{E}_{2}\coloneqq\left\{|\mathcal{T}^{\textnormal{int}}|<\textnormal{T}^{\textnormal{int}}\textnormal{ or }\forall k\in\mathcal{K}\,\,\ \left|\mathaccent 0{\symlargesymbols}062{I}^{k}-I\left(k\epsilon\right)\right|\leq 2\epsilon\textnormal{ and }\left|\mathaccent 0{\symlargesymbols}062{J}^{k}-J(k\epsilon)\right|\leq 2\epsilon\right\}\cap\mathcal{E}_{1}.$ $$

Then, for the choice $\mu=\epsilon\left(P\left(d\log\left(\frac{1+B^{2}T}{\delta}\right)\right)^{\nicefrac{{1}}{{2}}}+A\right)^{-1}$ and $\textnormal{T}^{\textnormal{int}}=8P^{2}\log(1/\delta)/\epsilon^{2}$, we have

$$ $\mathbb{P}\left(\mathcal{E}_{2}\right)\geq 1-2\delta-4\delta(2K+1).$ $$

The proof of the above lemma is deferred to [Section E.10](#A5.SS10).

Next, we control the error $|\mathaccent 0{\symlargesymbols}062{F}^{k}-F^{s}(k\epsilon)|$ uniformly for $k\in\mathcal{K}$. The results for $|\mathaccent 0{\symlargesymbols}062{D}^{k}-D^{b}(k\epsilon)|$ follow from similar arguments. To do so, we rely on the following well known result (for the sake of completeness, we provide a proof in [Section E.11](#A5.SS11)).

###### Lemma 13 .

Let $(y_{t})_{t\geq 1}$ be a sequence of random variables adapted for a filtration $\mathcal{F}_{t}$, such that $y_{t}-\mathbb{E}\left[y_{t}|\mathcal{F}_{t-1}\right]\in[m,M]$. Assume that for $t\in\mathbb{N}_{*}$, $\iota_{t}\in\{0,1\}$ is $\mathcal{F}_{t-1}$-measurable, and define $N_{t}\coloneqq\sumop\slimits@_{l\leq t}\iota_{l}$, and $\mathaccent 0{\symlargesymbols}062{\mu}_{t}\coloneqq N_{t}^{-1}\sumop\slimits@_{l\leq t}\iota_{l}(y_{l}-\mathbb{E}\left[y_{l}|\mathcal{F}_{l-1}\right])$ if $N_{t}\geq 1$. Then, for any $t\in\mathbb{N}_{*}$ and $\delta\in(0,1)$,

$$ $\mathbb{P}\left(N_{t}=0\,\,\textnormal{ or }\,\,|\mathaccent 0{\symlargesymbols}062{\mu}_{t}|\leq(M-m)\sqrt{\frac{\log(1/\delta)}{2N_{t}}}\right)\geq 1-2t\delta.$ $$

Moreover, for any $t>0$ and $\delta\in(0,1)$,

$$ $\mathbb{P}\left(N_{t}=t\,\,\textnormal{ and }\,\,|\mathaccent 0{\symlargesymbols}062{\mu}_{t}|\geq(M-m)\sqrt{\frac{\log(1/\delta)}{2N_{t}}}\right)\leq 1-2\delta.$ $$

For $t\leq T$, we define $\iota_{t}\coloneqq\mathbb{I}\left\{t\in\mathcal{T}^{F}_{k}\right\}$, $y_{t}\coloneqq\mathbb{I}\left\{s_{t}\leq p_{t}\right\}$, and we observe that for $\mathcal{F}_{t}=\sigma\left((x_{1},\ldots,x_{t+1},(\mathbb{I}\{s_{1}\leq p_{1}\},\mathbb{I}\{b_{1}\leq p_{1}\}),\ldots,(\mathbb{I}\{s_{t}\leq p_{t}\},\mathbb{I}\{b_{t}\leq p_{t}\})\right)$, $\iota_{t}$ is $\mathcal{F}_{t-1}$-measurable, and $y_{t}$ is $\mathcal{F}_{t}$ adapted. Moreover,

$$ $\displaystyle\iota_{t}\mathbb{E}\left[y_{t}\,\,|\,\,\mathcal{F}_{t-1}\right]$ $\displaystyle=\iota_{t}\mathbb{P}\left(x_{t}^{\top}\theta^{s}+\xi_{t}^{s}\leq x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon\right)$ $\displaystyle=\iota_{t}F^{s}\left(x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\right)+k\epsilon\right).$ $$

Using Lemma [13](#Thmlemma13), we find that with probability $1-2\delta$, either $|\mathcal{T}^{\textnormal{F}}_{k}|<\textnormal{T}^{\textnormal{FD}}$, or

$$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{F}^{k}_{t}-\frac{\sumop\slimits@_{s\leq t}\iota_{t}F^{s}\left(x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\right)+k\epsilon\right)}{\textnormal{T}^{\textnormal{FD}}}\right|\leq\sqrt{\frac{2\log(1/\delta)}{\textnormal{T}^{\textnormal{FD}}}}.$ $$

Moreover, on the event $\mathcal{E}_{1}$, for all $t\notin\mathcal{T}^{\textnormal{par}}$, $|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s})|\leq\epsilon$. Using the fact that $F^{s}$ is $L$-Lipschitz, we find that

$$ $\displaystyle\left|F^{s}\left(x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\right)+k\epsilon\right)-F^{s}\left(k\epsilon\right)\right|\leq L\epsilon.$ $$

Thus, with probability $1-2\delta$, either $|\mathcal{T}^{\textnormal{F}}_{k}|<\textnormal{T}^{\textnormal{FD}}$, or

$$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{F}^{k}_{t}-F^{s}(k\epsilon)\right|\leq\sqrt{\frac{2\log(1/\delta)}{\textnormal{T}^{\textnormal{FD}}}}+L\epsilon.$ $$

Using Lemma [11](#Thmlemma11) and [12](#Thmlemma12), along with a union bound over $k\in\mathcal{K}$ yields the desired result for the choice $\textnormal{T}^{\textnormal{FD}}=2\log(1/\delta)\epsilon^{-2}$.
∎

###### Proof.

###### Lemma 11 .

###### Lemma 12 .

###### Lemma 13 .

### E.4 Proof of Lemma 6

See [6](#Thmlemma6)

###### Proof.

The proof relies on the following result :

###### Lemma 14 .

On the event $\mathcal{E}^{\textnormal{ETC}}$, for all $(k,k^{\prime})\in\mathcal{A}_{t}$, and $p=x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon$, we have

$$ $\displaystyle\left|\textnormal{EGFT}(x_{t},p)-\left(\mathaccent 0{\symlargesymbols}062{I}^{k^{\prime}}\mathaccent 0{\symlargesymbols}062{F}^{k}+\mathaccent 0{\symlargesymbols}062{J}^{k}\mathaccent 0{\symlargesymbols}062{D}^{k^{\prime}}\right)\right|$ $\displaystyle\leq 6PL\epsilon+3\epsilon+2P\left(|\mathaccent 0{\symlargesymbols}062{\Delta}F|+|\mathaccent 0{\symlargesymbols}062{\Delta}D|\right)+|\mathaccent 0{\symlargesymbols}062{\Delta}I|+|\mathaccent 0{\symlargesymbols}062{\Delta}J|$ $$

where we define $\mathaccent 0{\symlargesymbols}062{\Delta}I=I(k^{\prime}\epsilon)-\mathaccent 0{\symlargesymbols}062{I}^{k^{\prime}}$, $\mathaccent 0{\symlargesymbols}062{\Delta}J=J(k\epsilon)-\mathaccent 0{\symlargesymbols}062{J}^{k}$, $\mathaccent 0{\symlargesymbols}062{\Delta}F=F(k\epsilon)-\mathaccent 0{\symlargesymbols}062{F}^{k}$, $\mathaccent 0{\symlargesymbols}062{\Delta}D=D(k^{\prime}\epsilon)-\mathaccent 0{\symlargesymbols}062{D}^{k^{\prime}}$.

The proof of this intermediate result is in [Section E.12](#A5.SS12).

To conclude the proof of Lemma [6](#Thmlemma6), it remains to bound the gaps $\mathaccent 0{\symlargesymbols}062{\Delta}F$, $\mathaccent 0{\symlargesymbols}062{\Delta}D$, $\mathaccent 0{\symlargesymbols}062{\Delta}I$, and $\mathaccent 0{\symlargesymbols}062{\Delta}J$ on the event $\mathcal{E}^{\textnormal{ETC}}$. By definition of the event $\mathcal{E}^{\textnormal{ETC}}$, on this event $\mathaccent 0{\symlargesymbols}062{\Delta}I\leq 2\epsilon$, $\mathaccent 0{\symlargesymbols}062{\Delta}D\leq(L+1)\epsilon$, $\mathaccent 0{\symlargesymbols}062{\Delta}J\leq 2\epsilon$ and $\mathaccent 0{\symlargesymbols}062{\Delta}F\leq(L+1)\epsilon$. Thus, on the event $\mathcal{E}^{\textnormal{ETC}}$,

$$ $\displaystyle\left|\textnormal{EGFT}(x_{t},p)-\left(\mathaccent 0{\symlargesymbols}062{I}^{k^{\prime}}\mathaccent 0{\symlargesymbols}062{F}^{k}+\mathaccent 0{\symlargesymbols}062{J}^{k}\mathaccent 0{\symlargesymbols}062{D}^{k^{\prime}}\right)\right|$ $\displaystyle\leq 6PL\epsilon+3\epsilon+4P(L+1)\epsilon+4\epsilon.$ $$

This concludes the proof.
∎

###### Proof.

###### Lemma 14 .

### E.5 Proof of Lemma 7

See [7](#Thmlemma7)

###### Proof.

By definition of $\mathcal{A}_{t}$,

$$ $\sup_{p\in[-P,P]}\textnormal{EGFT}(x_{t},p)\geq\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k_{t}^{*}\epsilon).$ $$

Since the mapping $p\mapsto\textnormal{EGFT}(x,p)$ is continuous, we can define

$$ $p^{*}_{t}\in\operatorname*{arg\,max}_{p}\textnormal{EGFT}(x_{t},p),\quad\tilde{k}_{t}=\left\lfloor\frac{p^{*}_{t}-x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}}{\epsilon}\right\rfloor,\quad\text{and }\,\,\tilde{k^{\prime}}_{t}=\left\lfloor\frac{x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}\right)+\tilde{k}_{t}}{\epsilon}\right\rfloor.$ $$

We now show that $(\tilde{k}_{t},\tilde{k}^{\prime}_{t})\in\mathcal{A}_{t}$. By Lemma [1](#Thmlemma1), we have that $p^{*}_{t}-x_{t}^{\top}\theta^{s}\geq-C$, and $p^{*}_{t}-x_{t}^{\top}\theta^{b}\leq C$ (otherwise $\textnormal{EGFT}(x_{t},p^{*}_{t})=0$). This implies that $p^{*}_{t}-x_{t}^{\top}\theta^{s}\in[-2P,2P]$, and similarly that $p^{*}_{t}-x_{t}^{\top}\theta^{b}\in[-2P,2P]$.

On the one hand, on the event $\mathcal{E}^{\textnormal{ETC}}$, $\left|x_{t}^{\top}\left(\theta^{s}-\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}\right)\right|\leq\epsilon$, so $p^{*}_{t}-x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}\in[-2P-\epsilon,2P+\epsilon]$. Thus, $\tilde{k}_{t}\in\mathcal{K}$.
On the other hand,

$$ $x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}\right)+\tilde{k}_{t}\epsilon=\left(x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+\tilde{k}_{t}\epsilon-p_{t}^{*}\right)+(p^{*}_{t}-x_{t}^{\top}\theta^{b})+x_{t}^{\top}\left(\theta^{b}-\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}\right).$ $$

Then, on the event $\mathcal{E}^{\textnormal{ETC}}$,

$$ $x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}\right)+\tilde{k}_{t}\epsilon\in[-2P-2\epsilon,2P+2\epsilon],$ $$

, so $k_{t}^{\prime}\in[-2P-3\epsilon,2P+3\epsilon]$. Therefore, $\tilde{k}^{\prime}_{t}\in\mathcal{K}$. This implies that $(\tilde{k}_{t},\tilde{k}_{t}^{\prime})\in\mathcal{A}_{t}$, so

$$ $\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k^{*}_{t}\epsilon)\geq\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+\tilde{k}_{t}\epsilon).$ $$

Finally, Lemma [1](#Thmlemma1) and Assumption [2](#Thmassumption2) imply that the function $p\mapsto\textnormal{EGFT}(x_{t},p)$ is $2LP$-Lipschitz continuous. This, in turn, implies that

$$ $\textnormal{EGFT}(x_{t},p^{*}_{t})-\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+\tilde{k}_{t}\epsilon)\leq 2LP\epsilon.$ $$

This proves the statement.
∎

###### Proof.

### E.6 Proof of Lemma 8

See [8](#Thmlemma8)

###### Proof.

The proof relies on Lemma [11](#Thmlemma11) and [12](#Thmlemma12). On top of these results, we have to control the error $|\mathaccent 0{\symlargesymbols}062{F}^{k}_{t}-F^{s}(k\epsilon)|$ uniformly for $k\in\mathcal{K}$. To do so, we rely on Lemma [13](#Thmlemma13). For $t\leq T$, we define $\iota_{t}=\mathbb{I}\left\{t\notin\mathcal{T}^{\textnormal{int}}\cup\mathcal{T}^{\textnormal{par}}_{T+1}\text{ and }k_{t}=k\right\}$, $y_{t}=\mathbb{I}\left\{s_{t}\leq p_{t}\right\}$, and we note that for $\mathcal{F}_{t}=\sigma\left((x_{1},\ldots,x_{t+1},(\mathbb{I}\{s_{1}\leq p_{1}\},\mathbb{I}\{b_{1}\leq p_{1}\}),\ldots,(\mathbb{I}\{s_{t}\leq p_{t}\},\mathbb{I}\{b_{t}\leq p_{t}\})\right)$, $\iota_{t}$ is $\mathcal{F}_{t-1}$-measurable, and $y_{t}$ is $\mathcal{F}_{t}$ adapted. Moreover,

$$ $\displaystyle\iota_{t}\mathbb{E}\left[y_{t}\,|\,\mathcal{F}_{t-1}\right]$ $\displaystyle=\iota_{t}\mathbb{P}\left(x_{t}^{\top}\theta^{s}+\xi_{t}^{s}\leq x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon\right)$ $\displaystyle=\iota_{t}F^{s}\left(x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\right)+k\epsilon\right).$ $$

Using Lemma [13](#Thmlemma13), we find that with probability $1-2\delta t$, either $N^{s,k}_{t}=0$ or

$$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{F}^{k}_{t}-\frac{\sumop\slimits@_{s\leq t}\iota_{t}F^{s}\left(x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\right)+k\epsilon\right)}{N^{s,k}_{t}}\right|\leq\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}$ $$

(where we recall that we adopt the convention $1/0=\infty$). Moreover, on the event $\mathcal{E}_{1}$, for all $t\notin\mathcal{T}^{\textnormal{par}}$, $|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s})|\leq\epsilon$. Since $F^{s}$ is $L$-Lipschitz, this implies

$$ $\displaystyle|F^{s}\left(x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\right)+k\epsilon\right)-F^{s}\left(k\epsilon\right)|\leq L\epsilon.$ $$

Thus, with probability $1-2\delta t$,

$$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{F}^{k}_{t}-F^{s}(k\epsilon)\right|\leq\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}+L\epsilon.$ $$

Using a union bound over $k\in\mathcal{K}$ and $t\notin\mathcal{T}^{\textnormal{int}}\cup\mathcal{T}^{\textnormal{par}}_{T+1}$ yields the desired result.

Next, we can bound $|\mathaccent 0{\symlargesymbols}062{D}^{k}_{t}-D^{b}(k\epsilon)|$ using similar arguments. In particular, we define $\iota_{t}=\mathbb{I}\left\{t\notin\mathcal{T}^{\textnormal{int}}\cup\mathcal{T}^{\textnormal{par}}_{T+1}\text{ and }k^{\prime}_{t}=k\right\}$, $y_{t}=\mathbb{I}\left\{b_{t}\geq p_{t}\right\}$ and note that

$$ $\displaystyle\iota_{t}\mathbb{E}\left[y_{t}\,|\,\mathcal{F}_{t-1}\right]$ $\displaystyle=\iota_{t}\mathbb{P}\left(x_{t}^{\top}\theta^{b}+\xi_{t}^{b}\geq x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k_{t}\epsilon\ \Big{|}\ \mathcal{F}_{t-1}\right)$ $\displaystyle=\iota_{t}D^{b}\left(x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b}\right)+k\epsilon+\epsilon\left(\frac{x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}+k_{t}\epsilon}{\epsilon}-k\right)\right).$ $$

By definition of $\mathcal{A}_{t}$, we have that if $\iota_{t}=1$, then $\left|\frac{x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}+k_{t}\epsilon}{\epsilon}-k\right|\leq 1$. Using the Lipschitz continuity of $D^{b}$, this implies that, conditioned on the event $\mathcal{E}_{1}$,

$$ $\displaystyle\iota_{t}\left|\mathbb{E}\left[y_{t}\,|\,\mathcal{F}_{t-1}\right]-D^{b}(k\epsilon)\right|\leq 2L\epsilon.$ $$

The rest of the proof follows similarly.
∎

###### Proof.

### E.7 Proof of Lemma 9

See [9](#Thmlemma9)

###### Proof.

Let us prove the first part of Lemma [9](#Thmlemma9).
By Lemma [14](#Thmlemma14), and by definition of the event $\mathcal{E}^{\textnormal{SBIP}}$, we have for all $(k,k^{\prime})\in\mathcal{A}_{t}$, and all $t\notin\mathcal{T}^{\textnormal{par}}_{T+1}\cup\mathcal{T}^{\textnormal{int}}$,

$$ $\displaystyle\left|\textnormal{EGFT}(x_{t},p)-\left(\mathaccent 0{\symlargesymbols}062{I}^{k^{\prime}}\mathaccent 0{\symlargesymbols}062{F}^{k}+\mathaccent 0{\symlargesymbols}062{J}^{k}\mathaccent 0{\symlargesymbols}062{D}^{k^{\prime}}\right)\right|$ $\displaystyle\leq 6PL\epsilon+3\epsilon+2P\left(\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}+\sqrt{\frac{2\log(1/\delta)}{N^{b,k^{\prime}}_{t}}}+3L\epsilon\right)+4\epsilon$ $\displaystyle\leq(12PL+7)\epsilon+2P\left(\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}+\sqrt{\frac{2\log(1/\delta)}{N^{b,k^{\prime}}_{t}}}\right).$ $$

This concludes the first part of Lemma [9](#Thmlemma9). The second claim follows immediately by noticing that by definition, $(k_{t}^{*},k_{t}^{\prime*})\in\mathcal{A}_{t}$, and that, for all $(k,k^{\prime})\in\mathcal{A}_{t}$,

$$ $\displaystyle{\textnormal{LCB}}_{t}(k,k^{\prime})\leq\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k\epsilon)\leq\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{s}+k_{t}^{*}\epsilon)\leq{\textnormal{UCB}}_{t}(k_{t}^{*},k_{t}^{\prime*}).$ $$

This concludes the proof.
∎

###### Proof.

### E.8 Proof of Lemma 10

See [10](#Thmlemma10)

###### Proof.

Assume that $t\in\mathcal{T}^{\textnormal{SE}}_{s,k}$. Then, our choice of $k_{t}$ together with Lemma [9](#Thmlemma9) ensures that, conditioned on the event $\mathcal{E}^{\textnormal{SBIP}}$,

$$ ${\textnormal{UCB}}_{t}(k_{t},k^{\prime}_{t})\geq{\textnormal{LCB}}_{t}(k^{*}_{t},k^{\prime*}_{t}).$ $$

This implies that

$$ ${\textnormal{LCB}}_{t}(k_{t},k^{\prime}_{t})+\left({\textnormal{UCB}}_{t}(k_{t},k^{\prime}_{t})-{\textnormal{LCB}}_{t}(k_{t},k^{\prime}_{t})\right)\geq\\ {\textnormal{UCB}}_{t}(k^{*}_{t},k^{\prime*}_{t})+\left({\textnormal{LCB}}_{t}(k^{*}_{t},k^{\prime*}_{t})-{\textnormal{UCB}}_{t}(k^{*}_{t},k^{\prime*}_{t})\right).$ $$

Using again Lemma [9](#Thmlemma9), this implies that

$$ $\displaystyle\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}+k_{t}\epsilon)$ $\displaystyle+\left({\textnormal{UCB}}_{t}(k_{t},k^{\prime}_{t})-{\textnormal{LCB}}_{t}(k_{t},k^{\prime}_{t})\right)+\left({\textnormal{UCB}}_{t}(k^{*}_{t},k^{\prime*}_{t})-{\textnormal{LCB}}_{t}(k^{*}_{t},k^{\prime*}_{t})\right)$ $\displaystyle\geq\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}+k^{*}_{t}\epsilon).$ $$

Thus,

$$ $\displaystyle\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}+k^{*}_{t}\epsilon)$ $\displaystyle-\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}+k_{t}\epsilon)$ $\displaystyle\leq\left({\textnormal{UCB}}_{t}(k_{t},k^{\prime}_{t})-{\textnormal{LCB}}_{t}(k_{t},k^{\prime}_{t})\right)+\left({\textnormal{UCB}}_{t}(k^{*}_{t},k^{\prime*}_{t})-{\textnormal{LCB}}_{t}(k^{*}_{t},k^{\prime*}_{t})\right).$ $$

Then, conditioned on the event $\mathcal{E}^{\textnormal{SBIP}}$,

$$ $\displaystyle{\textnormal{UCB}}_{t}(k_{t},k^{\prime}_{t})-{\textnormal{LCB}}_{t}(k_{t},k^{\prime}_{t})$ $\displaystyle\leq 2(12PL+7)\epsilon+4P\left(\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}+\sqrt{\frac{2\log(1/\delta)}{N^{b,k^{\prime}}_{t}}}\right).$ $$

Since $t\in\mathcal{T}^{\textnormal{SE}}_{s,k}$, we know that $N^{b,k^{\prime}_{t}}_{t}\geq N^{s,k_{t}}_{t}$. Then, we have that

$$ $\displaystyle{\textnormal{UCB}}_{t}(k_{t},k^{\prime}_{t})-{\textnormal{LCB}}_{t}(k_{t},k^{\prime}_{t})$ $\displaystyle\leq 2(12PL+7)\epsilon+8P\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}.$ $$

Similarly, since $t\in\mathcal{T}^{\textnormal{SE}}_{s,k}$, we have that $N^{b,k^{\prime*}_{t}}_{t}\geq N^{s,k_{t}}_{t}$, and $N^{s,k^{*}_{t}}_{t}\geq N^{s,k_{t}}_{t}$, so we also have

$$ $\displaystyle{\textnormal{UCB}}_{t}(k^{*}_{t},k^{\prime*}_{t})-{\textnormal{LCB}}_{t}(k^{*}_{t},k^{\prime*}_{t})$ $\displaystyle\leq 2(12PL+7)\epsilon+8P\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}.$ $$

Thus,

$$ $\displaystyle\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}+k^{*}_{t}\epsilon)-\textnormal{EGFT}(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}+k_{t}\epsilon)\leq 4(12PL+7)\epsilon+16P\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}.$ $$

By Lemma [7](#Thmlemma7), this implies

$$ $\displaystyle r(x_{t},x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}+k_{t}\epsilon)\leq(50PL+28)\epsilon+16P\sqrt{\frac{2\log(1/\delta)}{N^{s,k}_{t}}}.$ $$

The proof of the second claim follows from similar arguments.
∎

###### Proof.

### E.9 Proof of Lemma 11

See [11](#Thmlemma11)

###### Proof.

Let us prove the bound $|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s})|\leq\epsilon$ with high probability; the bound on $|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b})|$ will follow from similar arguments.

We introduce the variables

$$ $\tilde{x}_{t}\coloneqq x_{t}\mathbb{I}\left\{t\in\mathcal{T}^{\textnormal{par}}_{t+1}\right\}\quad\text{and}\quad\tilde{y}_{t}\coloneqq 2P\,\mathbb{I}\left\{t\in\mathcal{T}^{\textnormal{par}}_{t+1}\right\}\left(\mathbb{I}\left\{p_{t}\leq s_{t}\right\}-\frac{1}{2}\right)$ $$

and the $\sigma$-algebra $\mathcal{F}_{t}=\sigma\left((x_{1},\ldots,x_{t+1},(\mathbb{I}\{s_{1}\leq p_{1}\},\mathbb{I}\{b_{1}\leq p_{1}\}),\ldots,(\mathbb{I}\{s_{t}\leq p_{t}\},\mathbb{I}\{b_{t}\leq p_{t}\})\right).$ With these notation, we have that $\tilde{x_{t}}$ and $\{t\in\mathcal{T}^{\textnormal{par}}_{t+1}\}$ are $\mathcal{F}_{t}$-measurable. Moreover,

$$ $\displaystyle\mathbb{E}\left[\tilde{y}_{t}|\mathcal{F}_{t-1}\right]$ $\displaystyle=\mathbb{I}\left\{t\in\mathcal{T}^{\textnormal{par}}_{t+1}\right\}\cdot\left(2P\intslop\ilimits@_{-P}^{P}\mathbb{P}\left[u\leq s_{t}|\mathcal{F}_{t-1}\right]\frac{\mathop{}\!\mathrm{d}u}{2P}-P\right)$ $\displaystyle=\mathbb{I}\left\{t\in\mathcal{T}^{\textnormal{par}}_{t+1}\right\}\cdot\left(\intslop\ilimits@_{-P}^{P}\intslop\ilimits@_{-C}^{C}\mathbb{I}\left\{u\leq x_{t}^{\top}\theta^{s}+\xi\right\}f^{s}(\xi)\mathop{}\!\mathrm{d}\xi\mathop{}\!\mathrm{d}u-P\right)$ $\displaystyle=\mathbb{I}\left\{t\in\mathcal{T}^{\textnormal{par}}_{t+1}\right\}\cdot\left(\intslop\ilimits@_{-C}^{C}\intslop\ilimits@_{-P}^{\xi+x_{t}^{\top}\theta^{s}}\mathop{}\!\mathrm{d}uf^{s}(\xi)\mathop{}\!\mathrm{d}\xi-P\right)$ $\displaystyle=\mathbb{I}\left\{t\in\mathcal{T}^{\textnormal{par}}_{t+1}\right\}\cdot\left(x_{t}^{\top}\theta^{s}+\intslop\ilimits@_{-C}^{C}\xi f^{s}(\xi)\mathop{}\!\mathrm{d}\xi\right)$ $\displaystyle=\mathbb{I}\left\{t\in\mathcal{T}^{\textnormal{par}}_{t+1}\right\}x_{t}^{\top}\theta^{s}$ $$

where in the last equality we used that $\intslop\ilimits@_{-C}^{C}\xi f^{s}(\xi)\mathop{}\!\mathrm{d}\xi=\mathbb{E}\left[\xi^{s}_{t}\right]=0$. Thus, conditionally on $\mathcal{F}_{t-1}$, $\tilde{y}_{t}-\tilde{x}_{t}^{\top}\theta^{s}$ is centered and it belongs to $[-P,P]$, which implies that it is $P$-subgaussian. Now, for all $t\in\{1,\dots,T\}$, we have

$$ $\displaystyle\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}$ $\displaystyle=2P\left(\sumop\slimits@_{l\in\mathcal{T}^{\textnormal{par}}_{T+1}}x_{l}x_{l}^{\top}+\textbf{I}_{d}\right)^{-1}\sumop\slimits@_{s\in\mathcal{T}^{\textnormal{par}}_{T+1}}\left(\mathbb{I}\left\{p_{t}\geq s_{t}\right\}-\frac{1}{2}\right)x_{l}$ $\displaystyle=\left(\sumop\slimits@_{l<t}\tilde{x}_{l}\tilde{x}_{l}^{\top}+\textbf{I}_{d}\right)^{-1}\sumop\slimits@_{l<t}\tilde{y}_{l}\tilde{x}_{l}.$ $$

Using the fact that, for all $t\leq 1$, $\Vert\tilde{x}_{t}\Vert\leq B$ and $\Vert\theta^{s}\Vert\leq A$, and applying Theorem 2 by Abbasi-Yadkori et al. [], we find that for all $t\geq 0$, with probability $1-\delta$,

$$ $\Vert\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\Vert_{\sumop\slimits@_{s<t}\tilde{x}_{l}\tilde{x}_{l}^{\top}+\textbf{I}_{d}}\leq P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A.$ $$

Note that our definitions of $\tilde{x}_{t}$ and $\tilde{y}_{t}$ ensure that

$$ $\Vert\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\Vert_{\sumop\slimits@_{s\in\mathcal{T}^{\textnormal{par}}_{T+1}}x_{l}x_{l}^{\top}+\textbf{I}_{d}}=\Vert\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\Vert_{\sumop\slimits@_{s<t}\tilde{x}_{l}\tilde{x}_{l}^{\top}+\textbf{I}_{d}}.$ $$

Moreover, for all $t$,

$$ $|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s})|\leq\Vert x_{t}^{\top}\Vert_{\left(\sumop\slimits@_{s\in\mathcal{T}^{\textnormal{par}}_{T+1}}x_{l}x_{l}^{\top}+\textbf{I}_{d}\right)^{-1}}\,\,\Vert\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}\Vert_{\left(\sumop\slimits@_{s\in\mathcal{T}^{\textnormal{par}}_{T+1}}x_{l}x_{l}^{\top}+\textbf{I}_{d}\right)}.$ $$

In particular, if $t\notin\mathcal{T}^{\textnormal{par}}_{T+1}$, $\Vert x_{t}^{\top}\Vert_{\left(\sumop\slimits@_{s\in\mathcal{T}^{\textnormal{par}}_{T+1}}x_{l}x_{l}^{\top}+\textbf{I}_{d}\right)^{-1}}\leq\mu$, so with probability $1-\delta$,

$$ $|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s})|\leq\mu\left(P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A\right).$ $$

For the choice $\mu=\epsilon\left(P\sqrt{d\log\left(\frac{1+B^{2}T}{\delta}\right)}+A\right)^{-1}$, this implies that

$$ $|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s})|\leq\epsilon,$ $$

which concludes the proof.
∎

###### Proof.

### E.10 Proof of Lemma 12

See [12](#Thmlemma12)

###### Proof.

We control the error $\left|\mathaccent 0{\symlargesymbols}062{I}^{k}-I\left(k\epsilon\right)\right|$ uniformly for $k\leq K$; the result for $\left|\mathaccent 0{\symlargesymbols}062{J}^{k}-J(k\epsilon)\right|$ can be proved analogously.

For $k\leq K$, and $t\leq T$, let us define $\iota_{t}=\mathbb{I}\left\{t\in\mathcal{T}^{\textnormal{int}}\right\}$, $y_{t}=2P\mathbb{I}\left\{k\epsilon+x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{b}\leq p_{l}\leq b_{t}\right\}$ and note that for $\mathcal{F}_{t}=\sigma\left((x_{1},\ldots,x_{t+1},(\mathbb{I}\{s_{1}\leq p_{1}\},\mathbb{I}\{b_{1}\leq p_{1}\}),\ldots,(\mathbb{I}\{s_{t}\leq p_{t}\},\mathbb{I}\{b_{t}\leq p_{t}\})\right)$, $\iota_{t}$ is $\mathcal{F}_{t-1}$-measurable, and $y_{t}$ is $\mathcal{F}_{t}$-adapted. Moreover,

$$ $\displaystyle\mathbb{E}\left[y_{t}|\mathcal{F}_{t-1}\right]$ $\displaystyle=2P\,\mathbb{P}\left[k\epsilon+x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}_{t}^{b}\leq p_{t}\leq b_{t}\,|\,\mathcal{F}_{t-1}\right]$ $\displaystyle=2P\intslop\ilimits@_{k\epsilon+x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}}^{P}\intslop\ilimits@_{-C}^{C}\mathbb{I}\left\{x_{t}^{\top}\theta^{b}+\xi\geq u\right\}f^{b}(\xi)\mathop{}\!\mathrm{d}\xi\frac{\mathop{}\!\mathrm{d}u}{2P}$ $\displaystyle=\intslop\ilimits@_{k\epsilon+x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}}^{P}D^{b}\left(u-x_{t}^{\top}\theta^{b}\right)\mathop{}\!\mathrm{d}u.$ $$

Using the change in variables $u^{\prime}=u-x_{t}^{\top}\theta^{b}$, this implies that

$$ $\displaystyle\mathbb{E}\left[y_{t}|\mathcal{F}_{t-1}\right]$ $\displaystyle=\intslop\ilimits@_{k\epsilon+x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-x_{t}^{\top}\theta^{b}}^{P-x_{t}^{\top}\theta^{b}}D^{b}\left(u^{\prime}\right)\mathop{}\!\mathrm{d}u^{\prime}.$ $$

Moreover, under Assumptions [1](#Thmassumption1) and [2](#Thmassumption2), $P-x_{t}^{\top}\theta^{b}\geq C$ and, for $u^{\prime}\in[C,P-x_{t}^{\top}\theta^{b}]$, $D^{b}(u^{\prime})=0$. Thus,

$$ $\displaystyle\mathbb{E}\left[y_{t}|\mathcal{F}_{t-1}\right]$ $\displaystyle=\intslop\ilimits@_{k\epsilon+x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-x_{t}^{\top}\theta^{b}}^{C}D^{b}\left(u^{\prime}\right)\mathop{}\!\mathrm{d}u^{\prime}$ $\displaystyle=I(k\epsilon+x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-x_{t}^{\top}\theta^{b}).$ $$

Finally, note that $y_{t}-\mathbb{E}\left[y_{t}|\mathcal{F}_{t-1}\right]$ is in $[-2P,2P]$. Then, using Lemma [13](#Thmlemma13), we find that

$$ $\displaystyle\mathbb{P}\left(|\mathcal{T}^{\textnormal{int}}|=\textnormal{T}^{\textnormal{int}}\text{ and }\left|\mathaccent 0{\symlargesymbols}062{I}^{k}-\frac{\sumop\slimits@_{t\in\mathcal{T}^{\textnormal{int}}}I\left(k\epsilon+x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b}\right)\right)}{\textnormal{T}^{\textnormal{int}}}\right|\geq 4P\sqrt{\frac{\log(1/\delta)}{2\textnormal{T}^{\textnormal{int}}}}\right)\leq 2\delta.$ $$

To conclude our proof, note that on the event $\mathcal{E}_{1}$, for all $t\in\mathcal{T}^{\textnormal{int}}$, $|x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b})|\leq\epsilon$, so with probability $1-2\delta$, either $|\mathcal{T}^{\textnormal{int}}|<\textnormal{T}^{\textnormal{int}}$ or

$$ $\displaystyle\left|I\left(k\epsilon+x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b}\right)\right)-I(k\epsilon)\right|$ $\displaystyle=\left|\intslop\ilimits@_{k\epsilon}^{k\epsilon+x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b}\right)}\left(1-F^{b}(\lambda)\right)d\lambda\right|$ $\displaystyle\leq\left|\intslop\ilimits@_{k\epsilon}^{k\epsilon+x_{t}^{\top}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b}\right)}d\lambda\right|$ $\displaystyle\leq\left|x_{t}\left(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b}\right)\right|$ $\displaystyle\leq\epsilon.$ $$

Using the same reasoning to control the error in estimating $J$, taking a union bound for $k\in\mathcal{K}$, and using Lemma [11](#Thmlemma11), we find that on an event $\mathcal{E}_{2}\subset\mathcal{E}_{1}$ of probability larger than $1-2\delta-4\delta(2K+1)$, either $|\mathcal{T}^{\textnormal{int}}|<\textnormal{T}^{\textnormal{int}}$ or

$$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{I}^{k}-I(k\epsilon)\right|\leq 4P\sqrt{\frac{\log(1/\delta)}{2\textnormal{T}^{\textnormal{int}}}}+\epsilon$ $$

and

$$ $\displaystyle\left|\mathaccent 0{\symlargesymbols}062{J}^{k}-J(k\epsilon)\right|\leq 4P\sqrt{\frac{\log(1/\delta)}{2\textnormal{T}^{\textnormal{int}}}}+\epsilon$ $$

simultaneously for all $k\in\mathcal{K}$. For the choice $\textnormal{T}^{\textnormal{int}}=8P^{2}\log(1/\delta)/\epsilon^{2}$, we obtain the desired result.
∎

###### Proof.

### E.11 Proof of Lemma 13

See [13](#Thmlemma13)

###### Proof.

Let us define $Z_{t}\coloneqq\sumop\slimits@_{l\leq t}\iota_{l}(y_{l}-\mathbb{E}\left[y_{l}|\mathcal{F}_{l-1}\right])$, and for all $x\in\mathbb{R}$ let $M_{t}\coloneqq\exp\left\{x\,Z_{t}-\frac{1}{8}x^{2}(M-m)^{2}N_{t}\right\}$. We begin by showing that $M_{t}$ is a super-martingale. Indeed, we have that

$$ $\displaystyle\mathbb{E}\left[\exp\{x\,\iota_{t}(y_{t}-\mathbb{E}\left[y_{t}|\mathcal{F}_{t-1}\right])\}\,\,\Big{|}\,\,\mathcal{F}_{t-1}\right]$ $\displaystyle=\mathbb{E}\left[\iota_{t}\exp\{x(y_{t}-\mathbb{E}\left[y_{t}|\mathcal{F}_{t-1}\right])\}+(1-\iota_{t})\,\,\Big{|}\,\,\mathcal{F}_{t-1}\right]$ $\displaystyle\leq\iota_{t}\exp\left\{\frac{x^{2}(M-m)^{2}}{8}\right\}+(1-\iota_{t})$ $\displaystyle\leq\exp\left\{\frac{x^{2}(M-m)^{2}\iota_{t}}{8}\right\},$ $$

where we use the fact that $(y_{t}-\mathbb{E}\left[y_{t}\,|\,\mathcal{F}_{t-1}\right])$ is bounded in $[m,M]$ together with the conditional version of Hoeffding’s Lemma. Noticing that

$$ $\displaystyle M_{t}=M_{t-1}\exp\left\{x\,\iota_{t}(y_{t}-\mathbb{E}\left[y_{t}|\mathcal{F}_{t-1}\right])-\frac{x^{2}(M-m)^{2}\iota_{t}}{8}\right\},$ $$

this proves that $M_{t}$ is a super-martingale, and so $\mathbb{E}\left[M_{t}\right]\leq\mathbb{E}\left[M_{0}\right]=1$.

Now, for all $\epsilon>0$ and all $l\in\mathbb{N}$, and all $x>0$, by a Markov-Chernoff argument,

$$ $\displaystyle\mathbb{P}\left(Z_{t}\geq\epsilon\textnormal{ and }N_{t}=l\right)$ $\displaystyle=\mathbb{P}\left(\mathbb{I}\left\{N_{t}=l\right\}e^{xZ_{t}}\geq e^{\epsilon x}\right)$ $\displaystyle\leq e^{-\epsilon x}\mathbb{E}\left(\mathbb{I}\left\{N_{t}=l\right\}\cdot e^{xZ_{t}}\right)$ $\displaystyle=e^{-\epsilon x+\frac{x^{2}(M-m)^{2}l}{8}}\mathbb{E}\left(\mathbb{I}\left\{N_{t}=l\right\}\cdot e^{xZ_{t}-\frac{x^{2}(M-m)^{2}l}{8}}\right).$ $$

Using the previous result, we have that

$$ $\displaystyle\mathbb{E}\left(\mathbb{I}\left\{N_{t}=l\right\}\cdot e^{xZ_{t}-\frac{x^{2}(M-m)^{2}l}{8}}\right)$ $\displaystyle=\mathbb{E}\left(\mathbb{I}\left\{N_{t}=l\right\}\cdot e^{xZ_{t}-\frac{x^{2}(M-m)^{2}N_{t}}{8}}\right)$ $\displaystyle\leq\mathbb{E}\left(e^{xZ_{t}-\frac{x^{2}(M-m)^{2}N_{t}}{8}}\right)$ $\displaystyle=\mathbb{E}(M_{t})$ $\displaystyle\leq\mathbb{E}(M_{0})=1.$ $$

This yields

$$ $\displaystyle\mathbb{P}\left(Z_{t}\geq\epsilon\textnormal{ and }N_{t}=l\right)$ $\displaystyle\leq e^{-\epsilon x+\frac{x^{2}(M-m)^{2}l}{8}}.$ $$

In particular, for $\epsilon=(M-m)\sqrt{\frac{l\cdot\log(1/\delta)}{2}}$ and $x=\frac{4\epsilon}{l(M-m)^{2}}$,

$$ $\displaystyle\mathbb{P}\left(Z_{t}\geq(M-m)\sqrt{\frac{l\cdot\log(1/\delta)}{2}}\textnormal{ and }N_{t}=l\right)$ $\displaystyle\leq\delta.$ $$

This proves the first part of the Lemma. Summing over the values of $l$ from $1$ to $t$, we find that

$$ $\displaystyle\mathbb{P}\left(Z_{t}\geq(M-m)\sqrt{\frac{N_{t}\log(1/\delta)}{2}}\text{ and }N_{t}\geq 1\right)$ $\displaystyle\leq t\delta.$ $$

Similar arguments can be used to prove that

$$ $\displaystyle\mathbb{P}\left(-Z_{t}\geq(M-m)\sqrt{\frac{N_{t}\log(1/\delta)}{2}}\text{ and }N_{t}\geq 1\right)$ $\displaystyle\leq t\delta.$ $$

In order to conclude the proof we observe that $Z_{t}=\hat{\mu}_{t}N_{t}$, we normalize by $N_{t}$, and observe that adding the case $N_{t}=0$ can only increase the probability.
∎

###### Proof.

### E.12 Proof of Lemma 14

See [14](#Thmlemma14)

###### Proof.

By Lemma [1](#Thmlemma1), for any price $p=x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon$ and $k^{\prime}$ such that $(k,k^{\prime})\in\mathcal{A}_{t}$, and $\delta^{s}=p-x_{t}^{\top}\theta^{s}$, $\delta^{b}=p-x_{t}^{\top}\theta^{b}$, we have that

$$ $\displaystyle\textnormal{EGFT}(x_{t},p)=I(\delta^{b})F^{s}(\delta^{s})+J(\delta^{s})D^{b}(\delta^{b}).$ $$

Then,

$$ $\displaystyle\textnormal{EGFT}(x_{t},p)=$ $\displaystyle\left(I(k^{\prime}\epsilon)+I(\delta^{b})-I(k^{\prime}\epsilon)\right)\left(F^{s}(k\epsilon)+F^{s}(\delta^{s})-F^{s}(k\epsilon)\right)+$ $\displaystyle\left(J(k\epsilon)+J(\delta^{s})-J(k\epsilon)\right)\left(D^{b}(k^{\prime}\epsilon)+D^{b}(\delta^{b})-D^{b}(k^{\prime}\epsilon)\right).$ $$

Moreover, by letting $\Delta I=I(\delta^{b})-I(k^{\prime}\epsilon)$, $\Delta F=F^{s}(\delta^{s})-F^{s}(k\epsilon)$, $\Delta J=J(\delta^{s})-J(k\epsilon)$ and $\Delta D=D^{b}(\delta^{b})-D^{b}(k^{\prime}\epsilon)$, this yields

$$ $\displaystyle\textnormal{EGFT}(x_{t},p)=$ $\displaystyle I(k^{\prime}\epsilon)F^{s}(k\epsilon)+J(k\epsilon)D^{b}(k^{\prime}\epsilon)+I(\delta^{b})\Delta F+$ $\displaystyle F^{s}(k\epsilon)\Delta I+J(\delta^{s})\Delta D+D^{b}(k^{\prime}\epsilon)\Delta J.$ $$

Since $I$ and $J$ are bounded by $2P$, and $F$ and $D$ are bounded by $1$, this implies that

$$ $\displaystyle\left|\textnormal{EGFT}(x_{t},p)-\left(I(k^{\prime}\epsilon)F^{s}(k\epsilon)+J(k\epsilon)D^{b}(k^{\prime}\epsilon)\right)\right|\leq 2P|\Delta F|+|\Delta I|+2P|\Delta D|+|\Delta J|.$ $$

Now, let us introduce $e^{s}=\delta^{s}-k\epsilon$, and $e^{b}=\delta^{b}-k^{\prime}\epsilon$. Then, we have

$$ $\displaystyle e^{s}$ $\displaystyle=\left(x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon\right)-\left(k\epsilon+x_{t}^{\top}\theta^{s}\right)$ $\displaystyle=x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\theta^{s}).$ $$

On event $\mathcal{E}^{\textnormal{ETC}}$ we have $|e^{s}|\leq\epsilon$. Since $F$ is $L$-Lipschitz continuous, and $\Delta F=F^{s}(k\epsilon+e^{s})-F^{s}(k\epsilon)$, this implies $|\Delta F|\leq L\epsilon$. Similarly, $J$ is $1$-Lipschitz continuous, and $\Delta J=J(k\epsilon+e^{s})-J(k\epsilon)$, so $|\Delta J|\leq\epsilon$.
Similarly,

$$ $\displaystyle e^{b}$ $\displaystyle=\left(x_{t}^{\top}\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}+k\epsilon\right)-\left(x_{t}^{\top}\theta^{b}+k^{\prime}\epsilon\right)$ $\displaystyle=\left(x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{s}_{t}-\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t})+k\epsilon\right)-k^{\prime}\epsilon+x_{t}^{\top}(\mathaccent 0{\symlargesymbols}062{\theta}^{b}_{t}-\theta^{b}).$ $$

By definition of $\mathcal{A}_{t}$, under the event $\mathcal{E}^{\textnormal{ETC}}$ we have $|e^{b}|\leq 2\epsilon$. Since $D$ is $L$-Lipschitz continuous and $\Delta D=D^{b}(k^{\prime}\epsilon+e^{b})-D^{b}(k^{\prime}\epsilon)$, $|\Delta D|\leq 2L\epsilon$. Similarly, $I$ is $1$-Lipschitz continuous, $\Delta I=I(k^{\prime}\epsilon+e^{b})-I(k^{\prime}\epsilon)$, so this implies that $|\Delta I|\leq 2\epsilon$.
Putting everything together, we find that on the event $\mathcal{E}^{\textnormal{ETC}}$,

$$ $\displaystyle\left|\textnormal{EGFT}(x_{t},p)-\left(I(k^{\prime}\epsilon)F^{s}(k\epsilon)+J(k\epsilon)D^{b}(k^{\prime}\epsilon)\right)\right|\leq$ $\displaystyle 6PL\epsilon+3\epsilon.$ $$

Similarly, denoting $\mathaccent 0{\symlargesymbols}062{\Delta}I=I(k^{\prime}\epsilon)-\mathaccent 0{\symlargesymbols}062{I}^{k^{\prime}}$, $\mathaccent 0{\symlargesymbols}062{\Delta}D=D(k^{\prime}\epsilon)-\mathaccent 0{\symlargesymbols}062{D}^{k^{\prime}}$, $\mathaccent 0{\symlargesymbols}062{\Delta}J=J(k\epsilon)-\mathaccent 0{\symlargesymbols}062{J}^{k}$ and $\mathaccent 0{\symlargesymbols}062{\Delta}F=F(k\epsilon)-\mathaccent 0{\symlargesymbols}062{F}^{k}$, we have

$$ $\displaystyle\left|I(k^{\prime}\epsilon)F^{s}(k\epsilon)+J(k\epsilon)D^{b}(k^{\prime}\epsilon)-\left(\mathaccent 0{\symlargesymbols}062{I}^{k^{\prime}}\mathaccent 0{\symlargesymbols}062{F}^{k}+\mathaccent 0{\symlargesymbols}062{J}^{k}\mathaccent 0{\symlargesymbols}062{D}^{k^{\prime}}\right)\right|$ $\displaystyle\leq 2P|\mathaccent 0{\symlargesymbols}062{\Delta}F|+|\mathaccent 0{\symlargesymbols}062{\Delta}I|+2P|\mathaccent 0{\symlargesymbols}062{\Delta}D|+|\mathaccent 0{\symlargesymbols}062{\Delta}J|.$ $$

This concludes the proof.
∎

###### Proof.

## Appendix F Motivating example

Lemma [1](#Thmlemma1) emphasizes that the expected gain from trade at a given price $p$ depends on the quantities $\delta^{s}=p-x_{t}^{\top}\theta^{s}$ and $\delta^{b}=p-x_{t}^{\top}\theta^{b}$. Remember that the difference in average valuations is given by $\Delta=x_{t}^{\top}\theta^{b}-x_{t}^{\top}\theta^{s}$, and with this notation, $\delta^{b}=\delta^{s}-\Delta$. Therefore, the expected gain from trade can be rewritten as a function of the pair $(\delta^{s},\Delta)$. As an immediate consequence, we see that the optimal increment $\delta^{s}$ only depends on the difference in average valuations : if $p=x^{\top}\theta^{s}+\delta^{s}$ maximizes $\textnormal{EGFT}(x,p)$, and if $x^{\prime}$ is such that $x^{\prime\top}\theta^{b}-x^{\prime\top}\theta^{s}=x^{\top}\theta^{b}-x^{\top}\theta^{s}$, then $p^{\prime}=x^{\prime\top}\theta^{s}+\delta^{s}$ maximizes $\textnormal{EGFT}(x^{\prime},p^{\prime})$.

On the other hand, the following example shows that there no explicit dependence of the optimal price increment $\delta^{s}$ on the difference in average valuations . In words, when is small, we might prefer to choose an increment $\delta^{s}$ that leads to trade happening with lower probabilities but corresponds to higher rewards. By contrast, as increases, similar values of the increment $\delta^{s}$ will correspond to higher gains if the trade happens. Then, we might choose to post prices corresponding to a smaller increment $\delta^{s}$ to increase the probability that the trade happens.

This reasoning demonstrates that knowing that an increment $\delta^{s}$ is optimal for a difference in average valuations does not allow us to determine the optimal increment $\delta^{\prime}$ corresponding to a different value ^′ of the difference in average valuations. This implies that to precisely identify the optimal price increment $\delta^{s}$ for all differences in average valuations , it may be necessary to have accurate estimates of the functions $F^{s}$ and $I$ for a broad range of values of $\delta^{s}$. Similar arguments can be employed to argue that precise estimates of the value of $D^{b}$ and $J$ for a wide range of values of $\delta^{b}=\Delta-\delta^{s}$ might also be necessary.

To illustrate this phenomenon, we construct an example where different levels of lead to entirely different choices of the optimal price increment $\delta^{s}$. Specifically, we consider a scenario where, for certain values of $(s_{1},s_{2},s_{3})\in\mathbb{R}^{3}$, $(b_{1},b_{2},b_{3})\in\mathbb{R}^{3}$, $(\alpha_{1},\alpha_{2},\alpha_{3})$ in the simplex, and $\theta>0$ (to be defined later), the density $f^{s}$ (resp. $f^{b}$) of the seller’s noise $\xi^{s}$ (resp. buyer’s noise $\xi^{b}$) is given by:

$$ $\displaystyle f^{s}(\delta)$ $\displaystyle=\frac{\mathbb{I}\{x\in[s_{1},s_{1}+\theta]\cup[s_{2},s_{2}+\theta]\cup[s_{3},s_{3}+\theta]\}}{3\theta}$ $\displaystyle f^{b}(\delta)$ $\displaystyle=\frac{\alpha_{1}\mathbb{I}\{x\in[b_{1},b_{1}+\theta]\}+\alpha_{2}\mathbb{I}\{x\in[b_{2},b_{2}+\theta]\}+\alpha_{3}\mathbb{I}\{x\in[b_{3},b_{3}+\theta]\}}{\theta}.$ $$

The setting in illustrated in figure [1](#A6.F1).

We assume that $(s_{1},s_{2},s_{3})$ and $(b_{1},b_{2},b_{3})$ verify $s_{1}+\theta<b_{1}$, $b_{1}+\theta<s_{2}$, $s_{2}+\theta<b_{2}$, $b_{2}+\theta<s_{3}$, and $s_{3}+\theta<b3$. Then, it is straightforward to see that while $\Delta>0$, and is small enough so that $b_{1}+\theta+\Delta<s_{2}$ and $b_{2}+\theta+\Delta<s_{3}$, the optimal increment belongs to the set $\{\delta_{1},\delta_{2},\delta_{3}\}$, where $\delta_{1}$, $\delta_{2}$, and $\delta_{3}$ belong respectively to $[s_{1}+\theta,b_{1}]$, $[s_{2}+\theta,b_{2}]$, and $[s_{3}+\theta,b_{3}]$.

We also assume that $\alpha_{1}$ is much larger than $\alpha_{2}$, which in turn is much larger than $\alpha_{3}$. Then, the increment $\delta_{1}$ is such that the trade happens with the highest probability: indeed, if $\delta^{s}=\delta^{b}>b_{1}$, the buyer rejects the trade with a high probability. For the same reasons, the probability of a trade happening at an increment $\delta_{2}$ is much lower, and the probability of a trade happening at increment $\delta_{3}$ is the lowest.

Finally, we assume that $b_{3}-s_{3}$ is much larger than $b_{2}-s_{2}$, which in turn is much larger than $b_{1}-s_{1}$. Then, the gain from any trade happening at increment $\delta_{1}$ is small compared to the gain from trades happening at increment $\delta_{2}$, which in turn is small compared to the gain from a trade happening at increment $\delta_{3}$.

Figure: Figure 1: Illustration for the c.d.f. $f^{s}$ and $f^{b}$ corresponding to the example described in Section [F](#A6). The c.d.f. $f^{s}$ is represented in red, the c.d.f. $f^{b}$ is represented in blue.
Refer to caption: /html/2405.18183/assets/figures/example.png

For some well-chosen values of the parameters specified below, when the average gain from trade of the seller and the buyer are both zero ($x_{t}^{\top}\theta^{s}=x_{t}^{\top}\theta^{b}=0$), the most profitable increment is $\delta_{3}$: the probability of the trade happening is less likely, but when it occurs, it is more profitable.

Now, to obtain the probability of a price $p=x^{\top}\theta^{s}+\delta^{s}$ being accepted by the buyer, it is sufficient to translate the cumulative distribution function (c.d.f.) of $\xi^{b}$ (represented in Figure [1](#A6.F1)) by the quantity $\Delta=x^{\top}(\theta^{b}-\theta^{s})$. In particular, when $\Delta>0$ is small enough so that $b_{1}+\theta+\Delta<s_{2}$ and $b_{2}+\theta+\Delta<s_{3}$, we observe that, on the one hand, the probability that the trade happens for the increments $\delta^{s}\in{\delta_{1},\delta_{2},\delta_{3}}$ remains unchanged; however, the corresponding gains if the trade occurs all increase with . For some well-chosen values of the parameters, if is positive but sufficiently small, the expected gain from trade is maximized by $\delta^{s}=\delta^{2}$. When is large, the expected gain from trade is maximized by choosing $\delta^{s}=\delta^{1}$: in other words, this choice of increment ensures that the sale happens with the highest probability, and each sale leads to a reward of at least .
In Figure [2](#A6.F2), we plot the expected gain from trade for different values of as a function of $\delta^{s}$. The values chosen for the parameters are as follows: $(s_{1},s_{2},s_{3})=(0,2,6)$, $(b_{1},b_{2},b_{3})=(0.01,3,20)$, $(\alpha_{1},\alpha_{2},\alpha_{3})=(0.85,0.11,0.04)$, and $\theta=0.001$. With these values, for $\Delta=0$, the optimal increment is $\delta^{3}=10$; for $\Delta=1$, it is $\delta^{2}=2.5$; and for $\Delta=1.5$, it is $\delta^{3}=0.01$.

Figure: Figure 2: Expected gain from trade for different values of increment $\delta^{s}$ and difference in average valuations .
Refer to caption: /html/2405.18183/assets/figures/EGFT_example.png

## Appendix G Proofs of Section 5

See [2](#Thmlemma2)

###### Proof.

To simplify notation, and since we focus on a single round $t\in\mathcal{T}^{\textnormal{B}}$, we omit the explicit dependence on $t$ from $p_{t}$, $q_{t}$, $i_{t}$, $s_{t}$, and $b_{t}$.
We consider two cases. First, if $b-s\leq\nicefrac{{2}}{{T}}$, the inequality is immediately satisfied since the lhs is non-negative while the rhs is $\leq 0$.
Second, if $b-s>\nicefrac{{2}}{{T}}$, let $\mathcal{E}$ be the event in which $p\in[s,(s+b)/2]$. Since $p\sim\mathcal{U}([0,P])$ we have $\mathbb{P}(\mathcal{E})=(b-s)/2P$. Moreover, we have

$$ $\mathbb{P}\left(i=\left\lfloor\log\frac{1}{b-p}\right\rfloor\mid A\right)=\frac{1}{\log T},$ $$

which is well defined since

$$ $p\leq\frac{s+b}{2}\leq b-\frac{1}{T}.$ $$

Let $\mathcal{E}^{\prime}$ denote the event in which $i=\lfloor\log(1/(b-p))\rfloor$. Under $\mathcal{E}$ and $\mathcal{E}^{\prime}$ we get

$$ $q=p+2^{-i}=p+2^{-\lfloor\log(1/(b-p))\rfloor}\geq p+2^{-(\log(1/(b-p))+1)}=p+\frac{b-p}{2}=\frac{p+b}{2}.$ $$

Therefore, when $b\geq s+\nicefrac{{2}}{{T}}$,

$$ $\displaystyle\mathbb{E}\left[\textsc{Profit}(p,q)\right]$ $\displaystyle=(q-p)\,\frac{b-s}{2P\log T}$ $\displaystyle\geq\left(\frac{p+b}{2}-p\right)\,\frac{b-s}{2P\log T}$ $\displaystyle\geq\frac{(b-s)^{2}}{8P\log T}.$ $$

This concludes the proof.
∎

See [3](#Thmlemma3)

###### Proof.

First, we observe that given the sequence $(b_{t},s_{t})_{t\in\llbracket T\rrbracket}$, and a time step $\tau$, by Azuma-Hoeffding inequality we have that, with probability at least $1-\delta$,

$$ $\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\textsc{Profit}_{t}(p_{t},q_{t})\geq\mathbb{E}\left[\textsc{Profit}_{t}(p,q)\right]-\sqrt{2\log(1/\delta)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}([b_{t}-s_{t}]^{+})^{2}}.$ $$

Then, by applying a union bound, the above inequality holds simultaneously for all possible $\tau$ with probability at least $1-\delta T$. Then, by setting $\delta=T^{2}$, with probability at least $1-1/T$, it holds:

$$ $\displaystyle\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\textsc{Profit}_{t}(p_{t},q_{t})$ $\displaystyle\geq\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\mathbb{E}\left[\textsc{Profit}_{t}(p,q)\right]-\sqrt{4\log(T)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}([b_{t}-s_{t}]^{+})^{2}}$ $\displaystyle\geq\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\left(\frac{([b_{t}-s_{t}]^{+})^{2}}{8P\log T}-\frac{2}{T}\right)-\sqrt{4\log(1/\delta)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}([b_{t}-s_{t}]^{+})^{2}}$ (by Lemma 2 ) $\displaystyle\geq\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\frac{([b_{t}-s_{t}]^{+})^{2}}{8P\log T}-\sqrt{4\log(T)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}([b_{t}-s_{t}]^{+})^{2}}-2$ $\displaystyle=\tau\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\frac{1}{\tau}\frac{([b_{t}-s_{t}]^{+})^{2}}{8P\log T}-\sqrt{4\log(T)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}([b_{t}-s_{t}]^{+})^{2}}-2$ $\displaystyle\geq\frac{\tau}{8P\log T}\left(\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\frac{[b_{t}-s_{t}]^{+}}{\tau}\right)^{2}-\sqrt{4\log(T)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}([b_{t}-s_{t}]^{+})^{2}}-2$ (by Jensen’s Inequality) $\displaystyle\geq\frac{\alpha}{8P\log(T)}\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}-\sqrt{4\log(T)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}([b_{t}-s_{t}]^{+})^{2}}-2$ (by 3 ) $\displaystyle\geq\frac{\alpha}{8P\log(T)}\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}-\sqrt{4P^{2}\log(T)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}}-2.$ $$

This concludes the proof.
∎

See [4](#Thmtheorem4)

###### Proof.

The one-bit algorithm is global budget balanced by construction (see choice of $\mathcal{B}$).

Then, we condition the high probability regret bound on the following events:

- •
With probability $1-1/T$ the two-bit EOC algorithm guarantees a number of exploration rounds smaller than $|\mathcal{T}^{\textnormal{E}}|$ and regret at most $R^{(2)}_{T}$;
- •
With probability $1-1/T$, it holds the inequality in [Lemma 3](#Thmlemma3)
- •
By Azuma-Hoeffding, with probability at least $1-1/T$ it holds
$\sumop\slimits@_{t=1}^{\tau}\max_{p}\textnormal{EGFT}(x_{t},p)\leq\sumop\slimits@_{t=1}^{\tau}[b_{t}-s_{t}]^{+}+\sqrt{16P^{2}\tau\log(T)}.$

Then, the regret can be bounded as follows

$$ $\displaystyle R_{T}$ $\displaystyle=\sumop\slimits@_{t=1}^{T}\max_{p}\textnormal{EGFT}(x_{t},p)-\sumop\slimits@_{t=1}^{T}\textnormal{EGFT}(x_{t},p_{t})$ $\displaystyle\leq\sumop\slimits@_{t=1}^{\tau}\max_{p}\textnormal{EGFT}(x_{t},p)+\sumop\slimits@_{t=\tau+1}^{T}\left(\max_{p}\textnormal{EGFT}(x_{t},p)-\textnormal{EGFT}(x_{t},p_{t})\right)$ $\displaystyle\leq\sumop\slimits@_{t=1}^{\tau}\max_{p}\textnormal{EGFT}(x_{t},p)+2|\mathcal{T}^{\textnormal{E}}|+R^{(2)}_{T}$ $\displaystyle\leq\sumop\slimits@_{t=1}^{\tau}[b_{t}-s_{t}]^{+}+\sqrt{16P^{2}\tau\log(T)}+2|\mathcal{T}^{\textnormal{E}}|+R^{(2)}_{T}$ $\displaystyle\leq\sumop\slimits@_{t=1}^{\tau}[b_{t}-s_{t}]^{+}+\alpha\tau+2|\mathcal{T}^{\textnormal{E}}|+R^{(2)}_{T}$ $\displaystyle\leq 2\sumop\slimits@_{t=1}^{\tau}[b_{t}-s_{t}]^{+}+2|\mathcal{T}^{\textnormal{E}}|+R^{(2)}_{T},$ $$

where in the second-to-last inequality we use $\tau\geq 1024P^{3}\alpha^{-2}\log^{3}T$ (since $\tau\geq\mathcal{B}/2P$), and the last inequality is by [3](#Thmassumption3).

Then, by [Lemma 3](#Thmlemma3) and since $\sumop\slimits@_{t=1}^{\tau}[b_{t}-s_{t}]^{+}\geq\sumop\slimits@_{t=1}^{\tau}\textsc{Profit}_{t}(p_{t},q_{t})\geq 2048P^{4}\alpha^{-2}\log^{3}T$, we have

$$ $\displaystyle\sumop\slimits@_{t\in\llbracket\tau\rrbracket}\textsc{Profit}_{t}(p_{t},q_{t})$ $\displaystyle\geq\frac{\alpha}{8P\log(T)}\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}-\sqrt{4P^{2}\log(T)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}}-2$ $\displaystyle\geq\frac{\alpha}{8P\log(T)}\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}-\sqrt{8P^{2}\log(T)\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}}$ $\displaystyle\geq\frac{\alpha}{16P\log(T)}\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}.$ $$

Then, since $\mathcal{B}\leq 2048P^{4}\alpha^{-2}|\mathcal{T}^{\textnormal{E}}|\log^{3}T$ and $\sumop\slimits@_{t=1}^{\tau}\textsc{Profit}_{t}(p_{t},q_{t})\leq\mathcal{B}+1$, by substituting in the expression above we obtain the desired bound on $\sumop\slimits@_{t\in\llbracket\tau\rrbracket}[b_{t}-s_{t}]^{+}$ and hence on the regret.
∎

###### Proof.

###### Proof.

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 2
questions: 1) I am wondering why the stronger bounds from Contextual Search (Liu et al) were not used in place of the Feature Based Pricing. It seems many of the ideas would carry over and you would achieve improved regret guarantees.

2) It would be useful to know what new ideas are introduced for noisy setting  and how much was already known in other settings.
soundness: 4
strengths: The authors propose a very reasonable contextual model of online bilateral trade. I find the new model to be well motivated and combines two natural areas of study namely bilateral trade and online contextual regret minimization. The algorithms themselves seem interesting and are fairly natural. 

The reduction from the two bit strong budget balanced case to the one bit global budget balanced case is perhaps the most interesting to me. Essentially it is a general recipe where by one can exploit explore-or-commit algorithms and perform the explorations in such a way that we can always get feedback about either the buyer or seller. However, we may lose regret compared to other party, and thus we need to ensure that there is sufficient budget to do this. This is done by measuring the average profit the 2 bit algorithm can learn and then appropriately setting the parameters to balance out the findings.
summary: This paper tackles the bilateral trade problem in an online setting where there is an additional context present. At each time step $t$, a buyer and a seller arrive with private values $b_t$ and costs $s_t$. The algorithm must provide a pair of prices $(p,q)$ such that a sale happens if the buyer's value $b_t$ is less than $q$ and the seller's value is above $p$. The Gain from this trade assuming a sale happens is $(b_t - s_t)$.  The authors consider the problem of maximizing the gains from trade assuming either two bit feedback where we find out if $\mathbb{1}[b_t \leq q] $ and if $\mathbb{1}[s_t \geq p]$. They also consider the model where we have only one bit feedback where we know the product of these two bits of feedback. The original problem was already studied by Cesa-bianchi et al. This problem considers the setting where the buyer and seller have a hidden vector of preferences $\theta_b, \theta_s$ and their private values are generated from a shared context $b_t = x_t^T \theta_b$ and $s_t = x_t^T \theta_s$ . They consider where there may be some noise that is added as well as the budget balanced setting where the prices offered to both parties must be the same ($p=q$). 


The main results:

1) In the two feedback setting with strong budget balance $p=q$ at each time step when there is no noise in the setting. Here the authors use a natural modification of the feature based toolification.
2) In the two bit feedback model with noise, where the noise is i.i.d coming from distributions with bounded support and densities. Finally they devise an algorithm following the explore-or-commit framework where the authors decompose the gain in terms 
3) They also study the one bit feedback problem where you only find out if a sale happens or not. To get good bounds for this model they assume they have a good regret for the strongly-balanced two bit feedback and then use that in a black box manner. However the new bounds only have a global budget balanced guarantee.
weaknesses: Although the algorithms are natural and interesting, I am unable to distinguish where the new ideas are and how much of the paper is using known tools to a new setting. I would appreciate more explanation on what the new ideas are in both the two bit setting and the one-bit setting. \o

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Can you elaborate a bit more about the comparison with the related work, "A contextual online learning
theory of brokerage. arXiv preprint arXiv:2407.01566, 2024"? The setting is very similar, however, it seems the valuations of two traders in their paper share the same expected value.

2. For the one-bit feedback model, if we want to maintain per-round budget balance, is it still learnable?
soundness: 3
strengths: The paper is well-written and analyzes a very interesting theoretical problem. The authors did a good job to describe the problem and how the algorithm handles the challenges. 

The theoretical guarantee of the paper is sound. The authors provide a complete story for the setting with two-bit feedback model. In addition, the reduction from one-bit to two-bit by sacrificing budget balance constraint is very interesting and elegant.
summary: In this paper, the authors investigate online contextual bilateral trade problem, where the valuations of two traders are modeled by different (unknown) linear functions. The authors focus on two different feedback models: (1) two-bit feedback model, where the learner can observe the binary feedback of both traders (2) one-bit feedback model, where the learner can only learns the binary information of whether the trade happens or not. For (1), the authors propose an online learning algorithm to set trading price at each round (that satisfies the strong budget balance constraint), which achieves $O(T^{2/3})$ regret. The authors also show a matching lower bound. For (2), the authors provide a reduction from one-bit feedback model to two-bit feedback model by sacrificing per-round budget balance to global budget balance and show the algorithm used in (1) can be applied to (2) and still achieves sublinear regret guarantee.
weaknesses: There is no matching lower bound for the one-bit feedback setting. I also have some questions regarding this setting.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. How do you check whether the strong budget balance condition holds or not?

2. Could you please conduct numerical experiments to show the real performance? Also, what is the computation complexity of your algorithms.
soundness: 2
strengths: 1. The paper derives strong $O(\log T)$ regret, though under stronger conditions.

2. The paper derives $O(T^{2/3})$ regret upper bound for their algorithm and shows that there exists a matching lower bound.
summary: This paper studies the bilateral trade model which involves the challenge of enabling transactions between a seller and a buyer who both hold private valuations for the item. This paper considers specifically the online scenario, where at each step there is a fresh seller and buyer entering the system and the pricing decisions for both parties must be made immediately without prior knowledge of their valuations. The paper further restricts to the contextual setting where the private valuations for the seller and buyer are linearly featured by a context. A two-bid feedback is considered where for both the seller and the buyer, it can be observed whether the posed price has exceeded its value or not. By further assuming a strong budget balance between the buyer and the seller, the paper is able to derive a $O(\log T)$ regret. Without the budget balance conditions, the paper achieves a $O(T^{2/3})$ regret, which is minimax optimal. The paper further discusses the one-bit feedback and shows the potential to obtain a sub-linear regret.
weaknesses: 1. The main results of the paper rely on the two-bid feedback setting, where both the seller and the buyer reveal to the decision maker whether they want to sell the product or buy the product. This is quite a strong condition, and the paper would benefit from a more detailed discussion on whether this condition happens or not in reality.

2. Though the theoretical guarantee is provided, there are not numerical experiments in the paper showing the empirical performances. Also, the computation complexity of the proposed algorithms has not been discussed.

3. The algorithmic idea and the proof technique mainly build upon the previous work Cohen et al. (2020) and it has not been discussed which part of the proof is novel.

4. The $O(\log T)$ regret depends on some strong conditions that are hard to justify in practice.

5. The paper is overall theoretical and it is not clear how to apply their algorithm in practice.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Two bit feedback:
- Do we gain anything by removing the budget balance constraint in the two-bit feedback case (simplifying the algorithm maybe)?
- Can the authors provide more intuition of how combining the ETC, and Scouting strategy works? (maybe along the line -> with $O(T^\beta)$  exploration regret we reduce the 'Range of Delta_t' = $O(T^{-\alpha})$ and then the Scouting results in $O(T^{2/3})$ regret)
- As we do not rely on the exact reward feedback, will approximately linear reward functions work? 


One bit feedback:
- In the one-bit feedback case, is the knowledge of $\alpha$ essential? 
- Can the authors discuss if the $\alpha$ dependency a side effect of selecting the specific strategy of collecting the profit in the first phase? Can we improve/remove such dependency by adaptively collecting the budget or by leveraging improved exploration strategy?
soundness: 4
strengths: - This work initiates the feature based online bilateral trade problem
- With budget balance and two-bit feedback they establish a tight $O(T^{2/3})$ regret bound with by combining Scouting and Explore-or-Commit strategies. 
- They extend the results to the one-bit feedback setup while maintaining the regret guarantees under the budget balance constraint.
summary: The authors study the feature based online bilateral trade problem. Here,  the buyer's valuations are given by a linear function. The seller's valuation is similar. In each round, the buyer and seller see a new context that along with their private parameter vector determines the parameterized part of the reward. The noisy version of the problem adds a i.i.d. random variable (not necessarily zero mean) with the parameterized reward.  The authors study the problem in both 2-bit and 1-bit feedback under strong and global budget balance constraints, respectively. For the deterministic version they adopt existing  EllipsoidPricing policy and show a log(T) regret bound. For the noisy, version they propose an Explore-or-Commit algorithm that achieves a $O(T^{3/4})$ regret, which is further improved to $O(T^{2/3})$ (which matches the lower bound). Some tradeoff between budget and regret is established for 1-bit feedback case.
weaknesses: - See questions for more discussions around improving the paper, and my own curiosity.

Meta-review: The reviewers all appreciate the new scouting algorithm and the minimax optimal regret it achieves. A good paper overall.

Decision: Accept (Poster)