Breaking the \(T^{3/4}\) Barrier for Regret Minimization With Bi-Dimensional CDFs
July 22, 2026
Abstract
We study regret minimization for learning CDF-related objectives of the form \[g(x)\cdot\mathbb{P}_{X\sim\mathcal{D}}(X\le x),\] over \([0,1]^2\), where \(g\) is a known Lipschitz function and \(\mathcal{D}\) is an unknown distribution. At each round \(t\), the learner selects a point \(x_t\) and observes the binary feedback \(\mathbb{I}(X_t\le x_t)\), where \(X_t\sim\mathcal{D}\). We design an algorithm achieving regret \(\widetilde{\mathcal{O}}(T^{7/10})\), improving over the previous best-known bound of \(\widetilde{\mathcal{O}}(T^{3/4})\) and showing that the curse of dimensionality can be at least partially lifted for this class of objectives, though a gap remains with the \(\Omega(T^{2/3})\) lower bound. As an application, our techniques yield the same \(\widetilde{\mathcal{O}}(T^{7/10})\) regret bound for profit maximization in repeated bilateral trade with fixed prices.
1 Introduction↩︎
We study regret minimization for learning cumulative distribution functions (CDFs) over bi-dimensional domains. In the general \(d\)-dimensional variant, the learner seeks to learn a function \(r:[0,1]^d\to[-1,1]\) of the form \[r(x) \coloneq g(x) \cdot \mathbb{P}_{X\sim \mathcal{D}} (X\le x),\] where \(g:[0,1]^d\rightarrow [-1,1]\) is a known Lipschitz function, \(X\) is drawn from an unknown distribution \(\mathcal{D}\), and the inequality \(X\le x\) holds component-wise. At each round \(t\in[T]\), an independent sample \(X_t\sim\mathcal{D}\) is drawn, the learner selects a query point \(x_t\in[0,1]^d\), and observes the single bit \(\mathbb{I}(X_t\le x_t)\). The goal is to minimize the cumulative regret \[R_T\coloneq \max_{x\in [0,1]^d} \mathbb{E}\left[\sum_{t\in[T]} \left( r(x)- r(x_t) \right)\right].\]
This formulation captures numerous economic settings. For instance, it models profit maximization, where the Lipschitz function \(g(\cdot)\) represents the profit generated by a trade at a fixed set of prices, while the CDF characterizes the demand curve, i.e., the probability that buyers or sellers accept a trade at that price.
Our problem sits at the intersection of two lines of research. From an online learning perspective, the state of the art for problems of this type is given by (one-sided) Lipschitz bandits, which yield regret \(\widetilde{\mathcal{O}}\left(T^{2/3}\right)\) in the univariate case, \(\widetilde{\mathcal{O}}\left(T^{3/4}\right)\) in the bi-dimensional case, and \(\widetilde{\mathcal{O}}\left(T^{\frac{d+1}{d+2}}\right)\) in general [1], [2]. From a more economic perspective, our framework captures several natural learning problems for fixed-price mechanisms, including bilateral trade [3], the joint ads model [4], and small-market models [5], [6]. The canonical example is profit maximization with fixed-price mechanisms in bilateral trade, for which \(\widetilde{\mathcal{O}}\left(T^{3/4}\right)\) is again the best known bound. A substantial line of work studies regret minimization in this setting [3], [7]–[10]; most of it addresses the problem of maximizing the gain from trade1 — a problem not subsumed by our framework — and likewise achieves a matching \(\widetilde{\mathcal{O}}(T^{3/4})\) bound.
All of these problems face a curse of dimensionality: the best known bi-dimensional bounds are worse than the \(\widetilde{\mathcal{O}}\left(T^{2/3}\right)\) rate that is optimal in univariate settings like pricing [13]. In this paper, we focus on the bi-dimensional setting, \(d=2\), and ask whether this curse is inherent to CDF-based objectives, or whether it can be at least partially lifted:
Is it possible to improve over the \(\widetilde{\mathcal{O}}\left(T^{3/4}\right)\) regret bound for profit maximization with fixed-price mechanisms, and more generally for CDF-based objectives, reducing the curse of dimensionality?
A related result was recently established for the associated sample-complexity problem by [14], who show that uniformly estimating the CDF of a \(d\)-variate random variable on \([0,1]^d\) to precision \(\epsilon\), over a grid of \(K^d\) points, requires only \(\frac{1}{\epsilon^3}\log(K)^{\mathcal{O}(d)}\) samples — a bound that is essentially free of the curse of dimensionality, matching the optimal univariate rate up to polylogarithmic factors. Via a standard explore-then-commit reduction, this result already implies a \(\widetilde{\mathcal{O}}\left(T^{3/4}\right)\) regret bound for our class of functions in any fixed dimension. While this improves on the naive bound obtained by running a standard regret minimizer over a uniform grid whenever \(d\ge 3\), it falls short of breaking the \(\widetilde{\mathcal{O}}\left(T^{3/4}\right)\) barrier, and remains far from the \(\widetilde{\mathcal{O}}(T^{2/3})\) rate known to be tight in the univariate case. Dimension \(d=2\) is, in this sense, the least satisfying case: it is the only one in which the algorithm of [14] fails to improve at all over the trivial bound.
Whether the regret rate in multi-dimensional settings can be pushed below \(\widetilde{\mathcal{O}}(T^{3/4})\) was left open. We take a first step toward closing the gap between the upper bound \(\widetilde{\mathcal{O}}\left(T^{3/4}\right)\) and the lower bound \(\Omega\left(T^{2/3}\right)\) by designing a new algorithm for \(d=2\) that achieves regret \(\widetilde{\mathcal{O}}\left(T^{7/10}\right)\), disproving the conjecture that explore-then-commit is optimal for every \(d\ge 2\). We view this result as opening more questions than it closes. Is \(\widetilde{\mathcal{O}}\left(T^{7/10}\right)\) tight for \(d=2\), or is \(\widetilde{\mathcal{O}}\left(T^{2/3}\right)\) achievable? Can our approach be extended to arbitrary dimension, or does the \(\widetilde{\mathcal{O}}\left(T^{3/4}\right)\) barrier become tight for, say, \(d=3\)? We leave these as natural directions for future work.
1.1 Main Contributions↩︎
Our main contribution is a new algorithm for regret minimization with Lipschitz, CDF-dependent rewards in two dimensions that, for the first time, narrows the gap between the \(\tilde{\Omega}(T^{2/3})\) lower bound inherited from the univariate case [13], [15] and the trivial \(\tilde{O}(T^{3/4})\) upper bound achievable by running a standard multi-armed bandit algorithm over a uniform grid [1], [2].
Theorem 1 (Informal version of [thm:main]). There exists an algorithm that guarantees regret \(\tilde{\mathcal{O}}(T^{7/10})\) for reward functions of the form \(r(x)=g(x) \cdot \mathbb{P}_{X\sim \mathcal{D}} (X\le x)\) over \([0,1]^2\).
Crucially, this guarantee holds in the hardest possible stochastic setting: the learner receives only one bit of feedback per round (\(\mathbb{I}(X_t\le x_t)\)), and no assumption is made on the correlation or regularity of the underlying distribution \(\mathcal{D}\). Since bilateral trade is a special case of our framework, this theorem immediately yields an analogous improvement for fixed-price profit maximization in bilateral trade.
Corollary 1 (Informal version of 1). There exists an algorithm that guarantees regret \(\tilde{\mathcal{O}}(T^{7/10})\) for profit maximization in repeated bilateral trade with fixed prices and one-bit feedback.
Analogous results hold for the less-studied settings with two buyers (and no sellers) or two sellers (and no buyers). To the best of our knowledge, this is the first result to break the \(\widetilde{\mathcal{O}}(T^{3/4})\) barrier for fixed-price mechanisms in two dimensions, and the first evidence that the curse of dimensionality afflicting CDF-based regret minimization problems might be avoidable — much as it was shown to be absent in the sample-complexity setting by [14].
1.2 Challenges and Techniques↩︎
The starting point of our algorithm is the sample-complexity result of [14]. However, achieving \(o(T^{3/4})\) regret requires departing from the explore-then-commit framework intrinsic to that approach.
1.2.0.1 A Failed Approach: Uniform Approximation Over an Incomplete Grid.
The natural way to extend a sample complexity result and obtain optimal bounds is the general template of successive arm elimination. Time is partitioned into epochs of doubling length, and in epoch \(k\) we invoke the uniform CDF-estimation guarantee [14] at a target accuracy \(\epsilon_k\) that shrinks geometrically with \(k\), restricted to the current set of active grid points \(\mathcal{A}_k\) rather than the full domain, starting from a sufficiently fine uniform grid \(\mathcal{A}_0\). At the end of epoch \(k\), we eliminate every point whose upper confidence bound falls below the lower confidence bound of the best surviving point. Since every surviving point has true reward within \(O(\epsilon_k)\) of optimal, and recalling that the uniform approximation procedure requires \(\mathcal{O}(\epsilon_k^{-3})\) rounds (ignoring the size of the grid that appears only in polylogaritmic factors), the regret incurred during epoch \(k\) is at most \(O(\epsilon_k)\) times the length of the epoch, i.e., \({\mathcal{O}}(\epsilon_k^{-3})\). Since the final target accuracy is \(\epsilon\approx T^{-1/3}\), summing over all epochs would yield a regret bound of \(\widetilde{\mathcal{O}}(T^{2/3})\)!
Unfortunately, we do not have such a uniform exploration procedure on arbitrary subsets: the procedure of [14] works only on the full uniform grid, and extending it to an arbitrary subset of the grid is a non-trivial goal that we were not able to achieve. For this reason, we instead pursue a weaker result, relaxing the goal along several directions: we move from a logarithmic number of phases to a two-phase approach, we estimate differences between CDF values at pairs of points rather than the values themselves, and we compute such differences only between a restricted subset of point pairs.
1.2.0.2 Coarse Pruning via Uniform Approximation.
In the spirit of successive arm elimination by epochs, we run a single preliminary exploration round at coarse precision \(\Delta\). Since the initial grid is the full grid, we can directly apply the uniform approximation result [14]: this phase runs for \(\tilde{\mathcal{O}}(\Delta^{-3})\) rounds and incurs regret at most \(\tilde{\mathcal{O}}(\Delta^{-3})\), yielding a \(\Delta\)-approximation of the CDF uniformly over the whole grid.
1.2.0.3 Induced Graphs and Smoothing.
As discussed above, we cannot restrict to the set of \(\Delta\)-optimal points and perform uniform exploration over them efficiently. We can, however, use the coarse estimates to classify grid points by their approximate reward. Points whose estimated reward is far from the estimated optimum are discarded outright, since querying them would be too costly in regret. Points whose estimated reward is close to the estimated optimum are retained as candidates, since they might still be the true optimum. This leaves a third, intermediate class: points that are provably suboptimal, but only mildly so.
The natural instinct is to discard this intermediate class as well, since keeping suboptimal points seems only to inflate the size of the working grid. This intuition is wrong. Ideally, we would like to operate on the whole uniform grid, whereas the candidate set produced by the first pass is typically a sparse and irregularly shaped subset of it. Retaining some points from the intermediate class lets us improve the regularity of this subset.
We formalize regularity through an induced graph: informally, two points are connected if there exists an L-shaped path between them — a horizontal segment followed by a vertical one, or vice versa — that lies entirely within the incomplete grid. We decide whether to keep or discard each intermediate point so as to smooth this graph and increase its connectivity; technically, we aim to minimize the independence number of the resulting graph.
1.2.0.4 Relative Learning on an Incomplete Grid.
Rather than learning the CDF uniformly over the incomplete grid, we lower our ambition and instead learn the difference in CDF value between connected points up to a precision \(\epsilon\). Our procedure is inspired by [14], but requires new techniques. First, since queries are restricted to the incomplete grid, the binary search underlying [14] — which bisects intervals at their geometric midpoint — must be replaced with an index-based variant that only ever bisects at points present in the grid. Second, we show that the difference between two arbitrary grid points — not just the distance from a point to the origin — can still be decomposed into \(\mathcal{O}(\log K)\) dyadic sub-intervals; this extends the decomposition of [14], which applies only to intervals anchored at the origin, to intervals anchored at two arbitrary endpoints. Whenever the entire interval lies within the incomplete grid, we can recover such an approximation. Combining a horizontal segment with a vertical one then lets us approximate the difference \(D(x;y)\) between the CDFs of two connected points \(x\) and \(y\).
1.2.0.5 From Relative to Absolute CDF via Feedback Graphs with Misspecified Rewards.
The relative estimates from the previous step almost, but not quite, place us in a standard bandit-with-feedback-graph setting: pulling an arm \(x\) should reveal the reward of every neighboring arm \(y\) in the induced graph, via the relation \(r(y) =g(y)\left(\mathbb{P}_{X\sim \mathcal{D}}(X\le x)+D(x;y)\right)\). The catch is that \(D(x;y)\) is itself only known up to an additive error \(\epsilon\), so each inferred reward is biased, not exact — a setting not covered by existing feedback-graph analyses.
We address this by introducing and analyzing a general model of multi-armed bandits with feedback graphs and \(\epsilon\)-misspecified rewards, in which every edge of the graph carries a relation between the rewards of its endpoints, known only up to a uniform \(\epsilon\)-approximation. We design a UCB-style algorithm for this setting and, proceeding along the lines of the standard analysis, show that its regret scales as \(\tilde{\mathcal{O}}\left(\sqrt{\alpha(\mathcal{R})\,T} + \epsilon\,T\right)\), where \(\alpha(\mathcal{R})\) is the independence number of the feedback graph. This recovers the standard bound of the classical (unbiased) feedback-graph setting, while the bias of the relative estimates contributes only an additional, separable \(\mathcal{O}(\epsilon\,T)\) term to the regret. This result may be of independent interest beyond our application.
Balancing the coarse-pruning precision \(\Delta\) against the target accuracy \(\epsilon\) of the relative-learning phase completes the proof, yielding a total regret of \(\widetilde{\mathcal{O}}\left(T^{7/10}\right)\).
1.3 Related Works↩︎
Here, we review the lines of research most closely connected to our work.
1.3.0.1 GFT Maximization in Bilateral Trade.
Bilateral trade is a classical mechanism design problem modeling the exchange of a good between a buyer and a seller through an intermediary. Motivated by the impossibility of designing a mechanism that is simultaneously incentive compatible, individually rational, fully efficient, and budget balanced [16], a recent line of research studies how to learn optimal mechanisms in repeated bilateral trade. [3] initiated the study of regret minimization in this setting, focusing on the gain-from-trade (GFT) objective. A rich literature extends these results along many directions, providing a complete characterization of the setting [8]–[10], [17]–[22]. Interestingly, most of these works establish \(\widetilde{\mathcal{O}}\left(T^{3/4}\right)\) regret bounds, showing that gain-from-trade maximization also suffers from a curse of dimensionality. It is important to remark, however, that this arises for reasons quite different from ours, stemming from the absence of bandit feedback and from connections to the apple-tasting problem.
1.3.0.2 Profit Maximization in Bilateral Trade.
Until recently, the profit-maximization problem had received comparatively little attention. [11], [12] study the problem of maximizing profit in repeated bilateral trade, but with general mechanisms. Their setting and results are conceptually quite different from ours: the main challenge in learning a fixed price is limited feedback, whereas with general mechanisms the learner has full feedback but a huge action set. Their main results establish a \(\widetilde{\mathcal{O}}\left(\sqrt{T}\right)\) regret bound in the stochastic setting, and an analogous bound against a smoothed adversary, respectively.
1.3.0.3 CDF Learning and Pricing.
A parallel line of work studies the problem of estimating a CDF from limited feedback, motivated by applications to dynamic pricing. In the simpler dynamic pricing problem, the learner repeatedly posts a price and observes only whether a buyer accepts it, which is equivalent to querying the CDF of the buyer’s value distribution at a single point per round. Most work on this topic is one-dimensional; the most relevant result for us is the characterization of the optimal sample-complexity bound \(\Theta\left(\epsilon^{-3}\right)\) and the corresponding optimal regret bound \(\Theta(T^{2/3})\) [13], [15]. More recently, [14] study the sample complexity of learning a CDF uniformly over an arbitrary fine grid, providing a bound of \(\epsilon^{-3}\log(K)^{\mathcal{O}(d)}\) samples, where \(d\) is the number of dimensions. This yields applications to pricing with multiple buyers and/or sellers, including bilateral trade. Their result can also be extended to a regret bound via a standard explore-then-commit approach, yielding \(\widetilde{\mathcal{O}}(T^{3/4})\) regret — the first non-trivial bound in this direction.
2 Preliminaries↩︎
We study regret minimization over the decision space \([0,1]^2\), where rewards are defined through the cumulative distribution function (CDF) of an unknown probability distribution. Let \(\mathcal{D}\) be a probability distribution supported on \([0,1]^2\). Its CDF is the function \(F:[0,1]^2\to[0,1]\) defined by \[F(x) \coloneq \mathbb{P}_{X\sim \mathcal{D}}(X\le x),\] where the inequality holds component-wise. Let \(g : [0,1]^2 \to [-1,1]\) be a known \(1\)-Lipschitz function with respect to the \(\ell_1\)-norm,2 i.e., satisfying \(|g(x)-g(y)| \le \|x-y\|_1\) for every \(x, y \in [0,1]^2\).
The learner interacts with the environment over \(T \in \mathbb{N}\) rounds. At each round \(t \in [T]\),3 the learner selects a point \(x_t \in [0,1]^2\), the environment independently draws a sample \(X_t \sim \mathcal{D}\), and the learner receives a reward \(r_t(x_t)\) determined by a reward function \(r_t : [0,1]^2 \to [-1,1]\) defined by: \[r_t(x) \coloneq g(x) \cdot \mathbb{I}(X_t\le x).\] Finally, the learner observes the single bit: \[\mathbb{I}(X_t\le x_t).\] Note that, while \(g\) is known to the learner, the distribution \(\mathcal{D}\) is not. Crucially, the single observed bit \(\mathbb{I}(X_t \le x_t)\) contains enough information to learn \(F\), whereas it would be uninformative about \(g\). The learner’s goal is to minimize its (cumulative) regret over the \(T\) rounds, defined as: \[R_T \coloneq \max_{x\in [0,1]^2} \mathbb{E}\left[\sum_{t=1}^T r_t(x)-\sum_{t=1}^T r_t(x_t)\right].\]
2.1 Fixed-Price Mechanisms and Profit Maximization in Bilateral Trade↩︎
A canonical class of problems captured by our framework is profit maximization in repeated posted-price problems. In the classical model of [13], the learner (seller) posts a price \(p_t \in [0,1]\) to a single buyer, who accepts to buy if their valuation \(V_t \in [0,1]\) exceeds \(p_t\), yielding profit \(p_t\) to the learner. This is an instance of our framework with \(x_t=1-p_t\), \(g(x)=1-x\) and \(X_t=1-V_t\), so that \(g(x)=p_t\) and \(\mathbb{I}(X_t \le x_t) = \mathbb{I}(V_t \ge p_t)\). It is well known that, in this one-dimensional problem, a minimax regret bound of \(\widetilde{\Theta}(T^{2/3})\) can be achieved [13].
A natural two-dimensional generalization of this problem arises in profit-maximization settings involving two agents (buyers and/or sellers), among which bilateral trade is perhaps the most prominent and influential model [3]. At each round \(t \in [T]\), a new buyer and a new seller arrive, each with a private valuation for the indivisible item to be exchanged, denoted by \(B_t \in [0,1]\) and \(S_t\in [0,1]\), respectively. The learner then proposes two prices, \(p_t \in [0,1]\) to the seller and \(q_t \in [0,1]\) to the buyer. Both the seller and the buyer may decide whether to accept the proposed trade. A trade occurs if and only if \(S_t \le p_t\) and \(B_t \ge q_t\), in which case the learner obtains profit \(q_t - p_t\). The goal of the learner is to maximize cumulative profit.
By setting \[X_t=(S_t,1-B_t), \quad x_t=(p_t,1-q_t), \quad \textrm{and}\quad g(x_1,x_2)=1- x_1-x_2,\] we embed this problem in our framework, since \(g(x_t)=q_t-p_t\) and \(\mathbb{I}(X_t\le x_t)=\mathbb{I}(S_t\le p_t,\,B_t\ge q_t)\).
2.2 Grids and Their Induced Graphs↩︎
In this paper, we work extensively with uniform grids defined over \([0,1]^2\) and graphs induced by subsets thereof. Given any \(K \in \mathbb{N}\), we define the one-dimensional uniform grid \[G^U(K) \coloneq \left\{\frac{i}{K-1} \mid i \in \{0,\ldots, K-1\}\right\},\] and the two-dimensional uniform grid \[\mathcal{G}^U(K) \coloneq G^U(K)\times G^U(K).\]
We also work with segments connecting points on the grid \(\mathcal{G}^U(K)\). Given \(a,b \in [0,1]\), for ease of notation we define the interval \[I(a,b)\coloneq ( \min\{a,b\},\max\{a,b\} ]\] so that the notation is symmetric in \(a\) and \(b\), namely \(I(a,b) = I(b,a)\). Given two points \(x = (x_1,x_2), y = (y_1,y_2) \in \mathcal{G}^U(K)\) that share one coordinate (i.e., either \(x_1 = y_1\) or \(x_2= y_2\)), we define the segment connecting them as the set \(\mathfrak{I}(x,y) \subseteq \mathcal{G}^U(K)\) of grid points lying on the axis-parallel line connecting them: \[\mathfrak{I}(x,y) \coloneq \begin{cases} \left( x_1\times I(x_2,y_2) \right) \cap \mathcal{G}^U(K) \quad \text{if } x_1=y_1 \\ \left( I(x_1,y_1) \times x_2 \right) \cap \mathcal{G}^U(K) \quad \text{if }x_2=y_2, \end{cases}\] where we ignore the dependency on \(K\) since it will be clear from context. Notice that the segment \(\mathfrak{I}(x,y)\) is well defined only when \(x\) and \(y\) share one coordinate.
Given two points \(x=(x_1,x_2),y=(y_1,y_2) \in \mathcal{G}^U(K)\), we define the set of “corner-points” as \[\begin{align} \label{eq:corner} T(x,y)\coloneq\{(x_1,y_2),(y_1,x_2)\}, \end{align}\tag{1}\] each of which connects the two points through a triangular structure. Each element of \(T(x,y)\) is axis-aligned with both \(x\) and \(y\), so that the two segments forming an L-shaped path from \(x\) to \(y\) through a corner \(z\in T(x,y)\) are both well defined.
Then, we are finally ready to define the graph induced by a grid \(\mathcal{G}\): two points \(x,y \in \mathcal{G}\) are connected if there exists an L-shaped path through a corner \(z\in T(x,y)\) which stays entirely within \(\mathcal{G}\). Formally:
Definition 1. Given a subset of the uniform grid \(\mathcal{G}\subseteq \mathcal{G}^U(K)\), the induced graph \(\mathcal{R}(\mathcal{G})\) has vertex set \(\mathcal{G}\) and contains an edge between \(x \in \mathcal{G}\) and \(y \in \mathcal{G}\) if and only if there is a corner \(z \in T(x,y)\) such that: \[\mathfrak{I}(x,z)\cup \mathfrak{I}(y,z)\subseteq \mathcal{G}.\]
1 illustrates several examples of edges and non-edges. A key quantity throughout the paper is the independence number \(\alpha(\mathcal{R}(\mathcal{G}))\), defined as the size of a largest independent set in \(\mathcal{R}(\mathcal{G})\).
2.3 Basics on Probability Estimation and Uniform Learning↩︎
We rely on two procedures that have been recently introduced in [14]. The first procedure, which we call \(\textsf{Estimate}\) and which is called \(\mathrm{\small MCE}\) in [14], estimates the probability mass of an axis-aligned rectangle.
lemmalemmaCastiglioni[Lemma 4.2 in [14]] There exists an algorithm that, given a confidence \(\delta\in(0,1)\) and an axis-aligned rectangle \((a,b]\times[0,w]\subseteq[0,1]^2\), uses at most \(1/\epsilon^2\) rounds4 and outputs \(\widehat{P}((a,b]\times[0,w])\) such that, with probability at least \(1-\delta\): \[\bigl|\widehat{P}((a,b]\times[0,w]) -\mathbb{P}_{X\sim\mathcal{D}}(X\in(a,b]\times[0,w])\bigr| \;\le\; 2\epsilon\sqrt{\tfrac{1}{2}\ln\tfrac{2}{\delta}}.\]
The second procedure is the main result of [14]: a uniform learning procedure, which we call UniformCDF, that simultaneously estimates the CDF at every point of a grid.
Theorem 1 (Bi-dimensional Case of Theorem 3.1 in [14]). There exists an algorithm that, given an accuracy \(\Delta > 0\), a confidence \(\delta \in (0,1)\), and a uniform grid \(\mathcal{G}^U(K)\) over \([0,1]^2\) of resolution \(1 / K\) (with \(K \in \mathbb{N}\)), uses at most \(\frac{1}{\Delta^3}\log(K/\delta)^{\mathcal{O}(1)}\) rounds and outputs a function \(\widetilde{P}: \mathcal{G}^U(K) \to [0,1]\) such that, with probability at least \(1-\delta\), the following holds: \[\left|\mathbb{P}_{X \sim \mathcal{D}}(X \le x )-\widetilde{P}(x)\right|\le \Delta \quad \forall x \in \mathcal{G}^U(K).\]
3 Main Results and Proof Plan↩︎
The main contribution of this paper is the following theorem.
theoremthmmain Let \(\{X_t\}\) be i.i.d. samples in \([0,1]^2\). There exists an algorithm that guarantees \[R_T= \widetilde{\mathcal{O}}\left( T^{\frac{7}{10}}\right).\]
Since bilateral trade is a special case of our framework (see 2.1), [thm:main] immediately yields the following.
Corollary 1. There exists an algorithm for profit maximization in repeated bilateral trade that guarantees \[R_T= \widetilde{\mathcal{O}}\left( T^{\frac{7}{10}}\right).\]
The rest of the paper is devoted to proving [thm:main]. The algorithm proceeds in three sequential phases, summarized in 2, and its design is guided by the following core tension.
To minimize the regret we face two competing objectives: we want the working grid \(\mathcal{G}\) to be as dense as possible, so that the uniform exploration in the spirit of [14] can be applied efficiently and the optimal \(\tilde{O}(1/\epsilon^3)\) sample complexity is achieved; but we also want \(\mathcal{G}\) to contain only points that are not too suboptimal, since every query to a too suboptimal point incurs a large per-round regret. The three phases resolve this tension by finding the right compromise between this contrasting goals.
3.0.0.1 Phase 1 — Coarse Pruning via Uniform Approximation.
We run \(\mathrm{\small UniformCDF}(\mathcal{G}^U(K), \Delta, \delta)\) (1) at a low precision \(\Delta\), obtaining a uniform approximation \(\widehat{F}\) of the CDF over \(\mathcal{G}^U(K)\) at a cost of \(\widetilde{\mathcal{O}}(1/\Delta^3)\) queries (and hence at most \(\widetilde{\mathcal{O}}(1/\Delta^3)\) regret). Note that this approximation alone is clearly not sufficient to break the \(\tilde{O}(T^{3/4})\) barrier: running this phase alone with \(\Delta = T^{-1/4}\) already yields \(\widetilde{\mathcal{O}}(T^{3/4})\) regret via a standard explore-then-commit argument. Our improvement instead comes from choosing a much larger \(\Delta\) and using this phase only to obtain a rough approximation.
3.0.0.2 Processing Step — Building a Highly-Connected Graph Through Smoothing.
The previous step leaves us with three classes of points: candidate optima \(\mathcal{G}^{\textsf{OPT}}\), which must be kept for the following phase; clearly suboptimal points, which must be removed since querying them would incur large per-round regret; and a remaining set of borderline points, which are not suboptimal enough to require removal, but whose inclusion is optional. Since our goal is simply to minimize the independence number of \(\mathcal{G}^\textsf{OPT}\),the optimal approach is straightforward: we improve the connectivity by considering a graph \(\mathcal{G}\) that keeps all borderline points that help connect points in \(\mathcal{G}^{\textsf{OPT}}\), discard the rest, and then consider only the subgraph \(\mathcal{R}^\textsf{OPT}\) induced by the vertexes \(\mathcal{G}^\textsf{OPT}\). Overall, this procedure can be seen as a smoothing of the graph and grid that removes “sharp,” isolated components (see Figure 3).
3.0.0.3 Phase 2 — Relative Learning on an Incomplete Grid.
So far, we have only used the notion of connectivity to build a well-connected graph, on the promise that learning would be easier for more connected graphs. We now put this connectivity to use. Rather than estimating the CDF at each point of \(\mathcal{G}\) individually, we instead estimate only the relative differences \[D(x;y)= F(y)-F(x)\] between pairs of points connected in \(\mathcal{R}(\mathcal{G})\). The procedure \(\mathrm{\small RLS}\) (6) outputs estimates \(\widehat{D}(x;y)\) for all edges \((x,y)\in\mathcal{R}(\mathcal{G})\) satisfying, with high probability, \[\bigl|\widehat{D}(x;y) - D(x;y)\bigr| \le \epsilon \qquad\forall\,(x,y)\in\mathcal{R}(\mathcal{G}),\] using only \(\tilde{O}(1/\epsilon^3)\) queries in total — independently of \(|\mathcal{G}|\). To do so, it first estimates the distance between axis-aligned points, and then exploits the \(L\)-shaped structure of edges in \(\mathcal{R}(\mathcal{G})\) to extend these estimates to all edges.
3.0.0.4 Phase 3 — Multi-Armed Bandits with Feedback Graph and \(\epsilon\)-Misspecified Rewards.
The estimates \(\widehat{D}\) from Phase 2 turn \(\mathcal{R}^\textsf{OPT}\) into a feedback graph with \(\epsilon\)-misspecified rewards: querying a point \(x\) yields a slightly biased estimator of the reward of every neighbor \(y\) of \(x\) in \(\mathcal{R}^\textsf{OPT}\). We design a UCB-style algorithm (13) for this misspecified setting and show that its regret scales as \[\tilde{\mathcal{O}}\!\left(\sqrt{\alpha(\mathcal{R}^\textsf{OPT})\,T} + \epsilon\, T\right),\] replacing the usual dependence on the number of arms with the independence number of the feedback graph, at the cost of an additional \(\epsilon\) per-round regret due to the bias.
4 Build a Highly-Connected Graph Through Smoothing↩︎
At a high level, the goal of this section is to build an incomplete grid \(\mathcal{G}\subseteq \mathcal{G}^U(1/\epsilon)\) that is highly connected and does not contain highly suboptimal points.
Our algorithm is presented in 4 and works as follows. For each point \(x\in \mathcal{G}^U(1/\epsilon)\), it computes the estimated reward \[\tilde{r}(x)\mathrel{\vcenter{:}}= g(x) \hat{F}(x),\] and defines \(\widetilde{\textsf{OPT}} \coloneq \max_{x\in \mathcal{G}^U(1/\epsilon)}\tilde{r}(x)\) as the estimated optimal reward.
Since we do not want to remove the optimal solution from our final grid \(\mathcal{G}\), we need to keep all points that we cannot rule out as optimal, defined as \[\mathcal{G}^{\textsf{OPT}}\mathrel{\vcenter{:}}= \{ x\in \mathcal{G}^U(1/\epsilon): \tilde{r}(x)\ge \widetilde{\textsf{OPT}} - 2\Delta\}.\] We then observe that it is also safe to add points to the final graph \(\mathcal{G}\), provided they are at most \(O(\Delta)\)-suboptimal and improve connectivity. Given a set \(\mathcal{G}'\), we let \[\tilde{r}(\mathcal{G}')\mathrel{\vcenter{:}}= \min_{x \in \mathcal{G}'} \tilde{r}(x).\]
Starting from \(\mathcal{G}=\mathcal{G}^{\textsf{OPT}}\), we iterate over all pairs \(x,y \in \mathcal{G}^\textsf{OPT}\) and attempt to connect them: this is possible whenever there exists an \(L\)-shaped path connecting \(x\) and \(y\) that is at most \(6\Delta\)-suboptimal with respect to the estimated \(\tilde{r}\), in which case we add both segments of the path to \(\mathcal{G}\). Figure 3 shows an example of this procedure.
We proceed to analyze the guarantees of the algorithm, which rely on the following clean event.
Definition 2 (Clean Event \(E_0\)). We say the clean event \(E_0\) holds if \[\max_{x\in\mathcal{G}^U(K)}|\widehat{F}(x)-F(x)|\le\Delta.\]
We now show that, under \(E_0\), \(\mathcal{G}^\textsf{OPT}\) (and hence \(\mathcal{G}\)) contains the optimum, and that \(\mathcal{G}\) contains only \(O(\Delta)\)-suboptimal points.
Lemma 1. Let \(\textsf{OPT}\mathrel{\vcenter{:}}= \max_{x\in\mathcal{G}^U(1/\epsilon)} g(x)F(x)\) denote the true optimal value. Under the clean event \(E_0\), it holds that \[\max_{x \in \mathcal{G}^\textsf{OPT}} g(x) F(x) = \textsf{OPT}\] and \[g(x) F(x) \ge \textsf{OPT}- 8 \Delta \quad \forall x \in \mathcal{G}.\]
Proof. Let \(\widetilde{x}^*\) and \(x^*\) be such that \[\begin{align} \widetilde{x}^* \in \arg \max_{x\in \mathcal{G}^U(1/\epsilon)}\;g(x)\hat{F}(x), \\ x^* \in \arg \max_{x\in \mathcal{G}^U(1/\epsilon)}\;g(x){F}(x). \end{align}\] For every \(x\in \mathcal{G}\) we have \(g(x)\hat{F}(x)\ge \widetilde{\textsf{OPT}}-6\Delta\) by construction, which implies \[\begin{align} g(x)F(x)&\ge g(x)(F(x)-\hat{F}(x))+ g(x)\hat{F}(x)\ge -|F(x)-\hat{F}(x)| + \widetilde{\textsf{OPT}}-6\Delta\\ & \ge -\Delta + g(\widetilde{x}^*)\hat{F}(\widetilde{x}^*)-6\Delta \\ &\ge g(x^*)\hat{F}(x^*)-7\Delta\\ &= g(x^*)(\hat{F}(x^*)-F(x^*))+ g(x^*)F(x^*)-7\Delta\\ & \ge \textsf{OPT}- 8\Delta. \end{align}\] This proves the second part of the statement.
Additionally, for every \(x\notin \mathcal{G}^{\textsf{OPT}}\) we have that either \(g(x)\hat{F}(x)< \widetilde{\textsf{OPT}}-2\Delta\) or \(g(x)<0\) and there exists \(y\in \mathcal{G}^\textsf{OPT}\) such that \(g(y)\ge 0\). If the latter condition is verified, it is immediate to observe that \(\textsf{OPT}\ge g(y)F(y)\ge 0 \ge g(x)F(x)\), and if the first condition is verified we have
\[\begin{align} g(x)F(x)&= g(x)(F(x)-\hat{F}(x))+ g(x)\hat{F}(x)< |F(x)-\hat{F}(x)| + \widetilde{\textsf{OPT}}-2\Delta\\ & \le \Delta + g(\widetilde{x}^*)\hat{F}(\widetilde{x}^*)-2\Delta\\ &= g(\widetilde{x}^*)(\hat{F}(\widetilde{x}^*)-F(\widetilde{x}^*))+ g(\widetilde{x}^*)F(\widetilde{x}^*)-\Delta\\ & \le g(\widetilde{x}^*)F(\widetilde{x}^*)\\ &\le \textsf{OPT}, \end{align}\] which shows that \(x^*\in \mathcal{G}^\textsf{OPT}\) for at least one possible choice of \(x^*\) and proves the first part of the statement. ◻
![Figure 5: Analysis of the two cases in the proof of [lemma:32E0], with g(x)\ge 0, for all x\in \mathcal{G}^\textsf{OPT}. In the first, there are two possible L-paths which follow the Lipschitz direction, in the second just one.](/article/2607.20258/_pdflatex/cdogtasu.png "fig:")
We now show that the graph is highly connected. Since we known that the optimal point belong to \(\mathcal{G}^\textsf{OPT}\), we just care about the connectivity of the graph restricted to this node. Formally, we define the subgraph which consists of the vertices \(\mathcal{G}^\textsf{OPT}\) and all edges from \(\mathcal{R}(\mathcal{G})\) that have both endpoints in \(\mathcal{G}^\textsf{OPT}\).
Definition 3 (Subgraph \(\mathcal{R}^\textsf{OPT}\)). Let \(\mathcal{R}(\mathcal{G})\) be the graph induced by \(\mathcal{G}\) as per 1. We define \(\mathcal{R}^\textsf{OPT}\) as the subgraph of \(\mathcal{R}(\mathcal{G})\) induced by the vertex set \(\mathcal{G}^\textsf{OPT}\).
Then, we show that the subgraph induced by the vertex set \(\mathcal{G}^\textsf{OPT}\) has a small independence number. Intuitively, we focus on \(\mathcal{G}^\textsf{OPT}\) because this set contains the optimum under the clean event \(E_0\); the remaining points in \(\mathcal{G} \setminus \mathcal{G}^\textsf{OPT}\) serve only to improve the connectivity between points within \(\mathcal{G}^\textsf{OPT}\) (according to 1).
Intuitively, our proof works as follows. Consider two points \(x, y \in \mathcal{G}^\textsf{OPT}\) at a distance of at most \(\Delta\). By the one-sided Lipschitz property of the objective, these points can be connected via two consecutive axis-aligned segments—one horizontal and one vertical—forming an \(L\)-shaped path whose orientation depends on the relative positions of \(x\) and \(y\) (see Figure 5). Given the one-sided Lipschitz property, the objective value decreases by at most \(\Delta\) along each segment; consequently, both segments consist of \(\mathcal{O}(\Delta)\)-suboptimal points. The argument is completed by a covering argument, which shows there are at most \(\mathcal{O}(1/\Delta^2)\) such non-connected elements. Formally,
Lemma 2. Under the clean event \(E_0\), the graph \(\mathcal{R}^\textsf{OPT}\) has independent number \[\alpha(\mathcal{R}^\textsf{OPT}) \le \mathcal{O}\left(\frac{1}{\Delta^2}\right).\]
Proof. Suppose the clean event \(E_0\) holds. We split the analysis in two cases:
\(\exists x\in \mathcal{G}^\textsf{OPT}: g(x)\ge 0\), and therefore \(g(x)\ge 0 \;\forall x\in \mathcal{G}^\textsf{OPT}\)
\(\nexists x\in \mathcal{G}^\textsf{OPT}: g(x)\ge 0\), and therefore \(g(x)< 0 \;\forall x\in \mathcal{G}^\textsf{OPT}\).
We start by studying the first case.
Consider a point \(x=(x_1,x_2)\in \mathcal{G}^\textsf{OPT}\), so that \(g(x)\hat{F}(x)\ge \widetilde{\textsf{OPT}}-2\Delta\). Then, by the Lipschitzness of \(g(\cdot)\), any point \(y\) in \[Q_x \mathrel{\vcenter{:}}= [x_1,x_1+\Delta]\times [x_2,x_2+\Delta]\cap \mathcal{G}^U(1/\epsilon)\] satisfies \(g(y)\hat{F}(y)\ge \widetilde{\textsf{OPT}}-6\Delta\). Indeed, \[\begin{align} \widetilde{\textsf{OPT}}-2\Delta&\le g(x)\hat{F}(x)\\ &\le g(x)F(x)+\Delta \\ &\le g(x)F(y)+\Delta\\ &\le (g(x)-g(y))F(y)+g(y)F(y)+\Delta\\ & \le \lVert x-y\rVert_1+ g(y)(F(y)-\hat{F}(y))+g(y)\hat{F}(y)+\Delta\\ & \le g(y)\hat{F}(y)+4\Delta, \end{align}\] where we used the definition of the clean event \(E_0\), \(g(x)\ge0\), \(F(y)\le 1\), \(F(x)\le F(y)\), the \(1\)-Lipschitzness of \(g\) and \(\lVert x-y\rVert_1\le 2\Delta\).
We now prove that any two points \(x,y\in \mathcal{G}^\textsf{OPT}\) are connected in \(\mathcal{G}\) if \(\lVert x-y\rVert_\infty\le \Delta\). There are two possible cases:
either \(x\le y\) or \(y\le x\) holds component-wise;
both \(x\nleq y\) and \(y\nleq x\).
Let us consider the first case and, without loss of generality, assume \(x\le y\). Then \(y\in Q_x\), and therefore for any \(z\in T(x,y)\), both \(\mathfrak{I}(z,x)\) and \(\mathfrak{I}(z,y)\) are contained in \(Q_x\), which means that for every choice of \(z\in T(x,y)\) it holds \(\tilde{r}(\mathfrak{I}(x,z)\cup \mathfrak{I}(y,z))\ge \widetilde{\textsf{OPT}}-6\Delta\), and \(x\) and \(y\) are connected in \(\mathcal{G}\).
Let us now consider the second case, and, without loss of generality, assume \(x_1<y_1\) and \(y_2<x_2\). If we define \(z\in T(x,y)\) as \(z=(y_1,x_2)\), then \(\mathfrak{I}(x,z)\in Q_x\) and \(\mathfrak{I}(z,y)\in Q_y\), and means that for this choice of \(z\) we have \(\tilde{r}(\mathfrak{I}(x,z)\cup \mathfrak{I}(y,z))\ge \widetilde{\textsf{OPT}}-6\Delta\), and \(x\) and \(y\) are connected in \(\mathcal{G}\).
Hence, for any pair of points \(x,y\in \mathcal{G}^\textsf{OPT}\) such that \(\lVert x-y\rVert_\infty\le \Delta\), there always exists \(z \in T(x,y)\) such that \(\tilde{r}(\mathfrak{I}(x,z)\cup \mathfrak{I}(y,z)) \ge \widetilde{\textsf{OPT}}-6\Delta\).
Therefore, we have proven that any two points in \(\mathcal{G}^\textsf{OPT}\) whose \(\ell_\infty\) distance is at most \(\Delta\) are connected. The independence number restricted to graph \(\mathcal{R}^\textsf{OPT}\) is therefore upper-bounded by the maximum number of pairwise disjoint \(\ell_\infty\)-balls of radius \(\Delta\) that can simultaneously fit in \([0,1]\times[0,1]\), which is \(\mathcal{O}\left(\frac{1}{\Delta^2}\right)\).
Finally, to conclude the proof we consider the case in which \(g(x)<0\) for all \(x\in \mathcal{G}^\textsf{OPT}\). The analysis here is specular to the one above, namely, defining for any \(x\in \mathcal{G}^\textsf{OPT}\) \[Q^-_x \mathrel{\vcenter{:}}= [x_1-\Delta,x_1]\times [x_2-\Delta,x_2]\cap \mathcal{G}^U(1/\epsilon)\] we can prove that any \(y\in \mathcal{G}^\textsf{OPT}\cap Q^-_x\) is directly connected to \(x\) in \(\mathcal{R}(\mathcal{G})\). Indeed, similarly to before
\[\begin{align} \widetilde{\textsf{OPT}}-2\Delta&\le g(x)\hat{F}(x)\\ &\le g(x)F(x)+\Delta \\ &\le g(x)F(y)+\Delta\\ & \le g(y)\hat{F}(y)+4\Delta, \end{align}\] where we used the fact that \(F(y)\le F(x)\) and \(g(x)<0\).
By adapting the choice of \(z\in T(x,y)\) to the new notion of \(Q^-_x\), we can retrieve the desired guarantee even in this case, following the same steps above. ◻
5 Relative Learning on an Incomplete Grid↩︎
In this section we address the following question: given a grid \(\mathcal{G}\subseteq\mathcal{G}^U(K)\), how can we approximate the distance function \(D(x;y)=F(y)-F(x)\) using as few queries as possible, while restricting all queried points to \(\mathcal{G}\)?
When \(\mathcal{G}=\mathcal{G}^U(K)\) is the complete grid, this problem is already solved by [14]: estimating \(D\) over the full grid is equivalent to estimating \(F\) itself, which costs \(\frac{1}{\epsilon^3}\log(K/\delta\epsilon)^{\mathcal{O}(1)}\) queries. However, this procedure does not extend to an arbitrary incomplete grid \(\mathcal{G}\). Its binary search routines implicitly assume that every point on the path between two queried locations is itself available to query, which fails as soon as \(\mathcal{G}\) contains holes.
We therefore relax the goal: rather than estimating \(F\) at every point of \(\mathcal{G}\), we only estimate \(D(x;y)\) for pairs \(x,y\) that are directly connected in \(\mathcal{R}(\mathcal{G})\). Our procedure is presented in 6. First, we replace the standard distance-based binary search of [14] — which bisects an interval at its geometric midpoint — with an index-based binary search BinS that only bisects at points already present in \(\mathcal{G}\) (8). We perform this binary search both on the horizontal (\(H\)) and vertical (\(V\)) axis. The output of this procedure provides estimation of the probability that \(X\sim \mathcal{D}\) falls in some rectangles (see 5.1).
Then, we need to use such estimates to approximate the distance between connected points using function Estimate-Construction. We perform this step in two phases. First, we show that any segment \((a,b] \times c\) (or \(c\times [a,b])\) can be decomposed into \(O(\log K)\) dyadic sub-intervals for which the index-based search has already produced estimates, allowing us to assemble \(\widehat{D}(x;y)\) by summing the probability of the \(O(\log K)\) added areas (see 5.2). Finally, we extend this distance estimates to general edges by recalling that they are the sum of (at most) two \(L\)-shaped segments (5.3).
5.1 From Distance-Based Binary Search to Index-Based Binary Search↩︎
By symmetry between the two coordinates, we present all procedures along a single axis — specifically, the vertical-axis — as extending the procedure to the other axis is straightforward.
The pseudo-code for this procedure is detailed in 8. First, fix a column pair \(a, b \in G^U(K)\) and let \[\mathcal{W}=\{w_0<w_1<\cdots<w_M\}\coloneq \left\{w\in G^U(K):(a,w),(b,w)\in\mathcal{G}\right\}\] be the set of rows where both \((a,\cdot)\) and \((b,\cdot)\) are present in \(\mathcal{G}\) (see Figure 7). Our goal is to estimate \(\mathbb{P}\bigl((a,b]\times[0,w]\bigr)\) for every \(w \in \mathcal{W}\) using a number of queries that scales with the total probability mass of \((a,b]\times[0,1]\) rather than with \(M\).
The key insight is to perform a binary search over the indices of \(\mathcal{W}\) rather than the geometric midpoints of \([0,1]\). Given a range \([w_i, w_j]\), we split at the median index \(w_k\) where \(k = \lfloor(i+j)/2\rfloor\). By construction, every queried row is guaranteed to belong to \(\mathcal{W}\). We then recurse only into sub-ranges that carry non-negligible probability mass. This strategy guarantees that the total number of \(\mathrm{\small Estimate}\) calls is governed by the mass of \((a,b]\times[0,1]\) and almost independent of the grid resolution \(K\).
Let \(\mathrm{\small Extremes}(\mathcal{I})\) denote the union of the endpoints of all intervals in a collection \(\mathcal{I}\). Adapting the analysis of [14] to be index-based, we get the following guarantees on the resulting partition.
lemmalemmaBINS[Adapted from [14]] With probability at least \(1-\delta\), the partition \(\mathcal{I}\) returned by 8 satisfies the following three properties.
For every \(w_i\in \textrm{\mathrm{\small Extremes}}(\mathcal{I})\) of an interval in \(\mathcal{I}\), it holds: \[\left| \widehat{P}((a,b]\times [0,w_i])-\mathbb{P}(X\in (a,b]\times [0,w_i])\right|\le \epsilon \, 2\; \sqrt{\frac{\ln(\frac{4K}{\delta})}{2}} .\]
For every interval \(I \in \mathcal{I}\) such that \(I = (w_i, w_j]\), it holds: \[\mathbb{P}({X} \in [a,b] \times I) \le \epsilon+\epsilon \, 2^{3} \; \sqrt{\frac{\ln(\frac{4K}{\delta})}{2}} \quad \bigvee \quad w_{i+1}= w_j\]
The cardinality of \(\mathcal{I}\) satisfies: \[|\mathcal{I}| \le \frac{2 \mathbb{P}_{X\sim \mathcal{D}}(X \in (a,b]\times [0,1])\log_2 K}{\epsilon} +2.\]
Moreover, 8 uses at most \(\frac{1}{\epsilon^2}|\mathcal{I}|\) queries.
Intuitively, the lemma establishes three key properties:
Every endpoint produced by the recursion carries an \(\epsilon\)-accurate probability estimate.
Every leaf interval either contains negligible probability mass or corresponds to two adjacent rows of \(\mathcal{W}\) that cannot be split further.
The total number of leaves — and consequently, the total number of \(\mathrm{\small Estimate}\) calls — scales with the probability mass of the column \((a,b]\) rather than the grid resolution \(K\).
Because 8 only computes estimates at rows within \(\mathrm{\small Extremes}(\mathcal{I})\), querying an arbitrary row \(w \in \mathcal{W}\) requires interpolating between the two extremes of the interval containing \(w\). This interpolation is handled by the Compute-Prob procedure (9). By [thm:binS], the total probability mass fluctuates by at most \(\epsilon\) between these two extremes; thus, the interpolated probability is guaranteed to remain \(\epsilon\)-accurate.
Lemma 3. Let \((a,b]\) be the input to 8 and \(\hat{P}\) be the computed estimation function. Then, with probability at least \(1-\delta\), for any \(w\) such that \((a,w),(b,w)\in \mathcal{G}\), it holds: \[\begin{align} \left|\mathbb{P}((a,b]\times [0,w])-\frac{\hat{P}((a,b]\times [0,w_1])+\hat{P}((a,b]\times [0,w_2])}{2}\right|\le \frac{\epsilon+\epsilon \, 2^{3} \; \sqrt{\frac{\ln(\frac{4K}{\delta})}{2}}}{2} \end{align}\]
Crucially, Compute-Prob can only be applied to columns \((a,b]\) for which BinS has been executed. Consequently, it remains to determine exactly which columns and rows should undergo the BinS procedure. In the next section, we show that there exists a small set of columns \(\mathcal{I}^\star\) (on which we will run Compute-Prob) such that every distance between two columns can be decomposed into a logarithmic number of columns in \(\mathcal{I}^\star\).
5.2 Decomposing the Distance in Logarithmic Components↩︎
![Figure 10: Representation of the interval (x,y) in \mathcal{I}^\star, the orange interval is the largest one (a',b'], the anchor, the blue interval represent the decomposition (a, a'] and the green one the decomposition (b', b]](/article/2607.20258/_pdflatex/hrmjbxey.png "fig:")
While [thm:binS] provides \(\epsilon\)-accurate estimates of \(\mathbb{P}((a,b]\times[0,w])\), it only applies to column intervals \((a,b]\) for which BinS has explicitly been executed. Running BinS on every possible pair of grid columns is computationally prohibitive. To bypass this bottleneck, we exploit a dyadic structure. A key insight in the analysis of [14] is that any interval can be decomposed into \(O(\log K)\) dyadic pieces whose sizes are powers of two. We show that a similar decomposition applies to the difference between two arbitrary grid points rather than just the distance from a single point to the origin. This extends the framework of [14] — which is restricted to intervals of the form \([0,a]\) — to arbitrary intervals \([a,b]\).
We define the set \(\mathcal{I}^\star\) on which the procedures bins will be run (both on the horizontal and vertical axis: \[\begin{align} \label{eq:Istar} \mathcal{I}^\star\coloneq \bigcup_{j\in \left\{0,\ldots,\log_2(K-1)\right\}}\bigcup_{i\in \left\{0,\ldots,\frac{(K-1)}{2^j}-1\right\}}\left\{\bigg(i2^j\frac{1}{K-1},(i+1)2^j\frac{1}{K-1}\bigg]\right\}. \end{align}\tag{2}\] Notice that \(|\mathcal{I}^\star|\le 2K\).5 Then, we can prove the following:
Lemma 4. Let \(a,b\in G^U(K)=\{\frac{i}{K-1}: i=0,\ldots,K-1\}\) such that \(a<b\). Then Algorithm 11 on input (\(a,b\)) returns a collection of at most \(2\log_2(K)\) intervals in \(\mathcal{I}^\star\) that partition \((a,b]\).
Proof. The proof mirrors the algorithm’s execution and proceeds in two phases: first we extract a single large sub-interval covering at least a quarter of the target interval, then we recursively decompose the two leftover boundary segments.
5.2.0.1 Phase 1: Finding the First Main Sub-Interval.
Write \(u = (K-1)a\) and \(v = (K-1)b\) for the endpoints of \((a,b]\) rescaled to the integer grid, and let \(L = v - u = (K-1)(b-a)\) denote the rescaled length. Let \(2^j\) be the largest power of two not exceeding \(L\), i.e., \(j = \lfloor \log_2 L\rfloor\).
To justify the extraction of the first sub-interval, note that because \(L \ge 2^{j}\) if \((u,v]\) does not contain a full dyadic interval of size \(2^{j}\), the interval \((u,v]\) must contain exactly one multiple of \(2^j\), which we denote as \(m \cdot 2^j\). This grid point defines two adjacent canonical dyadic intervals of size \(2^{j-1}\) in \(\mathcal{I}^\star\): \[I_{\text{left}} = (m2^j - 2^{j-1}, m2^j] \quad \text{and} \quad I_{\text{right}} = (m2^j, m2^j + 2^{j-1}].\] Because the total length \(L \ge 2^j = 2 \cdot 2^{j-1}\), then \((u, v]\) must fully enclose at least one of these two canonical intervals. Let \((\frac{n_1}{K-1}, \frac{n_2}{K-1}] \in \mathcal{I}^\star\) be this enclosed interval, where \(n_2 - n_1 = 2^{j-1}\) and \(u \le n_1 < n_2 \le v\).
5.2.0.2 Phase 2: Recursive Decomposition of Leftover Intervals.
After removing the main sub-interval, two boundary segments remain, \((a, \frac{n_1}{K-1}]\) and \((\frac{n_2}{K-1}, b]\), whose inner endpoints \(n_1, n_2\) are already aligned with the dyadic grid. We decompose each recursively; by symmetry it suffices to treat \((a,\frac{n_1}{K-1}]\).
Let \(n^{(0)} = n_1\) be the current right anchor. Since \(n^{(0)}\) is, by construction, a multiple of \(2^{j-1}\), it is in particular a multiple of every smaller power \(2^{i}\), \(i \le j-1\). We peel off valid sub-intervals from right to left: at step \(k\), given anchor \(n^{(k)}\), we do the following:
Let \(2^{i_k}\) be the largest power of two fitting in the remaining rescaled gap, i.e., \(i_k = \lfloor \log_2\big(n^{(k)}-a(K-1)\big)\rfloor\).
Since, as we observed, \(n^{(k)}\) is a multiple of \(2^{i_k}\), the point \(n^{(k+1)} := n^{(k)} - 2^{i_k}\) is again a valid dyadic grid point, and the interval \(\big(\tfrac{n^{(k+1)}}{K-1}, \tfrac{n^{(k)}}{K-1}\big]\) belongs to \(\mathcal{I}^\star\).
The remaining gap at least halves at each step: \[n^{(k+1)} - (K-1)a \;\le\; \tfrac12\big(n^{(k)} - (K-1)a\big).\]
Iterating, the remaining gap \(n^{(k)} - (K-1)a\) shrinks geometrically and reaches \(0\) after at most \(\lfloor \log_2((b-a)(K-1))\rfloor\) steps. Hence \((a,\tfrac{n_1}{K-1}]\) decomposes into at most \(\lfloor \log_2((b-a)(K-1))\rfloor - 1\) elements of \(\mathcal{I}^\star\).
By the symmetric argument, \((\tfrac{n_2}{K-1}, b]\) also decomposes into at most \(\lfloor \log_2((b-a)(K-1))\rfloor - 1\) elements of \(\mathcal{I}^\star\).
Combining the single interval from Phase 1 with the two recursive decompositions, \((a,b]\) decomposes into at most \[1 + 2\Big(\lfloor \log_2((b-a)(K-1))\rfloor - 1\Big) \;\le\; 2\log_2(K)\] elements of \(\mathcal{I}^\star\), which completes the proof. ◻
5.3 Reconstruct the Differences From Sampling↩︎
We now show how to combine BinS and ComputeInterval to construct the distance function returned by RLS, whose pseudocode is given in 6. This construction is carried out by the procedure EstimateConstruction in 12.
Fix two points \(x = (x_1, x_2)\) and \(y = (y_1, y_2)\) that are directly connected in \(\mathcal{R}(\mathcal{G})\), and let \(z \in T(x,y)\) be the corresponding corner point (1 ). We decompose the distance between \(x\) and \(y\) along the two axes, reducing the problem to estimating the CDF differences of a single one-dimensional segment on each axis. By 4, each such segment can be decomposed into at most \(2\log_2 K\) intervals of \(\mathcal{I}^\star\), each of which is passed to BinS in 6. We estimate the probability mass of each interval via Compute-Prob and sum the resulting estimates to obtain an estimate of the segment’s length; the overall distance estimate \(\hat{D}(x;y)\) is then the sum of the two per-axis estimates. Overall, we get the following guarantees for EstimateConstruction and hence RLS:
Lemma 5. 6 uses at most \(\tilde{\mathcal{O}}\left(\dfrac{\log(K)}{\epsilon^3}+\dfrac{K}{\epsilon^2}\right)\) samples, and with probability at least \(1-\delta\) outputs, for every pair of points \(x, y \in \mathcal{G}\) which are connected in \(\mathcal{R}(\mathcal{G})\), an estimate \(\hat{D}(x;y)\) satisfying \[\left|\hat{D}(x;y) - D(x;y)\right| \le \tilde{\mathcal{O}}\left(\epsilon\log_2(K/\delta)\right).\]
Proof. We prove separately the sample complexity bound and the approximation guarantees. In the following, we assume that [thm:binS] holds, and hence our results will hold simultaneously for all call of the BinS procedure, with probability at least \(1-\delta\), taking the union bound over all \(2|\mathcal{I}^\star|\) events, each of probability at least \(1-\frac{\delta}{2|\mathcal{I}^\star|}\).
5.3.0.1 Sample Complexity.
6 invokes \(\textsf{BinS}^H(I,\epsilon,\delta/(2|\mathcal{I}^\star|),\mathcal{G})\) and \(\textsf{BinS}^V(I,\epsilon,\delta/(2|\mathcal{I}^\star|),\mathcal{G})\) for every interval \(I \in \mathcal{I}^\star\). By [thm:binS], each invocation requires at most \[\frac{2\mathbb{P}(X \in I \times [0,1])\log_2 K}{\epsilon^3} + \frac{2}{\epsilon^2}\] samples. Since Estimate-Construction\((\mathcal{G})\) performs no additional sampling, it suffices to bound \[\sum_{I \in \mathcal{I}^\star} \mathbb{P}(X \in I \times [0,1]).\]
The family \(\mathcal{I}^\star\) is organized into \(\log_2(K-1)+1\) dyadic levels, and at every level the intervals partition \((0,1]\), so \[\begin{align} \sum_{I \in \mathcal{I}^\star} \mathbb{P}(X \in I \times [0,1]) &= \sum_{j=0}^{\log_2(K-1)} \left(\sum_{i=0}^{\frac{K-1}{2^j}-1} \mathbb{P}\!\left(X \in \left(\tfrac{i 2^j}{K-1}, \tfrac{(i+1)2^j}{K-1}\right] \times [0,1]\right)\right) + \mathbb{P}(X \in \{0\} \times [0,1]) \\ &= \sum_{j=0}^{\log_2(K-1)} \mathbb{P}(X \in [0,1]\times[0,1]) = \log_2(K-1) + 1 = \mathcal{O}(\log_2 K), \end{align}\] where the second equality holds because, at each fixed level \(j\), the intervals \(\left(\tfrac{i 2^j}{K-1}, \tfrac{(i+1)2^j}{K-1}\right]\) partition \((0,1]\) exactly.
Substituting this bound into the per-interval sample count and summing over the \(\mathcal{O}(\log K)\) calls to BinS at each level, the total number of samples used by all calls to BinS is \[\sum_{I \in \mathcal{I}^*}\left(\frac{2\mathbb{P}(X \in I \times [0,1])\log_2 K}{\epsilon^3} + \frac{2}{\epsilon^2}\right) = \tilde{\mathcal{O}}\left(\frac{\log_2 K}{\epsilon^3} + \frac{K}{\epsilon^2}\right).\]
5.3.0.2 Approximation Guarantees
It remains to show that, with probability at least \(1-\delta\), every pair of connected vertices \(x, y \in \mathcal{G}\) satisfies \[\left|\hat{D}(x,y) - D(x,y)\right| \le \tilde{\mathcal{O}}\!\left(\epsilon \log_2(K/\delta)\right).\]
Assume first that \(x\) and \(y\) are connected through a point \(z \in T(x,y)\) sharing the first coordinate with \(x\) and the second coordinate with \(y\), namely \(z = (x_1, y_2)\), with \(x_1 \le y_1\) and \(x_2 \le y_2\). Then, it holds: \[\begin{align} D(x;y) &= \mathbb{P}(X \le y) - \mathbb{P}(X \le x) \\ &= \bigl(\mathbb{P}(X \le y) - \mathbb{P}(X \le z)\bigr) + \bigl(\mathbb{P}(X \le z) - \mathbb{P}(X \le x)\bigr) \\ &= \mathbb{P}\!\left(X \in (x_1,y_1] \times [0,y_2]\right) + \mathbb{P}\!\left(X \in [0,x_1] \times (x_2,y_2]\right). \end{align}\]
Let \(H\) and \(V\) be the collections of intervals constructed by 12. By 4, their elements are pairwise disjoint, \(|H|, |V| \le 2\log_2 K\), and \[\bigcup_{I \in H} I = (x_1,y_1], \qquad \bigcup_{I \in V} I = (x_2,y_2].\] Hence \[\mathbb{P}\!\left(X \in (x_1,y_1] \times [0,y_2]\right) = \sum_{I \in H} \mathbb{P}(X \in I \times [0,y_2]),\] and similarly \[\mathbb{P}\!\left(X \in [0,x_1] \times (x_2,y_2]\right) = \sum_{I \in V} \mathbb{P}(X \in [0,x_1] \times I).\]
By 3, and the union bound over all calls of BinS, with probability at least \(1-\delta\) each term in these two sums is estimated with additive error at most \[8\log_2(K)\,\epsilon\sqrt{\frac{\ln(8K|\mathcal{I}^\star|/\delta)}{2}}.\]
Summing over the at most \(|H| + |V| \le 4\log_2 K\) terms and applying the triangle inequality, we obtain \[\begin{align} |\hat{D}(x;y)-D(x;y)| &\le \sum_{I\in H} \left| \widehat{P}(X\in I\times[0,y_2]) - \mathbb{P}(X\in I\times[0,y_2]) \right|\\ &\quad+ \sum_{I\in V} \left| \widehat{ P}(X\in[0,x_1]\times I) - \mathbb{P}(X\in[0,x_1]\times I) \right|\\ &\le \widetilde{\mathcal{O}}\!\left( \epsilon\log_2(K/\delta) \right), \end{align}\] where the polylogarithmic factors absorb the cardinalities of \(H\) and \(V\).
The remaining configurations of \(x\), \(y\), and \(z\) are handled analogously, by exchanging the roles of the endpoints and, when necessary, of the horizontal and vertical components. ◻
6 Share the Feedback↩︎
Here, we address the last challenge in designing our algorithm: learning how to share feedback among points of the grid.
This resembles a bandit problem with a feedback graph. From the feedback generated by choosing an arm \(x\), it is possible to recover an approximation of the reward of a connected arm \(y\), for any edge \((x,y)\) in the graph. We consider graphs equipped with all self-loops, namely the edge \((x,x)\) belongs to the graph for all vertexes \(x\). Unfortunately, this does not directly fit the standard bandits-with-feedback-graphs framework, since the reward of \(y\) is only recovered up to approximation.
The section is organized as follows. We first define a general model, which we call multi-armed bandits with feedback graph and \(\epsilon\)-misspecified rewards, and provide a UCB1-style algorithm showing how the \(\epsilon\)-error propagates into the regret bound. We then show how to adapt this model to our setting, where the feedback graph is the key device that replaces the dependence of the regret bound on the number of arms with a dependence on the graph’s independence number.
6.1 Multi-Armed Bandits With Feedback Graph and \(\epsilon\)-Misspecified Rewards↩︎
At each round \(t \in [T]\), the learner selects an arm \(i\) from a set \(\mathcal{M}\) of size \(M\), and observes feedback \(o_{t,i}\in [0,1]\) and gets reward \(r_{t,i} \in [0,1]\). For each arm, the rewards are i.i.d.across rounds according to a fixed, unknown distribution \(D_i\) with mean \(\mu_i\).
Unlike the standard bandit problem, the learner has access to additional feedback according to a graph. In the standard bandits-with-feedback-graph model, pulling an arm reveals not only the reward of that arm, but also the rewards of a prescribed set of neighboring arms, as determined by a feedback graph. Here, we study a generalization in which these neighboring rewards may be slightly misspecified.
Let \(\mathcal{R} = (\mathcal{M}, \mathcal{E})\) be an undirected graph over the set of arms \(\mathcal{M}\), and let \(\mathcal{N}(i) = \{j \in \mathcal{M} : (i,j) \in \mathcal{E}\}\) denote the neighborhood of arm \(i\). For every edge \((i,j) \in \mathcal{E}\), there exists an unknown function \(f_{i,j} : [0,1] \to [0,1]\), such that \[\begin{align} \mu_j= \mathbb{E}[f_{i,j}(o_{t,i})] \end{align}\] The learner does not know \(f_{i,j}\), but is given an estimate \(\hat{f}_{i,j} : [0,1] \to [0,1]\) satisfying the uniform approximation guarantee \[\sup_{x \in [0,1]} |\hat{f}_{i,j}(x) - f_{i,j}(x)| \le \epsilon.\]
In summary, at each round the learner receives feedback only for the selected arm; nevertheless, by combining the graph structure with the \(\epsilon\)-accurate estimates \(\{\hat{f}_{i,j}\}\), it can form approximations of the expected rewards of neighboring arms.
For the remainder of this section, we let \(\mathbb{I}_t(i)\) denote the indicator function equal to \(1\) if and only if the learner selects arm \(i \in \mathcal{M}\) at round \(t\), and we let \(n_t(i) = \sum_{\tau=1}^t \mathbb{I}_\tau(i)\).
6.2 A UCB-Like Approach↩︎
Our analysis is largely inspired by standard tools used in bandits with feedback graphs. The crucial observation is that, while playing arm \(i\), observing \(o_{t,i}\) together with knowing the function \(\hat{f}_{i,j}(\cdot)\) suffices to recover a slightly biased estimator of the reward of any arm \(j \in \mathcal{N}(i)\), with bias bounded as \[|\mu_j - \mathbb{E}[f_{i,j}(o_{t,i})]| \le \epsilon.\]
We then follow standard arguments, carrying this bias term through the analysis, where it appears linearly in the final regret bound. 13 gives the pseudocode, while the following theorem, whose proof is deferred to Appendix 9, states the resulting regret guarantee.
theoremtheoremGraph With probability at least \(1-\delta\) 13 attains \[\begin{align} R_T= \tilde{\mathcal{O}}\left(\log(M\delta^{-1})\left(\sqrt{\alpha(\mathcal{R})T}+ T\epsilon\right)\right), \end{align}\] where \(\alpha(\mathcal{R})\) is the independence number of the graph \(\mathcal{R}\).
As a direct corollary, we obtain an analogous guarantee for our setting.
Corollary 2. There exists an algorithm that takes in input the graph \(\mathcal{R}^\textsf{OPT}\) (3) and the estimates \(D(x;y)\) for each \(x\) and \(y\) which are connected by an edge in the graph \(\mathcal{R}^{\textsf{OPT}}\), and under the clean event \(E_0\) and the event described by 5 it guarantees regret over \(T\) rounds of at most \[\widetilde{\mathcal{O}}\left(\log(\delta^{-1})\left(\sqrt{\alpha(\mathcal{R}^\textsf{OPT})T}+T\epsilon\right)\right),\] with probability at least \(1-\delta\).
Proof. The proof proceeds by reducing the problem to an instance of a multi-armed bandit with graph feedback and \(\epsilon\)-misspecified rewards, as defined above.
Fix two connected points \(x, y \in \mathcal{G}^{\mathrm{OPT}}\). Recall that \(\mu_{x} = g(x)F(x)\), \(\mu_{y} = g(y)F(y)\), and \(F(y) = F(x) + D(x;y)\). Notice that we can recover an instance with positive rewards by a simple normalization. Additionally, by choosing \(x\) at round \(t\) we observe \(o_{t,x}=\mathbb{I}(X_t\le x)\). Define \(f_{x,y}\) as \[f_{x,y}(o) = \left(o + D(x;y)\right) g(y).\] Since \(f_{x,y}\) is affine, it holds \[\begin{align} \mathbb{E}[f_{x,y}(o_{t,x})] &=f_{x,y}(\mathbb{E}[\mathbb{I}(X_t\le x)]) \\ &= f_{x,y}(F(x))\\ &= \left(F(x) + D(x;y)\right) g(y) \\ & = F(y)\, g(y) = \mu_y, \end{align}\] so that \(f_{x,y}\) satisfies the exact-reward-recovery condition required by the reduction. Notice that if \(x=y\) then \(D(x;y)=0\) and \(f_{x,x}(o)=o \cdot g(x)\).
Similarly, define the estimated map \[\hat{f}_{x,y}(o) = \left(o + \hat{D}(x,y)\right) g(y).\] Then, we get that for each \(o\in [0,1]\), it holds \(|\hat{f}_{x,y}(o)|\le \mathcal{O}(1)\).
Moreover, assuming the event of 5, \[\begin{align} |f_{x,y}(o) - \hat{f}_{x,y}(o)| &= \bigl|(D(x;y) - \hat{D}(x;y))\, g(y)\bigr| \\&\le |D(x;y) - \hat{D}(x;y)| \le \tilde{\mathcal{O}}(\epsilon \log_2(\delta^{-1})) \qquad \forall o \in [0,1], \end{align}\] where we used \(K=1/\epsilon\). Finally, for this choice of the set \(\mathcal{M}\) we have that \(M=|\mathcal{G}^\textsf{OPT}|\le K^2\). This concludes the proof. ◻
7 Putting Everything Together↩︎
We are ready to prove the main theorem, which we restate here for clarity.
Proof. Let \(x^*\) be defined as the optimum on the grid \(\mathcal{G}^U(1/\epsilon)\), i.e. \(x^*\in \arg \max_{x\in \mathcal{G}^U(1/\epsilon)}\sum_{t=1}^Tg(x)F(x)\), and let us consider 2. Let \(P_1,P_2,P_3\) be the set or rounds in which the algorithm is playing Phase \(1 ,2, 3\) respectively (the BuildGraph procedure is only a computational procedure that does not require interaction with the environment and therefore does not generates regret). To prove the theorem it is necessary to decompose the regret in 4 components:
The approximation error : \(\max_{x\in [0,1]^2}\sum_{t=1}^T g(x)F(x)-\max_{x\in \mathcal{G}^U(1/\epsilon)}\sum_{t=1}^T g(x)F(x)\)
The regret of the first phase: \(R_T^1= \sum_{t\in P_1}g(x^*)F(x^*)-\sum_{t\in P_1}g(x_t)F(x_t)\)
The regret of the second phase: \(R_T^2= \sum_{t\in P_2}g(x^*)F(x^*)-\sum_{t\in P_2}g(x_t)F(x_t)\)
The regret of the third phase: \(R_T^3= \sum_{t\in P_3}g(x^*)F(x^*)-\sum_{t\in P_3}g(x_t)F(x_t)\)
7.0.0.1 Bounding \(R_T^1\).
The regret suffered in the first phase can be upperbounded by the number of rounds in \(P_1\). Hence, by 1 \[R_T^1\le |P_1|\le \mathcal{O}\left(\frac{1}{\Delta^3}\log(1/\epsilon\delta)^{\mathcal{O}(1)}\right).\]
7.0.0.2 Bounding \(R_T^2\).
The regret suffered in the second phase can be upperbounded by the number of rounds in \(P_2\) multiplied for the highest possible sub-optimality gap in \(\mathcal{G}\), as this phase is specifically designed to choose only elements in \(\mathcal{G}\).
We can bound the highest sub-optimality gap in \(\mathcal{G}\) under the event \(E_0\) with \(8\Delta\) thanks to 1, and we can bound \(|P_2|\) using the result in terms of sample complexity of 5
In particular, recall that the parameter \(K\), which denotes the size of the one-dimensional discretization, is set to \(K=1/\epsilon\) in 2; that is, the initial uniform grid is \(\mathcal{G}^U(1/\epsilon)\).
Hence, under the event \(E_0\), \[R_T^2\le 8\Delta|P_2|\le \mathcal{O}\left(\left(\frac{\Delta}{\epsilon^3}\right)\log(1/\epsilon)\right).\]
7.0.0.3 Bounding \(R_T^3\).
The regret suffered by the third phase can be bounded using 2 and [lemma:32E0], so that under \(E_0\) and with probability at least \(1-\delta\), \[R_T^3\le \widetilde{\mathcal{O}}\left(\frac{1}{\Delta}\sqrt{T\ln(1/\epsilon\delta)}+T\epsilon\right).\]
7.0.0.4 Bounding the Discretizations Error.
The difference between the optimum on the uniform grid and the optimum on the continuum can be bounded by the 1-Lipschitzness of \(g(\cdot)\). Indeed, for any \(x\in [0,1]^2\), it exists a \(y\in \mathcal{G}\), \(y\ge x\) such that \(\lVert y-x\rVert_1\le 2\epsilon\), so that \(g(y)F(y)\ge g(y)F(x)\ge g(x)F(x) - 2\epsilon\). Hence, \[\max_{x\in [0,1]^2}\sum_{t=1}^T g(x)F(x)-\max_{x\in \mathcal{G}^U(1/\epsilon)}\sum_{t=1}^T g(x)F(x)\le 2T\epsilon.\]
To conclude, by setting \(\Delta= T^{-2/10}\), \(\epsilon= T^{-3/10}\) and \(\delta=\frac{1}{T}\) \[\begin{align} R_T&= \tilde{\mathcal{O}}\left(\frac{1}{\Delta^3}\log(1/\epsilon\delta)^{\mathcal{O}(1)}+\left(\frac{\Delta }{\epsilon^3}\right)\log(1/\epsilon)+\frac{1}{\Delta}\sqrt{T\ln(1/\epsilon\delta)}+T\epsilon+T\delta\right) \le \tilde{\mathcal{O}}\left(T^{7/10}\right), \end{align}\] which concludes the proof. ◻
8 Omitted Proofs from 5↩︎
For completeness, we report the pseudocode of Estimate (called Monte Carlo Estimation in [14]).
Moreover, we restate their result:
Then, we are ready to proof [thm:binS].
Proof. The proof is substantially analogous to the one provided for a complete grid \(\mathcal{G}^U(K)\).
The procedure Estimate is called deterministically at most once for every element in \(\mathcal{W}\), and \(|\mathcal{W}|\le K\) by construction. Hence, we define the clean event \(\mathcal{E}\) under which every call to Estimate made by BinS satisfies the property in [lem:Estimate] for a confidence parameter \(\delta' \coloneq \delta / (K)\). Given that \(\mathcal{E}\) is simply the intersection of at most \(K\) events, by a union bound \(\mathcal{E}\) holds with probability at least \(1 -\delta\).
Under the clean event \(\mathcal{E}\) the following holds: \[\left\lvert \widehat{P}((a,b]\times [0,w])-\mathbb{P}_{X\sim \mathcal{D}}(X\in (a,b]\times[0,w])\right\rvert\le \epsilon\,2\;\sqrt{\frac{\ln(\frac{4K}{\delta})}{2}} \quad \forall w\in \textrm{\mathrm{\small Extremes}}(\mathcal{I}),\] which is exactly the first property in the statement of the lemma.
Then, for all \(I \in \mathcal{I}\) such that \(I = (w_i,w_{i+1}]\), under the event \(\mathcal{E}\) it holds:
\[\begin{align} \widehat{P}([a,b] \times [0,w_{i+1}]) - \widehat{P}&([a,b]\times [0,w_{i}]) - \epsilon\,2\left(2\sqrt{\frac{\ln(\frac{4K}{\delta})}{2}}\right) \\ & \ge \mathbb{P}_{X\sim \mathcal{D}}\left(X \in [a,b] \times (w_i,w_{i+1}]\right)- \epsilon\,4\left(2\sqrt{\frac{\ln(\frac{4K}{\delta})}{2}}\right)\label{eq:32phat32difetto}, \end{align}\tag{3}\] and \[\begin{align} \widehat{P}([a,b]\times [0,w_{i+1}]) - \widehat{P}([a,b]\times [0,w_{i}]) - \epsilon\,2\left(2\sqrt{\frac{\ln(\frac{4K}{\delta})}{2}}\right)\le \mathbb{P}_{X\sim \mathcal{D}}(X \in [a,b] \times (w_i,w_{i+1}])\label{eq:32phat32eccesso}. \end{align}\tag{4}\] This proves the second property in the statement of the lemma. Indeed \[\begin{align} \mathbb{P}_{X\sim \mathcal{D}}(X \in [a,b] \times (w_i,w_{i+1}])\le \epsilon + \epsilon\,8\sqrt{\frac{\ln(\frac{4K}{\delta})}{2}}. \end{align}\]
Finally, the splitting condition on the probability is identical to the one of [14], and with analogous analysis, letting \(n_k \in \mathbb{N}\) be the number of sub-intervals \((y_i,y_j]\) such that \(\lfloor j-i \rfloor=2^{-k}\), under \(\mathcal{E}\), we have for each splitted \((y_i,y_j]\): \[\mathbb{P}_{X\sim \mathcal{D}}(X \in [a,b] \times (y_i, y_j]) \ge \widehat{P}([a,b] \times [0, y_j]) - \widehat{P}([a,b] \times [0, y_i]) -\epsilon\,2\left(2\sqrt{\frac{\ln(4K/\delta)}{2}}\right) \ge \epsilon.\] Hence, \[n_k \, \epsilon \le \mathbb{P}_{X\sim \mathcal{D}}(X \in [a,b]\times [0,1]).\] To conclude, each split introduces one new interval in \(\mathcal{I}\), and each call to Estimate employs \(1/\epsilon^2\) samples, therefore \[|\mathcal{I}| \le \sum_{k=0}^{\log_2 K} n_k +2 \le (\log_2 K+1)\,\frac{\mathbb{P}_{X\sim \mathcal{D}_{j}}(X \in [a,b]\times [0,1])}{\epsilon} +2,\] where the plus two accounts for the case \(\mathbb{P}_{X\sim \mathcal{D}_{j}}(X \in [a,b]\times [0,1])=0\). ◻
9 Proof of [thm:32graph32reg]↩︎
We start by giving some preliminary results.
Lemma 6. Set \(t\in [T], i\in \mathcal{M}\). Then, with probability at least \(1-\delta\) \[\big|\hat{r}_{t,i}-\mathbb{E}[r_{t,i}]\big|\le 6\sqrt{\frac{\ln(\delta^{-1})}{\sum_{j\in \mathcal{N}(i)}n_t(j)}}+ \epsilon\]
Proof. As a first step, we relate the expected value of the estimator \(\hat{r}_{t,i}\) and the expected reward of arm \(i\).
\[\begin{align} \mathbb{E}[\hat{r}_{t,i}]& = \mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_\tau(j)\hat{f}_{j,i}(o_{\tau,j})\right]\\ & = \mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_\tau(j){f}_{j,i}(o_{\tau,j})\right]\\ & + \mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_\tau(j)\bigg(\hat{f}_{j,i}(o_{\tau,j})-f_{j,i}(o_{\tau,j})\bigg)\right]\\ & =\mathbb{E}\left[\mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_\tau(j){f}_{j,i}(o_{\tau,j})\bigg|\{\mathbb{I}_\tau(j)\}_{\tau,j}\right]\right]\\ & + \mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_\tau(j)\bigg(\hat{f}_{j,i}(o_{\tau,j})-f_{j,i}(o_{\tau,j})\bigg)\right]\\ & = \mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_\tau(j)\mathbb{E}[r_{t,i}]\right]\\ & + \mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_\tau(j)\bigg(\hat{f}_{j,i}(o_{\tau,j})-f_{j,i}(o_{\tau,j})\bigg)\right]\\ & =\mathbb{E}[r_{t,i}]+ \mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_\tau(j)\bigg(\hat{f}_{j,i}(o_{\tau,j})-f_{j,i}(o_{\tau,j})\bigg)\right]. \end{align}\]
Then, we show how the second term can be bounded with misspecification error \(\epsilon\): \[\begin{align} &\left|\mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i) }\sum_{\tau=1}^t \mathbb{I}_\tau(j)\bigg(\hat{f}_{j,i}(o_{\tau,j})-f_{j,i}(o_{\tau,j})\bigg)\right]\right|\\ & \le \mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_\tau(j)\bigg(\left|\hat{f}_{j,i}(o_{\tau,j})-f_{j,i}(o_{\tau,j})\right|\bigg)\right]\\ & \le \epsilon \cdot\mathbb{E}\left[\frac{1}{\sum_{j\in \mathcal{N}(i)} n_t(j) }\sum_{j\in \mathcal{N}(i)}\sum_{\tau=1}^t \mathbb{I}_t(j)\right]= \epsilon, \end{align}\]
therefore \[\begin{align} \left|\mathbb{E}[\hat{r}_{t,i}]-\mathbb{E}[r_{t,i}]\right|\le \epsilon. \end{align}\]
Finally, we employ Azuma-Hoeffding inequality to bound the difference between the realization of \(\hat{r}_{t,i}\) and its expected value. To do so, we observe that \(-1\le 0-\epsilon\le \hat{f}_{j,i}(o_{t,j})\le 1+\epsilon\le 2\). Then, with probability at least \(1-\delta\)
\[\begin{align} \left|\hat{r}_{t,i}-\mathbb{E}[\hat{r}_{t,i}]\right|\le 6\sqrt{\frac{\ln(\delta^{-1})}{\sum_{j\in \mathcal{N}(i)}n_t(j)}}, \end{align}\] which concludes the proof. ◻
Additionally, we can take the union bound, and rescaling \(\delta\) to have a result that holds simultaneously for all \(t\in [T]\), \(i\in \mathcal{M}.\)
Lemma 7. Let \(\delta\in (0,1).\) With probability at least \(1-\delta\) \[\begin{align} \left|\hat{r}_{t,i}-\mathbb{E}[r_{t,i}]\right|\le 6\sqrt{\frac{\ln(TM\delta^{-1})}{\sum_{j\in \mathcal{N}(i)}n_t(j)}}+\epsilon \quad \forall i\in \mathcal{M}, \forall t\in [T] \end{align}\]
Then, we can employ standard UCB-N analysis ([23]) to bound the regret. Naturally, the regret will depend on the graph property. Therefore, we can prove the following result.
Proof. Let \(i^*\in \arg \max_{i\in \mathcal{M}} \mathbb{E}[r_{t,i}]\). Let \(\mathcal{H}_t\) be the history up to round \(t\), for all \(t\in [T]\). By 7, with probability at least \(1-\delta\) \[\begin{align} \sum_{t=1}^T \left(\mathbb{E}[r_{t,i^*}]-\mathbb{E}[r_{t,i_t}|\mathcal{H}_{t-1}]\right)& = \sum_{t=1}^T \left(\mathbb{E}[r_{t,i^*}]-\overline{r}_{t,i^*}\right)\\ & +\sum_{t=1}^T \left(\overline{r}_{t,i^*}-\overline{r}_{t,i_t}\right)+ \sum_{t=1}^T \left(\overline{r}_{t,i_t}-\mathbb{E}[r_{t,i_t}|\mathcal{H}_{t-1}]\right)\\ & \le \sum_{t=1}^T \left(\overline{r}_{t,i_t}-\mathbb{E}[r_{t,i_t}|\mathcal{H}_{t-1}]\right)\\ & \le 2\sum_{t=1}^T \left(6\sqrt{\frac{\ln(TM\delta^{-1})}{\sum_{j\in \mathcal{N}(i_t)}n_t(j)}}+\epsilon\right), \end{align}\] where we used the fact that \(i_t\in \arg\max_{i\in \mathcal{M}}\overline{r}_{t,i}\), and that with probability at least \(1-\delta\) \(\mathbb{E}[r_{t,i}]-\overline{r}_{t,i}\le 0\) for all \(t\in [T]\), for all \(i\in \mathcal{M}\). Therefore, aside from the addittive term \(\mathcal{O}(T\cdot \epsilon)\), specific of our setting, the confidence intervals shrinking is equivalent to the one in the algorithm UCB-N proposed by [23], and following the same analysis we have
\[\begin{align} R_T \le \mathcal{O}\left(\ln(TM\delta^{-1})\sqrt{\alpha(\mathcal{R})T} + 2\epsilon \,T\right). \end{align}\] ◻
References↩︎
[11], [12] study profit maximization, but with general rather than fixed-price mechanisms.↩︎
Notice that the assumption that the Lipschitz constant is equal to \(1\) is without loss of generality. All our results extend straightforwardly to arbitrary Lipschitz constants. Moreover, since all norms are equivalent up to constants depending only on \(d\), and we work in fixed dimension \(d=2\), our results extend straightforwardly to arbitrary norms, at the cost of only a multiplicative constant in the regret bound.↩︎
We denote by \([n] \coloneq \{1,\ldots,n\}\) the set of the first \(n \in \mathbb{N}\) natural numbers.↩︎
Throughout the paper, we omit the ceiling operator in round numbers and assume that they are integer quantities.↩︎
To account for the interval \({0}\), we also run the procedure on the degenerate interval \((0^-,0]={0}\), where, by convention, \(\mathbb{I}(x\le(0^-,w))=0\) deterministically for all \(w\in [0,1]\). This modification does not affect the analysis or the order of the guarantees.↩︎