Tight Regret Bounds for Fixed-Price Bilateral Trade

For readability, it is helpful to review the standard MAB problem and the elimination algorithms: there are $K$ arms whose (independent) random rewards follow the Bernoulli distributions $\mathrm{𝙱𝚎𝚛𝚗}({\rho }_i)$ with mean rewards ${\rho }_i\in [0,1]$, $\forall i\in [K]$.

An elimination algorithm operates in $L+1=\log \left(\frac{1}{\epsilon }\right)+1$ stages, for some parameter $\epsilon =\epsilon (T,K)>0$ to be determined. In stage $\mathrm{\ell }\in [0:L]$, we pull each arm $2^{\mathrm{\ell }}/\epsilon$ times; by standard concentration inequalities, with high probability we can identify and eliminate those $\mathrm{\Omega }(\sqrt{\epsilon /2^{\mathrm{\ell }}})$-suboptimal mean rewards. After all stages, the rest of the entire time horizon $[T]$ (if existential) can arbitrarily exploit the non-eliminated mean rewards–every such reward is $𝒪(\sqrt{\epsilon /2^L})=𝒪(\epsilon )$-approximately optimal.

This elimination algorithm has two key features in each stage $\mathrm{\ell }\in [0:L]$, which we call the accuracy guarantee $\mathrm{■}$ ‣ 1 and the regret guarantee $\mathrm{■}$ ‣ 1.

• $\mathrm{■}$

  (MAB-AG) After stage $\mathrm{\ell }$, every non-eliminated mean reward is $𝒪(\sqrt{\epsilon /2^{\mathrm{\ell }}})$-approximately optimal.

• $\mathrm{■}$

  (MAB-RG) Stage $\mathrm{\ell }$ accumulates at most $𝒪(\sqrt{\epsilon /2^{\mathrm{\ell }-1}})\cdot 2^{\mathrm{\ell }}/\epsilon \cdot K=𝒪(K/\epsilon )$ regret.¹¹1More rigorously, the initial stage $\mathrm{\ell }=0$ requires a different deduction to the same regret bound $1\cdot 2^0/\epsilon \cdot K=𝒪(K/\epsilon )$.

In combination, the total regret of this elimination algorithm is at most

By choosing $\epsilon =\tilde{\mathrm{\Theta }}(\sqrt{K/T})$, we achieve (nearly) optimal $\widetilde{𝒪}(\sqrt{KT})$ regret.

In the bilateral trade model, it turns out that by considering the $\frac{1}{K}$-net of the entire action space ${\{a_{i,j}:=(\frac{i}{K},\frac{j-1}{K})\}}_{i,j\in [K]}\subseteq {[0,1]}^2$, at least one of the near-diagonal actions ${\{a_{k,k}\}}_{k\in [K]}$ is a $\frac{1}{K}$-approximation to the benchmark action $(p^{\ast },q^{\ast })$; we thus designate ${\{a_{k,k}\}}_{k\in [K]}$ as the (initial) candidates and index them by ${𝒞}_0:=[1:K]$.

If we could mechanically implement the above elimination algorithm for the standard MAB problem, then the total regret would be at most

by choosing $K=\tilde{\mathrm{\Theta }}({\epsilon }^{-1})$ and $\epsilon =\tilde{\mathrm{\Theta }}(T^{-1/3})$, which gives the desired regret bound.

The standard elimination template suggests maintaining near-diagonal candidates $a_{k,k}$ and eliminating clearly suboptimal ones stage by stage. The obstacle is that, under one-bit feedback, playing a candidate itself does not provide an unbiased estimator for its GFT. A direct estimator queries separate polylines for different candidates and therefore incurs too much regret.

Our key idea is to reuse information across candidates. At each stage, the surviving candidates are enclosed by short diagonal segments. Around each segment, we query shared horizontal and vertical actions. By independence of the seller’s and buyer’s values, the desired GFT values can be reconstructed through recursive ratio decompositions. As the stages progress, the queried actions move exponentially closer to the diagonal, so their per-query regret diminishes. This simultaneously gives the accuracy invariant and the regret invariant needed for the $\tilde{O}(T^{2/3})$ bound. The full recursive implementation and concentration analysis appear in the full version.

Basically, a regret lower bound requires constructing a family of hard-to-distinguish instances: When facing some instance from this family, a mechanism must determine its identity in the online learning process, namely “finding a needle in a haystack”.

To address our problem using this approach, we shall construct one base instance ${𝒟}_0$ and $K\ge 1$ hard instances ${\{{𝒟}_k\}}_{k\in [K]}$ – recall that an instance is a ${[0,1]}^2$-supported joint distribution. Each hard instance ${𝒟}_k$ shall differ from the base instance ${𝒟}_0$ by some $\delta >0$ in the total variation distance. As such, ${𝒟}_k$ can simply perturb ${𝒟}_0$ by total probability mass of $\mathrm{\Theta }(\delta )$, distributed across constant number of actions, which forms the “needle”. The construction shall follow two criteria:

• $\mathrm{■}$

  Information-Regret Dilemma: Each hard instance ${𝒟}_k$ has a set of informative actions. Only those actions can provide information (on playing) that helps distinguish this hard instance ${𝒟}_k$, but each of them will incur constant regret $\mathrm{\Omega }(1)$.

• $\mathrm{■}$

  Disjointness: All hard instances ${\{{𝒟}_k\}}_{k\in [K]}$ shall have disjoint sets of informative actions, thus no information sharing on individual plays of informative actions of different ${𝒟}_k$’s.

Given such a construction (if possible), we can informally reason about the total regret of a mechanism as follows:

• $\mathrm{■}$

  If all individual hard instances ${\{{𝒟}_k\}}_{k\in [K]}$ are distinguishable from the base instance ${𝒟}_0$, given the total variation distances of $\delta$, this necessitates $\mathrm{\Omega }({\delta }^{-2})$ number of plays of a single ${𝒟}_k$’s informative actions and thus $\mathrm{\Omega }(K{\delta }^{-2})$ number of such plays altogether (Disjointness). However, then, we will suffer from $\mathrm{\Omega }(K{\delta }^{-2})$ total regret (Information-Regret Dilemma).

• $\mathrm{■}$

  Otherwise, some hard instances ${𝒟}_k$ are indistinguishable, and (roughly speaking) we will suffer from $\mathrm{\Omega }(\delta T)$ total regret when facing one of them.

By choosing $\delta =K^{1/3}{T}^{-1/3}$, any mechanism will incur total regret

Consequently, proving an optimal lower bound reduces to the task of seeking a construction that has the largest possible $K\ge 1$ and, simultaneously, retains the above criteria.

It remains to determine the bottleneck of $K\ge 1$. Since each hard instance ${𝒟}_k$ for $k\in [K]$ needs to perturb the base instance ${𝒟}_0$ by total probability mass of $\mathrm{\Theta }(\delta )$ (planting a “mass-$\delta$ needle”), and these perturbations are “disjoint”, we naturally require $K=𝒪({\delta }^{-1})$. So if a construction can satisfy $K=\mathrm{\Theta }({\delta }^{-1})$, plugging this into Equation 1 directly gives an $\mathrm{\Omega }(T^{3/4})$ lower bound, as desired.

To implement the above general approach in practice, however, the technical challenge is due in large part to the GBB constraint. As we quote from [3]:

“This (the GBB constraint) considerably complicates the construction of the hard instances, as any algorithm could sacrifice some profit temporarily by posting prices with $P^t>Q^t$ to extract a large Gains from Trade.”

The previous work [3] and our work will adopt very different remedies for the GBB constraint.

The previous work [3] circumvents the GBB constraint in an ingenious manner. Their base instance ${𝒟}_0$ (see Figure 1(a) for a diagram) involves, just below the diagonal, value points “so bad” that even a single action play on their lower right side will incur intolerable regret.
$⊳$ These value points refer to grey points ${𝒱}^4$ in Figure 1(a). Further, “so bad” means the GFT-decrease due to a single such value point even dominates the total GFT-increase due to all other value points vertically above it.
This automatically forces a regret-optimal mechanism to satisfy the GBB constraint. In other words, central to their lower-bound construction is such a more “qualitative” principle:

Sacrifice of profit cannot produce extra Gains from Trade.

As it turns out, there are as many “so bad” value points as the hard instances ($K\ge 1$), and they each have probability mass $\mathrm{\Omega }(K\delta )$. Then, it can be shown that $K=\mathrm{\Theta }({\delta }^{-1/2})$. Plugging this in Equation 1 gives an $\mathrm{\Omega }(T^{5/7})$ lower bound [3, Theorem 5.5].

Here, our contribution is a more careful treatment of the GBB constraint instead of simply circumventing it like [3]. Specifically, instead of incorporating “so bad” value points into the base instance ${𝒟}_0$, our lower-bound construction derives from a more “quantitative” principle:

Sacrifice of profit (“investment”) can produce extra Gains from Trade (“return”).
Just, the “return on investment” is not worthy enough for regret minimization.

This means a regret-optimal mechanism must abandon “investment” and, thus, restrict its action plays to the upper left side of the diagonal. In this manner, our more “quantitative” principle reaches the same goal – the GBB constraint – as the more “qualitative” principle by [3]. Technically, our principle is also more flexible for lower-bound construction, which enables us to construct $K=\mathrm{\Theta }({\delta }^{-1})$ many hard instances (while retaining the mentioned criteria) and thus show an $\mathrm{\Omega }(T^{3/4})$ lower bound.

We have developed new techniques to implement the above discussions into a formal proof. In particular, we introduce a new constraint called Global Price Balance, given by

Under our lower-bound construction, this new constraint turns out to be a consequence/relaxation of the original GBB constraint – every GBB mechanism must satisfy it – and is relatively easier to manipulate. Indeed, our $\mathrm{\Omega }(T^{3/4})$ lower bound holds “more generally” for any mechanism that satisfies this new constraint; see Section 4 for details.

Our fixed-price mechanism GBB-OneBit will use the following parameters. Specifically, both subroutines ProfitMax and FractalElimination will use the discretization parameter $K$, only the former will use the profit threshold $\beta$, and only the latter will use the others $L$, $\delta$, and ${\gamma }_{\mathrm{\ell }}$’s.

In expectation over the randomness of values $(S,B)\sim {𝒟}_S⨂{𝒟}_B$, an action $(p,q)\in {[0,1]}^2$ induces (expected) Gains from Trade $\text{GFT}(p,q)$, (expected) profit $\text{Profit}(p,q)$, and (expected) regret $\text{Regret}(p,q)$. It is easy to see that these formulae are $[0,1]$-valued.

Here we abuse notation: ${𝒟}_S(p):={\mathrm{\mathbb{P}}}_{S\sim {𝒟}_S}[S\le p]$ and denote the corresponding cumulative distribution functions (CDF’s).

The following Lemma 2 shows a useful decomposition of the formula $\text{GFT}(p,q)$.

In addition, we recall that one-bit feedback $Z^t=Z(S^t,B^t,P^t,Q^t)\in \{0,1\}$ reveals whether or not the trade succeeded in a single round $t\in [T]$.

To understand the performance guarantees of our fixed-price mechanism GBB-OneBit, all we need to know about (Phase 1 of GBB-OneBit) the subroutine ProfitMax can be summarized into the following Proposition 3, which is quoted (or, indeed, slightly rephrased) from [3, Lemma 5.1].³³3This fixed-price mechanism ProfitMax is built on the EXP3.P learning algorithm by [1]; its performance guarantees given in Proposition 3 were shown by [3, Lemma 5.1] for “adversarial values”, which accommodates “independent values”. As mentioned, the purpose of ProfitMax is to accumulate sufficient profit (at the cost of tolerable regret), making mechanism design in subsequent phases more flexible. For detailed implementation of ProfitMax, the interested reader can reference [3, Sections 3 and 5].

In the rest of Section 3, we would call the subroutine ProfitMax “successful” if its cumulative regret satisfies the bound ${\sum }_{t\in [T^{\prime }]}\text{Regret}(P^t,Q^t)\le 220T^{2/3}{\log }^{5/3}(T)$ given in Corollary 4, or “failed” otherwise.

Based on the profit accumulated above ($\ge \beta =\tilde{\mathrm{\Theta }}(T^{2/3})$, say), our fixed-price mechanism GBB-OneBit (Phase 2 thereof) then invokes the subroutine FractalElimination to distinguish the optimal action $a^{\ast }=(p^{\ast },q^{\ast })\in {[0,1]}^2$, or rather, its good enough approximations, while preserving the GBB constraint.

Now let us elaborate on this subroutine FractalElimination; see Algorithm 2 for its implementation and Figure 2 for a diagram. Before all else, we use our discretization parameter $K=\tilde{\mathrm{\Theta }}(T^{2/3})$ to construct the following $\frac{1}{K}$-net ${\{a_{i,j}\}}_{1\le i,j\le K}$ of the whole action space ${[0,1]}^2$ (yet FractalElimination only takes actions from the lower-right half ${\{a_{i,j}\}}_{1\le j\le i\le K}$). Among these discrete actions, we designate ${\{a_{k,k}\}}_{k\in [1:K]}$ as candidates of “good enough approximations to the optimal action $a^{\ast }$”; indeed, the optimal candidate $a_{\mu ,\mu }$ (say) is a good enough $\frac{1}{K}$-approximation to the optimal action $a^{\ast }$.

In regard to discrete actions ${\{a_{i,j}\}}_{1\le i,j\le K}$ and one-bit feedback $Z^t=\mathbb{𝟙}[S^t\le P^t]\cdot \mathbb{𝟙}[Q^t\le B^t]\in \{0,1\}$, we define the trade rates ${\{{\text{Z}}_{i,j}\}}_{1\le i,j\le K}$ as follows. It is easy to see that ${\text{Z}}_{i,j}\in [0,1]$ and the monotonicity ${\text{Z}}_{1,j}\le \mathrm{\cdots }\le {\text{Z}}_{i,j}\le \mathrm{\cdots }\le {\text{Z}}_{K,j}$ and ${\text{Z}}_{i,1}\ge \mathrm{\cdots }\ge {\text{Z}}_{i,j}\ge \mathrm{\cdots }\ge {\text{Z}}_{i,K}$.

In regard to (Lemma 2) the decomposition $\text{GFT}(p,q)=\text{H}(p,q)+\text{V}(p,q)+\text{Profit}(p,q)$, $\forall (p,q)\in {[0,1]}^2$, we define the following terms $\tilde{\text{H}}([\sigma :\tau ],j)$ and $\tilde{\text{V}}(i,[\sigma :\tau ])$.

It is easy to check that all these terms are $[0,1]$-bounded and, specifically, that $\tilde{\text{H}}([1:i],j)=\text{H}(a_{i,j})\pm K^{-1}$ and $\tilde{\text{V}}(i,[j:K])=\text{V}(a_{i,j})\pm K^{-1}$, $\forall 1\le i,j\le K$. Moreover, every candidate $k\in [1:K]$ induces negligible profit $\text{Profit}(a_{k,k})=\pm K^{-1}$.

FractalElimination follows a divide-and-conquer principle and, over $L+1\approx \log \left(K\right)$ stages, locates the optimal candidate $a_{\mu ,\mu }$ more and more accurately. In more details:

Induction Hypothesis. Before a specific stage $\mathrm{\ell }\in [0:L]$, we have already located $a_{\mu ,\mu }$ in a candidate set ${𝒞}_{\mathrm{\ell }}\subseteq [1:K]$, and we have up to $2^{\mathrm{\ell }}$ many disjoint segments $[\sigma :\tau ]\subseteq [1:K]$ whose union covers ${𝒞}_{\mathrm{\ell }}$. For every considered segment $[\sigma :\tau ]$, estimates $\text{h}\approx \tilde{\text{H}}([1:\sigma -1],\sigma )$ and $\text{v}\approx \tilde{\text{V}}(\tau ,[\tau +1:K])$ are good enough.

Base Case. Before the initial stage $\mathrm{\ell }=0$, we just consider a “universal” candidate set ${𝒞}_0:=[1:K]$ and a single “universal” segment $[\sigma :\tau ]=[1:K]$. Therefore, (Phase 2 of GBB-OneBit) estimates $\text{h}=0=\tilde{\text{H}}(\mathrm{\varnothing },\sigma )=\tilde{\text{H}}([1:\sigma -1],\sigma )$ and $\text{v}=0=\tilde{\text{V}}(\tau ,\mathrm{\varnothing })=\tilde{\text{V}}(\tau ,[\tau +1:K])$ are perfect.

Induction Step. In a specific stage $\mathrm{\ell }\in [0:L]$, we aim at locating $a_{\mu ,\mu }$ more accurately ${𝒞}_{\mathrm{\ell }+1}\subseteq {𝒞}_{\mathrm{\ell }}$, by leveraging one-bit feedback, and retain Induction Hypothesis for the next stage $\mathrm{\ell }+1\in [1:L+1]$.

For every considered segment $[\sigma :\tau ]$ (cf. the two red $\text{<svg version="1.1" fill="none" height="13.83700013837" stroke="none" width="13.83700013837" overflow="visible"><g transform="translate(0,13.83700013837) scale(1,-1)"><g transform="translate(6.92,6.92)"><circle style="--ltx-stroke-color:\#000000;" r="5.53" stroke="\#000000" stroke-width="0.5" cx="0" cy="0"></circle></g></g></svg>}$’s in Figure 2), we can obtain (Lines 2 and 3) the following good enough estimates for trade rates ${\{{\text{Z}}_{i,\sigma }\}}_{i\in [\sigma :\tau ]}\cup {\{{\text{Z}}_{\tau ,j}\}}_{j\in [\sigma :\tau ]}$ (cf. the red horizontal/vertical lines in Figure 2).