This paper studies batched bandit learning problems for nondegenerate functions. Over a compact doubling metric space (X,D), a functionf : X→ R is called nondegenerate if there existsL≥ λ > 0 andq≥ 1, such that λ (D(x, x*))q≤f(x) −f(x*) ≤L(D(x, x*))q, x ∈X, where x* = arg minz∈Xf(z) is the unique minimizer offoverX. In this paper, we introduce an algorithm that solves the batched bandit problem for nondegenerate functions nearoptimally. More specifically, we introduce an algorithm, called Geometric Narrowing (GN), whose regret bound is of orderO(Ad+√T), wheredis the doubling dimension of (X,D), andA+is a constant independent ofdand the time horizonT. In addition, GN only needsO(log logT) batches to achieve this regret. We also provide lower bound analysis for this problem. More specifically, we prove that over some (compact) doubling metric space of doubling dimensiond: 1. For any policy π, there exists a problem instance on which π admits a regret of order Ω (Ad−√T), whereA−is a constant independent ofdandT; 2. No policy can achieve a regret of orderAd−√Tover all problem instances, using less than Ω(log logT) rounds of communications. Our lower bound analysis shows that the GN algorithm achieves near optimal regret with minimal number of batches.

We prove convergence rates of Zeroth-order Gradient Descent (ZGD) algorithms for Łojasiewicz functions. Our results show that for smooth Łojasiewicz functions with Łojasiewicz exponent larger than 0.5 and smaller than 1, the functions values can converge much faster than the (zeroth-order) gradient descent trajectory. Similar results hold for convex nonsmooth Łojasiewicz functions. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0247 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0247 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

In this paper, we study Lipschitz bandit problems with batched feedback, where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. We introduce a novel landscape-aware algorithm, called Batched Lipschitz Narrowing (BLiN), that optimally solves this problem. Specifically, we show that for a$T$-step problem with Lipschitz reward of zooming dimension$d_{z}$, our algorithm achieves theoretically optimal (up to logarithmic factors) regret rate$\widetilde {\mathcal {O}}\left ({T^{\frac {d_{z}+1}{d_{z}+2}}}\right)$using only$\mathcal {O} \left ({\log \log T}\right) $batches. We also provide complexity analysis for this problem. Our theoretical lower bound implies that$\Omega (\log \log T)$batches are necessary for any algorithm to achieve the optimal regret. Thus, BLiN achieves optimal regret rate (up to logarithmic factors) using minimal communication.

In this paper, we study Lipschitz bandit problems with batched feedback, where the expected reward is Lipschitz and the reward observations are communicated to the player in batches. We introduce a novel landscape-aware algorithm, called Batched Lipschitz Narrowing (BLiN), that optimally solves this problem. Specifically, we show that for a $T$-step problem with Lipschitz reward of zooming dimension $d_z$, our algorithm achieves theoretically optimal (up to logarithmic factors) regret rate $\widetilde{\mathcal{O}}\left(T^{\frac{d_z+1}{d_z+2}}\right)$ using only $ \mathcal{O} \left( \log\log T\right) $ batches. We also provide complexity analysis for this problem. Our theoretical lower bound implies that $\Omega(\log\log T)$ batches are necessary for any algorithm to achieve the optimal regret. Thus, BLiN achieves optimal regret rate using minimal communication.

A classical problem in causal inference is that of matching, where treatment units need to be matched to control units based on covariate information. In this work, we propose a method that computes high quality almost-exact matches for high-dimensional categorical datasets. This method, called FLAME (Fast Large-scale Almost Matching Exactly), learns a distance metric for matching using a hold-out training data set. In order to perform matching efficiently for large datasets, FLAME leverages techniques that are natural for query processing in the area of database management, and two implementations of FLAME are provided: the first uses SQL queries and the second uses bit-vector techniques. The algorithm starts by constructing matches of the highest quality (exact matches on all covariates), and successively eliminates variables in order to match exactly on as many variables as possible, while still maintaining interpretable high-quality matches and balance between treatment and control groups. We leverage these high quality matches to estimate conditional average treatment effects (CATEs). Our experiments show that FLAME scales to huge datasets with millions of observations where existing state-of-the-art methods fail, and that it achieves significantly better performance than other matching methods.

We study the bandit problem where the underlying expected reward is a Bounded Mean Oscillation (BMO) function. BMO functions are allowed to be discontinuous and unbounded, and are useful in modeling signals with singularities in the domain. We develop a toolset for BMO bandits, and provide an algorithm that can achieve poly-log $\delta$-regret – a regret measured against an arm that is optimal after removing a $\delta$-sized portion of the arm space.