1 Introduction↩︎

Stochastic optimization problems have been a subject of intense investigation, as they offer a powerful lens through which we can handle uncertain inputs. In stochastic problems, uncertain input parameters are modeled by random variables, which are usually independent. Solutions (or policies) to a stochastic problem are sequential decision processes, where the next decision depends on all previously observed information. This approach has been applied to many domains: optimal stopping [1]–[3], revenue management [4], mechanism design [5], [6], submodular optimization [7]–[9], stochastic probing [10]–[12] and various other stochastic combinatorial optimization problems such as knapsack [13], [14] and matching [15], [16]. A fundamental assumption in all these results is that the underlying probability distributions are known to the algorithm. While the known-distributions assumption holds in some settings, it is not satisfied in many practical applications, e.g., in the absence of historical data. Our main goal in this paper is to relax this assumption and handle stochastic problems with unknown distributions. We start by providing some concrete examples.

Series testing. There is a system with \(n\) components, where each component \(i\) is “working” independently with some probability \(p_i\). All \(n\) components must be working for the system to be functional. Moreover, it costs \(c_i\) to test component \(i\) and determine whether/not it is working. The goal is to test components sequentially to determine whether/not the system is functional, at the minimum expected cost. Clearly, testing will continue until some component is found to be not working, or we have tested all components and found them to be working. In the standard setting, where the probabilities \(\{p_i\}_{i=1}^n\) are known upfront, the greedy policy that tests components in decreasing order of \(\frac{1-p_i}{c_i}\) is optimal [17].

Pandora’s box. There are \(n\) items, where each item \(i\) has an independent random value \(\mathsf{X}_i\) with a known distribution \(\mathcal{D}_i\). The realized value of \(\mathsf{X}_i\) can be revealed by inspecting item \(i\), which incurs cost \(c_i\). The goal is to inspect a subset \(S\) of the items (possibly adaptively) to maximize the expected utility \(\mathbb{E}\left[\max_{i \in S} \mathsf{X}_i - \sum_{i \in S} c_i\right]\). We emphasize that a solution to this problem can be quite complex: the choice of the next item to inspect may depend on the realizations of all previous items. Nevertheless, there is an elegant optimal solution to this problem when the distributions \(\{\mathcal{D}_i\}_{i=1}^n\) are known [1].

Single Resource Revenue Management. An airline has \(C\) seats for sale across \(n\) fare classes, where each seat sold in class \(i\) has a fixed revenue \(p_i\). The customer demand for each fare class \(i\) is an independent random variable \(\mathsf{X}_i\sim \mathcal{D}_i\). Customers preferring lower fares arrive earlier—a common assumption in practice. The airline allocates seats to different fare classes sequentially. If \(m_i\) seats are offered to fare class \(i\) then the associated revenue is \(p_i\cdot \mathbb{E}[\min(X_i, m_i)]\). The number of seats offered to class \(i\) may depend on the actual sales in prior classes. The objective is to maximize the expected total revenue. There is an exact dynamic programming algorithm for this problem [4].

There are \(n\) buyers for an item, where each buyer \(i\) has a random valuation \(\mathsf{X}_i\) with known distribution \(\mathcal{D}_i\). The seller wants to choose a take-it-or-leave-it price \(p_i\) for each buyer \(i\) so as to maximize the expected revenue when the buyers are offered these prices in some order. The first buyer \(i\) whose value \(\mathsf{X}_i\) exceeds their posted price \(p_i\) buys the item, and the seller receives revenue \(p_i\). There are two variants of this problem, depending on whether the buyer ordering is fixed or can be chosen by the algorithm. There is an exact dynamic program for the fixed-order setting and a \(\left(1-\frac{1}{e}\right)\) approximation algorithm for the free-order setting [18].

In each of the above problems, what if the underlying probabilities/distributions are unknown? Is it still possible to obtain good performance guarantees? In order to address this question formally, we utilize the framework of online learning. Here, the algorithm interacts with an unknown-but-fixed input distribution \(\mathcal{D}\) over multiple time periods. In each period \(t =1,\cdots T\), the online algorithm comes up with a solution/policy \(\sigma^{t}\) to the stochastic problem and receives some feedback based on the performance of \(\sigma^t\) on the (unknown) distribution \(\mathcal{D}\).

The type of feedback received is a crucial component in this learning-based framework. The simplest setting is full feedback, where the algorithm receives one sample from every random variable (r.v.). However, this is unrealistic for stochastic problems because the policy \(\sigma^t\) in period \(t\) only observes the r.v.s corresponding to some subset of the items. For example, in series testing, \(\sigma^t\) tests the \(n\) components in some order until the first non-working component is found: if the first \(k-1\) components are working and the \(k^{th}\) component is not working then we would only observe the outcomes/samples of the first \(k\) r.v.s (and the remaining \(n-k\) r.v.s are unobserved). In order to address this aspect, we consider the more natural setting of semi-bandit feedback, where in each period \(t\), the algorithm only receives samples from the r.v.s that the policy \(\sigma^t\) actually observed. We further study two other restricted feedback models— censored and binary feedback—that naturally arise in applications like revenue management and posted pricing, respectively.

Our goal is to minimize the expected regret of the online algorithm, which is the difference between the total \(T\)-period objective of our algorithm and the optimum (which knows the distribution \(\mathcal{D}\)). Obtaining \(o(T)\) regret dependence with respect to \(T\) means that our online algorithm, which doesn’t know \(\mathcal{D}\), asymptotically approaches the optimum. An additional difficulty arises from the fact that many problems that we consider are NP-hard (e.g., knapsack and submodular optimization). In such cases, we cannot hope to approach the optimum via a polynomial algorithm. Here, we use the notion of \(\alpha\)-regret, where the online algorithm approaches the \(\alpha\) approximately optimal value.

Our main result is a general method for transforming any offline \(\alpha\)-approximation algorithm (with known distributions) to an online learning algorithm with \(\alpha\)-regret of \(\widetilde{O}(\sqrt{T})\). It is well-known that the \(\sqrt{T}\) regret bound cannot be improved, even in very special cases. Our method works for a wide range of stochastic problems that satisfy a natural monotonicity condition. This includes all the above examples as well as several other fundamental stochastic optimization problems.

1.1 Problem Setup↩︎

We first set-up notation for stochastic optimization problems in the known distribution setting.

1.1.0.1 Stochastic Optimization

Consider a stochastic problem \(\mathcal{P}\) where the input consists of \(n\) items with an independent real-valued r.v. \(\mathsf{X}_i\) associated with each item \(i\in [n]=\{1,2,\cdots n\}\). There is a known probability distribution \(\mathcal{D}_i\) for \(\mathsf{X}_i\); that is, \(\mathsf{X}_i \sim \mathcal{D}_i\). We will primarily consider the setting where each \(\mathcal{D}_i\) has finite support, and denote the set of outcomes of all r.v.s by \(O\). (We also consider continuous distributions in §3.) In order to determine the realization of any r.v. \(\mathsf{X}_i\), we need to select or probe item \(i\).

A solution or policy for \(\mathcal{P}\) is given by a decision tree \(\sigma\), where each node is labeled by an item to probe next, and the branches out of a node correspond to the random realization of the probed item. Each node in decision tree \(\sigma\) also corresponds to the current “state” of the policy, which is given by the sequence of previously-probed items along with their realizations; we will refer to nodes and states of the policy interchangeably. The root node of \(\sigma\) is the starting state of the policy, at which point no item has been probed. Leaf nodes in \(\sigma\) are also called terminal nodes/states. The policy execution under any realization \(\mathbf{x}= ( x_1, \ldots, x_n)\) corresponds to a root-leaf path \(\sigma_\mathbf{x}\) in the decision tree \(\sigma\), where at any node labeled by item \(i\), path \(\sigma_\mathbf{x}\) follows the branch corresponding to outcome \(x_i\). Note that running policy \(\sigma\) under \(\mathbf{x}\) corresponds to traversing path \(\sigma_\mathbf{x}\). We also define \(S(\sigma,\mathbf{x})\) as the sequence of items probed by policy \(\sigma\) under realization \(\mathbf{x}\).

The cost of policy \(\sigma\) depends on the realization \(\mathbf{x}\), and we use \(f(\sigma, \mathbf{x})\ge 0\) to denote the cost of policy \(\sigma\) under realization \(\mathbf{x}\). Specifically, \(f(\sigma, \mathbf{x})\) depends only on the sequence of probed items \(S(\sigma,\mathbf{x})\) and their realizations. We assume that cost is accrued only at terminal/leaf nodes: this is without loss of generality as every policy execution ends at a leaf node.

We make no further assumptions about the cost function \(f\) beyond boundedness: it does not have to be linear, submodular etc. Our goal is to find a policy \(\sigma\) that minimizes the expected cost \(f(\sigma) := \mathbb{E}_{\mathbf{x}}[f(\sigma, \mathbf{x})]\). We also allow for constraints in problem \(\mathcal{P}\), which must be satisfied under all realizations (i.e., with probability \(1\)). Let \(\mathcal{C}\) denote the set of feasible policies (that satisfy the constraints in \(\mathcal{P}\)). Note that any probing restrictions (e.g., constraints on which item may be probed next given prior observations) are captured by the feasible policy set \(\mathcal{C}\). Sometimes, we work with randomized policies, where each node in the decision tree corresponds to a probability distribution over items (rather than a single item). Randomized policies are not any stronger than deterministic ones: there is always an optimal deterministic policy for this class of problems. The stochastic problem \(\mathcal{P}\) is as follows (maximization problems are defined similarly). \[\text{minimize} \quad f(\sigma) = \mathbb{E}_{\mathbf{x}}\left[f(\sigma, \mathbf{x})\right] \quad \text{subject to} \quad \sigma \in \mathcal{C}.\]

Observe that the number of nodes in policy \(\sigma\) may be exponential. So, we are interested in “efficient” policies that can be implemented in polynomial-time for any realization \(\mathbf{x}\). For some stochastic problems like series systems and Pandora’s box, efficient optimal policies are known. On the other hand, there are many problems like stochastic knapsack, matching and set-cover, where optimal policies may not be efficient: in these cases, we will focus on (efficient) approximately optimal policies. We use \(\sigma^*\) to denote an optimal policy, and denote its expected cost by \(\mathtt{OPT}\). To ground this abstract setup, we note that the problems described in §1 (series testing, Pandora’s box, revenue management, and posted pricing) all fit naturally into this framework: the items \([n]\) correspond to the random variables being probed, the decision tree \(\sigma\) captures the adaptive probing order, and the cost function \(f(\sigma, \mathbf{x})\) encodes the problem-specific objective. We refer the reader to 5 for a full list of applications.

An \(\alpha\)-approximation algorithm for a stochastic problem \(\mathcal{P}\) takes as input the probability distributions \(\{\mathcal{D}_i\}_{i=1}^n\) (along with any objective/constraint parameters) and returns a policy that has expected cost at most \(\alpha\cdot \mathtt{OPT}\). We use the convention that for minimization problems, the approximation ratio \(\alpha\ge 1\), whereas for maximization problems \(\alpha\le 1\).

1.1.0.2 The Online Semi-Bandit Setting.

In this setting, the distributions \(\mathcal{D}_1, \ldots, \mathcal{D}_n\) are unknown (other parameters such as the cost function and constraints are known). Moreover, we have to repeatedly solve the stochastic problem \(\mathcal{P}\) over \(T\) time periods. We assume throughout the paper that \(T \geq n\). The distributions \(\{\mathcal{D}_i\}_{i=1}^n\) remain the same across all \(T\) periods. The goal is to simultaneously learn the distributions and converge to a good policy over time. At time \(t \leq T\), we use all prior observations to compute policy \(\sigma^t\). The policies \(\sigma^t\) may be different for each time \(t\in [T]\). We measure our learning algorithm in terms of expected total regret. For minimization problems, we define it as follows.

\[\begin{align} R(T) &= \mathbb{E}_{\mathbf{x}^1, \ldots, \mathbf{x}^T}\left[ \sum_{t=1}^T \left(f(\sigma^t, \mathbf{x}^t) - f(\sigma^*, \mathbf{x}^t)\right) \right] \notag \\ &= \mathbb{E}_{\mathbf{x}^1, \ldots, \mathbf{x}^T}\left[ \sum_{t=1}^T f(\sigma^t, \mathbf{x}^t) \right] - T\cdot \mathtt{OPT}. \label{eq:exp-regret1} \end{align}\tag{1}\] Here \(\mathbf{x}^{t}\) represents the realization at time \(t\). For conciseness, we use \(\mathbf{h}^{t-1}\) to denote the history until time \(t\); that is, \(\mathbf{h}^{t-1} = (\mathbf{x}^1, \ldots, \mathbf{x}^{t-1})\). Note that policy \(\sigma^t\) is itself random because it depends on prior observations, i.e., on the history \(\mathbf{h}^{t-1}\). The algorithm’s cost at time \(t\) is \(f(\sigma^t, \mathbf{x}^t)\), which depends additionally on the realizations \(\mathbf{x}^t\) at time \(t\). We can also re-write 1 as follows. \[\begin{align} R(T) & = \sum_{t=1}^T \mathbb{E}_{\mathbf{h}^{t-1}} \mathbb{E}_{\mathbf{x}^t}\left[f(\sigma^t , \mathbf{x}^t) \right] - T\cdot \mathtt{OPT}. \label{eq:exp-regret2} \end{align}\tag{2}\] Note that many of the stochastic optimization problems are known to be NP-hard, even when the distributions are known. Thus, we do not expect to learn policies that approach \(\mathtt{OPT}\). To get around this issue, we define the notion of \(\alpha\)-regret as follows.

\[\label{eq:appx-exp-regret1} \alpha\text{-}R(T) = \sum_{t=1}^T \mathbb{E}_{\mathbf{h}^{t-1}}\left[ \mathbb{E}_{\mathbf{x}^t}\left[f(\sigma^t , \mathbf{x}^t) \right] \right] - \alpha \cdot T\cdot \mathtt{OPT}.\tag{3}\]

We consider the setting of semi-bandit feedback, where the algorithm only observes the realizations of items that it probes. That is, at time \(t\), the algorithm only observes \(\left(x^t_i : i\in S(\sigma^t, \mathbf{x}^t)\right)\) where \(S(\sigma^t, \mathbf{x}^t)\) is the set of items probed by policy \(\sigma^t\) before it terminates.

1.1.0.3 Censored/Binary Feedback

We also extend our results to more restricted feedback settings, where the policy may not be able to directly observe \(\mathsf{X}_i\) for a probed item \(i\). In particular, we consider two such extensions. In censored feedback, the policy only observes the truncated realization \(\min(x_i , \tau)\) where \(\tau\) is some threshold. This is useful in revenue management applications with random demand. In binary feedback, the policy only observes whether or not the realization \(x_i\) is more than the threshold \(\tau\). This is useful in posted pricing and mechanism design.

1.2 Main Result and Techniques↩︎

For any stochastic problem instance \(\mathcal{I}\) and distribution \(\mathbf{{D}} = \{\mathcal{D}_i\}_{i=1}^n\), let \(\mathtt{OPT}_{\mathcal{I}}(\mathbf{{D}})\) denote the optimal cost of instance \(\mathcal{I}\) with r.v.s having distribution \(\mathbf{{D}}\). We first define a monotonicity condition for a stochastic problem \(\mathcal{P}\) which will be used in our main result.

Above, the \(\widetilde{O}\) notation is used to suppress (poly) logarithmic factors. If we do not care about polynomial running time then we can just set \(\alpha=1\), by computing the optimal policy for \(\mathcal{P}\) via a stochastic dynamic program, and obtain \(1\)-regret \(\widetilde{O}( n (\sqrt{k T}+k)f_{\max})\) for any monotone stochastic problem. The only general result of this type known prior to our work is a \(T^{2/3}\) regret bound for these problems using sample complexity bounds of [19]; specifically, this yields \(\widetilde{O}\left((nkT)^{2/3} \right)\) regret under semi-bandit feedback (see Appendix 7). While our result has better dependence in \(T\), the bound from [19] has better dependence in \(n\).

The regret bound in Theorem 1 is nearly optimal in the following sense. There is an \(\Omega(\sqrt{T})\) lower bound on the regret even in a very special case: see Appendix 8. Furthermore, if we move beyond our setting of independent-identically-distributed (i.i.d.) distributions across periods, to the “adversarial” setting with different distributions for each period, then there is a linear \(\Omega(T)\) lower-bound on regret for prophet inequality [20], which shows that sublinear regret is not possible for our class of problems in the adversarial case.

Technical Overview.

At a high-level, our algorithm is based on the principle of optimism in the face of uncertainty which is well-studied in the multi-armed bandits literature: see e.g., the UCB algorithm [21]. Given observations from previous rounds, our algorithm first constructs a modified empirical distribution \(\mathbf{{E}} = \{\mathcal{E}_i\}_{i=1}^n\) which stochastically dominates the true distribution \(\mathbf{{D}}\). It then executes policy \(\sigma\) given by the offline (approximation) algorithm under distribution \(\mathbf{{E}}\).

We now discuss how to bound the regret of the policy \(\sigma\) under the true distribution \(\mathbf{{D}}\). To keep things simple here, we assume that \(\alpha=1\). We also assume that the problem is up-monotone and has a minimization objective (our analysis for down-monotonicity and/or maximization objective is identical). The difficulty in our setting is that the decision to probe/observe an item is random: it depends on the choice of policy \(\sigma\) and the underlying distribution \(\mathbf{D}\) of items. In contrast, the classical multi-armed bandits setting allows direct control to the algorithm on which item to probe: so the UCB algorithm can control the rate of exploration of individual items and bound the regret of individual items in terms of this rate. How do we bound the rate of exploration of different items when we do not have direct control on which items are probed? Moreover, how do we bound the regret contribution of individual items in terms of their rate of exploration?

The key insight in our analysis is the following “stability” bound, which answers the above questions. Given product distributions \(\mathbf{{D}}\) and \(\mathbf{{E}}\), where \(\mathbf{{E}}\) stochastically dominates \(\mathbf{{D}}\), we show⁴ \[\begin{align} f(\sigma | \mathbf{{D}}) - f(\sigma^* | \mathbf{{D}}) \,\,&\leq \,\,f(\sigma | \mathbf{{D}}) - f(\sigma | \mathbf{{E}}) \,\,\leq\,\, f_{\max} \sum_{i=1}^n {Q}_{i}(\sigma) \cdot \epsilon_i, \end{align}\] where \(\sigma^*\) (resp. \(\sigma\)) is an optimal policy under \(\mathbf{{D}}\) (resp. \(\mathbf{{E}}\)), \(Q_i(\sigma)\) is the probability that policy \(\sigma\) probes item \(i\), and \(\epsilon_i\) is the total-variation distance between \(\mathcal{E}_i\) and \(\mathcal{D}_i\). The first inequality above follows from the monotonicity property. The second inequality requires analyzing the decision tree of \(\sigma\) carefully and is a key technical contribution of this paper (see §2.2).

The above stability bound can be interpreted as follows: the contribution of item \(i\) in the total regret is the probability that it is probed times the total variation error in estimating \(\mathcal{D}_i\). The dependence on the probability of probing is crucial here. This allows us to analyze the regret using a charging argument where we charge item \(i\) for regret in a pay-per-use manner. The paths in the execution tree of the online algorithm that probe \(i\) will pay for the error in estimation of \(\mathcal{D}_i\), but then \(\epsilon_i\) will also reduce along these paths. Moreover, we can bound the overall regret irrespective of the policy \(\sigma\) that is used at periods. The error \(\epsilon_i \approx \sqrt{1/m}\) when \(i\) has been probed \(m\) times in the past, which gives a total regret contribution of \(\sum_{m=1}^T \sqrt{1/m} = O(\sqrt{T})\) for any item. Finally, we lose an extra logarithmic factor to ensure that our empirical distribution \(\mathbf{E}\) stochastically dominates \(\mathbf{D}\) with high probability. We contrast our algorithm (and stability bound) with another algorithm that balances the explore-exploit trade-off in a different manner: the explore-then-commit algorithm.

Using the sample complexity bound of [19], it is easy to show that this algorithm achieves \(T^{2/3}\) regret; see Appendix 7 for details. However, each item is explored an equal number of times regardless of its quality and we might end up exploring some “low quality” items too many times. Our stability bound highlights a crucial difference between our algorithm and explore-then-commit: we only explore items that are actually probed by the (current) optimal policy. If there are low-quality items that are rarely used in the optimal policy, they will be explored infrequently in our algorithm: so their regret contribution is low. This explains why our approach achieves a near-optimal \(\sqrt{T\log T}\) regret bound compared to the \(T^{2/3}\) bound of the sampling-based approach.

1.3 Additional Results and Applications↩︎

We can also extend our main result to stochastic problems with continuous (or mixed) distributions. Here, we need to make some additional (mild) assumptions on the objective function. Informally, we require that for any fixed policy and leaf-node, the function value does not vary significantly with the variables \(\mathbf{x}\). This assumption is satisfied whenever the function value at a leaf-node is linear or monotone, which suffices for applications such as Prophet inequality and Pandora’s box. In this case, we are able to obtain \(\alpha\)-regret bounds similar to Theorem 1. The algorithm for the continuous setting is identical to the discrete case. The main new idea in the analysis is the use of a different distance-measure between distributions (the Kolmogorov–Smirnov distance) and modifying the proof of the “stability” bound appropriately. We also assume that the \(\alpha\)-approximation algorithm returns a \(k\)-threshold policy (defined in 3), which is a natural generalization of the discrete setting where any policy has at most \(k\) branches per node; see the remark at the start of 3 for further discussion.

Another extension of our main result is to censored and binary feedback. This extension requires discrete distributions and a more restrictive assumption on the objective function. Roughly speaking, we assume that the function value can always be determined based on the observed feedback (either censored or binary). This assumption is satisfied for the single-resource revenue management and sequential posted pricing problems. Again, we obtain regret bounds as in Theorem 1. While the high-level algorithm is the same, we need to design new sampling algorithms to construct the stochastically dominating distribution \(\mathbf{{E}}\). This requires more work because the feedback from a probed item \(i\) does not directly provide us with a sample of \(\mathsf{X}_i\). All the details of this extension are in 4. We note that the discrete-distribution assumption is necessary here in order to obtain \(\sqrt{T}\) regret: see Appendix 8 for a regret lower bound of \(\Omega(T^{2/3})\) under binary-feedback and continuous distributions.

We demonstrate the generality of our framework by obtaining polynomial time online learning algorithms for a number of stochastic optimization problems arising in domains of optimal stopping, revenue management, submodular optimization, knapsack and matching. For many problems, we get better regret bounds using our framework than what was known previously using problem-specific methods. We summarize our results in 1 and refer to 5 for further details.

1.4 Related Work↩︎

As mentioned earlier, stochastic optimization problems (under known distributions) have been studied extensively. Several papers have extended the classic prophet inequality [2] and Pandora’s box [1] results to more complex settings, e.g., [3], [22]–[26]. Moreover, good approximation bounds have been achieved for stochastic versions of various combinatorial optimization problems [8]–[10], [12]–[16], [27]–[29].

There has also been extensive work in online learning, where one considers unknown distributions (in the stochastic learning setting), see e.g., books [30], [31] and [32]. All our stochastic problems can be modeled as Markov decision processes (MDPs) with unknown transition probabilities, and there have been some works on achieving sublinear regret in this setting [33]–[35]. However, the regret bounds from these works have a polynomial dependence on the “state space” of the MDP, which in our setting, is exponential in \(n\) (the number of r.v.s). It is also known that any online algorithm for arbitrary MDPs incurs an \(\Omega(\sqrt{S\cdot T})\) regret, where \(S=\exp(n)\) is the size of the state space [36], [37]. In contrast, we obtain regret bounds that depend polynomially on \(n\).

Although both stochastic optimization and online learning have been subjects of comprehensive research, there has been relatively limited work at the intersection of these two domains. [20] obtained online learning algorithms for Pandora’s box and prophet inequality under bandit feedback, which is even more restrictive than semi-bandit feedback. Here, the algorithm only observes the realized objective value of its policy. [20] gave algorithms with \(1\)-regret \(O\left(n^3\sqrt{T}\log(T)\right)\) and \(O\left(n^{4.5}\sqrt{T}\log(T)\right)\) for prophet inequality and Pandora’s box respectively.

While our semi-bandit feedback model is more relaxed than bandit feedback, we think that it already captures the core issue of partial observations in learning policies. Moreover, under semi-bandit feedback we are able to obtain a general framework that applies to several stochastic optimization problems. Regarding bandit feedback for general stochastic problems, recent work of [38] and [39] established regret lower bounds that are exponentially dependent on the problem size for stochastic submodular maximization and MDPs respectively, suggesting that semi-bandit feedback is necessary for polynomial regret bounds in this generality.

There have also been several works studying sample complexity bounds for stochastic optimization problems. The goal in these works is to understand how much data is necessary and sufficient to guarantee near-optimal algorithms. Such results have been obtained for single-parameter revenue maximization [40], [41] and prophet inequality [42]. The recent work of [19] gives optimal sample complexity bounds for stochastic optimization problems that exhibit strong monotonicity, which is a stronger condition than our monotonicity definition. Informally, strong monotonicity requires that the optimal policy under one distribution also performs near-optimally under any stochastically dominating distribution, which is a strictly stronger condition than our monotonicity definition.

Another relevant line of work is on combinatorial multi-armed bandits (CMAB), which also involves semi-bandit feedback [43]–[46]. Here, there are \(n\) base arms that produce stochastic outcomes drawn from an unknown fixed distribution. There is also a collection \({\cal F}\subseteq 2^{[n]}\) of allowed “super arms”. In each period \(t\), the algorithm selects a super-arm \(S^t\in {\cal F}\) and observes the realizations of all arms \(i\in S^t\).

The result closest to ours is by [46], which considers a class of non-linear objectives satisfying a “monotone” condition and obtains a UCB-type algorithm achieving \(\alpha\)-regret of \(O(n\sqrt{T\log T})\) where \(\alpha\) is the approximation ratio for the offline problem. Our setting is more general because we need to select policies (not static subsets). When we select a policy, we do not know which arms will actually be observed. So, we only have an indirect control on what arms will be observed in each round. While our algorithm can be seen as a natural extension of [46], our analysis requires new ideas: in particular in proving the stability Lemma 4 and its use in bounding overall regret.

There are also some online-to-offline reductions that work in the adversarial setting (which is harder than our stochastic setting). In particular, [47] considered combinatorial optimization with linear objective functions, and obtained \(1\)-regret of \(O(n\sqrt{T})\) under full-feedback (assuming an exact offline algorithm). Then, [48] extended this result to linear problems with only an \(\alpha\)-approximation algorithm, and obtained \(\alpha\)-regret of \(O(n\sqrt{T})\) under full-feedback and \(O(nT^{2/3})\) under bandit-feedback. Recent work of [49], [50] considers certain combinatorial optimization problems with non-linear objectives, assuming an \(\alpha\)-approximation via a greedy-type algorithm. For such problems, [49] obtained \(\sqrt{T}\) regret under full-feedback and \(T^{2/3}\) regret under bandit-feedback. While these results work in the harder adversarial online setting, our result handles a much wider class of problems: we learn policies (rather than just subsets) and handle arbitrary objectives. As noted before, there is an \(\Omega(T)\) regret lower-bound for some of our applications in the adversarial setting.

1.5 Preliminaries↩︎

We present some preliminaries that are required in our algorithm and proofs.

We use \(\mathcal{D}\preceq_{\mathsf{SD}}\mathcal{E}\) to denote that distribution \(\mathcal{E}\) stochastically dominates \(\mathcal{D}\). For product distributions \(\mathbf{{D}} = \{\mathcal{D}_i\}_{i=1}^n\) and \(\mathbf{{E}}= \{\mathcal{E}_i\}_{i=1}^n\), we say that \(\mathbf{{E}}\) stochastically dominates \(\mathbf{{D}}\) if \(\mathcal{E}_i\) stochastically dominates \(\mathcal{D}_i\) for all \(i\in [n]\); we also denote this by \(\mathbf{{D}}\preceq_{\mathsf{SD}}\mathbf{{E}}\).

Let \(\operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathcal{D}, \mathcal{E})\) denote the total variation distance between discrete distributions \(\mathcal{D}\) and \(\mathcal{E}\). The total variation distance is half of the \(\ell_1\) distance between the two distributions, i.e., \(\operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathcal{D}, \mathcal{E}) = \frac{1}{2} \cdot \vert\vert \mathcal{D}- \mathcal{E}\vert\vert_1\). The following standard result (see, for example, Lemma B.8 in [51]) bounds the total variation distance between product distributions.

Consider independent r.v.s \(\mathsf{X}_1, \ldots, \mathsf{X}_n\) where \(\mathsf{T}_i\) denotes the domain of \(\mathsf{X}_i\). Let \(h\) be a function from \(\mathbf{{T}} = \mathsf{T}_1 \times \cdots \times \mathsf{T}_n\) to \([0, U]\); that is, \(h\) is a function on the outcomes of the random variables that is bounded by \(U\). Thus, for any \(\mathbf{x} \in \mathbf{{T}}\), \(h(\mathbf{x})\) denotes the value of \(h\) on the outcome \(\mathbf{x} = (x_1, \ldots x_n)\). Given a product distribution \(\mathbf{{P}}\) over the r.v.s, define \(h(\mathbf{{P}}) := \mathbb{E}_{\mathbf{x} \sim \mathbf{{P}}}\left[ h(\mathbf{x}) \right]\). The following useful fact bounds the difference in function value at two different distributions.

The following inequality bounds the deviation of the empirical CDF from the true CDF uniformly over all thresholds, and will be used to bound the total variation distance between our empirical distribution and the true distribution.

2 The Online Framework↩︎

In this section we present our main algorithm. We will assume access to an \(\alpha\)-approximation algorithm \(\mathtt{ALG}\) for the stochastic problem \(\mathcal{P}\). For concreteness, we assume that \(\mathcal{P}\) is a minimization problem. Thus, given an instance of \(\mathcal{P}\) (with a probability distribution for each item), \(\mathtt{ALG}\) finds a policy of expected cost at most \(\alpha\) times the optimum.

We also assume that \(\mathcal{P}\) is up-monotone; see Definition 1. The online framework for down-monotone problems and maximization problems is almost identical: the changes are explained in 2.4 and 2.5. Our online algorithm is based on the principle of optimism in the face of uncertainty, and is very simple to describe. At each time step \(t\), we construct an “optimistic” empirical distribution \(\mathbf{{E}}^t\) that stochastically dominates the true (unknown) distribution \(\mathbf{{D}}\). Then, we run the offline algorithm \(\mathtt{ALG}\) on this empirical distribution \(\mathbf{{E}}^t\) to obtain policy \(\sigma^t\), which is the online policy at time \(t\).

2.0.0.1 Computing stochastically dominating distributions.

Given i.i.d. samples of any random variable, we show that it is possible to compute a stochastically dominating empirical distribution that has a small total-variation distance from the true distribution.

The algorithm \(\mathtt{EmpStocDom}\) and proof of this result are deferred to 2.3. The main idea is to “shift” some probability mass in the usual empirical distribution from low to high values. In a previous version of this paper, we obtained a slightly simpler proof with a (worse) \(\operatorname{\mathtt{TV}-\mathtt{Dist}}\) bound of \(k\sqrt{\frac{\log (2/\delta)}{2m}}\).

Algorithm 1 describes our online framework, which uses algorithm \(\mathtt{EmpStocDom}\). We now analyze Algorithm 1, and prove Theorem 1. The basic idea in the analysis is that as we get more and more samples with increasing \(t\), the total variation distance between \(\mathbf{{E}}^t\) and \(\mathbf{{D}}\) reduces, and the policy \(\mathtt{ALG}(\mathbf{{E}}^t)\) will become closer and closer to the optimal policy.

2.2 Proving the Stability Lemma↩︎

We now prove Lemma 4. Recall that there are two product distributions \(\mathbf{E}=\{\mathcal{E}_i\}_{i=1}^n\) and \(\mathbf{D}=\{\mathcal{D}_i\}_{i=1}^n\) with \(\mathbf{D}\preceq_{\mathsf{SD}}\mathbf{E}\) and \(\operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathcal{E}_i, \mathcal{D}_i) \leq \epsilon_i\) for each \(i \in [n]\). Let \(\sigma=\mathtt{ALG}(\mathbf{E})\) be the policy returned by the (offline) \(\alpha\)-approximation algorithm, and \(\sigma^*\) be an optimal policy under distribution \(\mathbf{D}\).

We want to upper bound \(f(\sigma) - \alpha\cdot f(\sigma^*)\). Let \(\mathcal{C}\) denote the set of all feasible policies to the given instance. Then, \(\mathtt{OPT}(\mathbf{D}) = \min_{\tau \in \mathcal{C}} \mathbb{E}_{\mathbf{x}\sim \mathbf{D}}[f(\tau,\mathbf{x})] \text{ and } \mathtt{OPT}(\mathbf{E}) = \min_{\tau \in \mathcal{C}} \mathbb{E}_{\mathbf{x}\sim \mathbf{E}}[f(\tau,\mathbf{x})].\) We use \(f(\tau|\mathbf{{U}}) := \mathbb{E}_{\mathbf{x}\sim \mathbf{{U}}}[f(\tau,\mathbf{x})]\) to denote the expected cost of any policy \(\tau\) when the r.v.s have product distribution \(\mathbf{{U}}\). Note that \(f(\tau) = f(\tau|\mathbf{D})\) where \(\mathbf{D}\) is the true distribution. We now have: \[\begin{align} &f(\sigma) - \alpha\cdot f(\sigma^*) \,\, = \,\, f(\sigma| \mathbf{D}) - \alpha\cdot f(\sigma^*| \mathbf{D}) \notag \\ &= \,\, f(\sigma| \mathbf{D}) - f(\sigma| \mathbf{E}) +f(\sigma| \mathbf{E}) - \alpha\cdot f(\sigma^*| \mathbf{D}) \notag \\ & \le \,\, f(\sigma| \mathbf{D}) - f(\sigma| \mathbf{E}) + \alpha\cdot \mathtt{OPT}(\mathbf{E}) - \alpha\cdot f(\sigma^* | \mathbf{D}) \\ &= \,\, f(\sigma | \mathbf{D}) - f(\sigma | \mathbf{E}) + \alpha\cdot \mathtt{OPT}(\mathbf{E}) - \alpha\cdot \mathtt{OPT}(\mathbf{D}) \\ &\le\,\, f(\sigma | \mathbf{D}) - f(\sigma | \mathbf{E}). \end{align}\] Above, the first inequality uses the fact that \(\sigma\) is an \(\alpha\)-approximate policy to the instance with distribution \(\mathbf{E}\), the penultimate equality uses the fact that \(\sigma^*\) is an optimal policy for the instance with distribution \(\mathbf{D}\), and the final inequality is by up-monotonicity (Definition 1) and \(\mathbf{D}\preceq_{\mathsf{SD}}\mathbf{E}\). We note that stochastic dominance and monotonicity are only used to establish \(\mathtt{OPT}(\mathbf{E}) \le \mathtt{OPT}(\mathbf{D})\) in this final inequality; the rest of the proof holds more generally whenever one can construct a distribution \(\mathbf{E}\) satisfying this condition.

2.2.0.1 Equivalent view of adaptive policy \(\sigma\).

Let \(N\) denote the number of nodes in decision tree \(\sigma\) (this may be exponential, but it is only used in the analysis). Note that there is a partial ordering of the nodes of \(\sigma\) based on ancestor-descendent relationships in the tree. We index the nodes in \(\sigma\) from \(1\) to \(N\) according to this partial order, so that \(u<v\) for any node \(v\) that is a child of node \(u\). Recall that each node \(v\in \sigma\) is labeled by one of the \(n\) items. Note that the same item \(i\in [n]\) may label multiple nodes of \(\sigma\); however, in any policy execution (i.e., root-leaf path in \(\sigma\)) we will encounter at most one node labeled by item \(i\). Hence, we can equivalently view policy \(\sigma\) as having an item \(\mathsf{X}_v\) with independent distribution \(\mathcal{D}_v\) at each node \(v\in \sigma\). (This involves making several independent copies of each item, which does not affect the policy execution as at most one copy of each item is seen on any root-leaf path.)

2.2.0.2 Bounding \(| f({\sigma} | \mathbf{{D}}) - f({\sigma}| \mathbf{{E}})|\).

Based on the above view of \(\sigma\), we use \(\mathcal{D}_v\) (resp. \(\mathcal{E}_v\)) to denote the independent distribution at each node \(v\in \sigma\) under the joint distribution \(\mathbf{D}\) (resp. \(\mathbf{E}\)). Using the above indexing of the nodes in \(\sigma\), we define the following hybrid product distributions: for each \(v\in [N]\) let \(\mathbf{{H}}^v = \mathcal{D}_1 \times \cdots \times \mathcal{D}_{v} \times \mathcal{E}_{v+1} \times \cdots \times \mathcal{E}_N\). Observe that \(f(\sigma \mid \mathbf{{H}}^N) = f(\sigma \mid \mathbf{{D}})\) and \(f(\sigma \mid \mathbf{{H}}^0) = f(\sigma \mid \mathbf{{E}})\). Using a telescoping sum, we can write: \[f(\sigma \mid \mathbf{D}) - f(\sigma \mid \mathbf{E}) = \sum_{v=1}^N f(\sigma \mid \mathbf{{H}}^v) - f(\sigma \mid \mathbf{{H}}^{v-1}).\] Crucially, we now show that for every node \(v\in [N]\), \[\label{eq:stab-lemma-key} \mid f(\sigma \mid \mathbf{{H}}^v) - f(\sigma \mid \mathbf{{H}}^{v-1})\mid \,\, \leq \,\, f_{\max} \cdot Q_v(\sigma) \cdot \epsilon_v,\tag{7}\] where \(Q_v(\sigma)\) is the probability that \(\sigma\) reaches node \(v\) under distribution \(\mathbf{D}\) and \(\epsilon_v = \operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathcal{D}_v,\mathcal{E}_v)\).

We first complete the proof of the lemma using 7 . Note that for any node \(v\) labeled by item \(i\in [n]\), we have \(\epsilon_v=\operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathcal{D}_i, \mathcal{E}_i)\le \epsilon_i\). \[\begin{align} & \big| f(\sigma \mid \mathbf{D}) - f(\sigma \mid \mathbf{E}) \big| \notag \\ &\le \,\, \sum_{v=1}^N \big| f(\sigma \mid \mathbf{{H}}^v) - f(\sigma \mid \mathbf{{H}}^{v-1})\big| \notag \\ &\le \,\, f_{max} \cdot \sum_{v=1}^N Q_v(\sigma) \cdot \epsilon_v \notag \\ &= \,\, f_{max} \cdot \sum_{i=1}^n \epsilon_i \sum_{v\in [N] : labeled i} Q_v(\sigma) \notag \\ &= f_{max} \cdot \sum_{i=1}^n \epsilon_i \cdot \Pr[\sigmareaches a node labeled i]\notag \\ &=\,\, f_{max} \cdot \sum_{i=1}^n \epsilon_i \cdot Q_i(\sigma). \label{eq:stable-abs-diff} \end{align}\tag{8}\] The second equality uses the fact that the events “\(\sigma\) reaches \(v\)” where node \(v\) is labeled by \(i\), are mutually disjoint. The last equality uses the fact that the probability \(Q_i(\sigma)\) of probing \(i\) equals the probability of reaching some node \(v\in [N]\) labeled \(i\).

Towards proving 7 , we introduce the following notation. Let \(Q_v(\sigma \mid \mathbf{{U}})\) denote the probability that \(\sigma\) reaches node \(v\) under distribution \(\mathbf{{U}}\). Note that the event “\(\sigma\) reaches node \(v\)” only depends on the random realizations at the ancestor nodes of \(v\), which are all contained in \(\{u\in [N] : u < v\}\) (by our indexing of nodes). Hence, \[\label{eq:hybrid-reach-prob} Q_v(\sigma \mid \mathbf{{H}}^v) = Q_v(\sigma \mid \mathbf{{H}}^{v-1}) =Q_v(\sigma \mid \mathbf{{D}}) = Q_v(\sigma),\tag{9}\] because each node \(\{u\in [N] : u < v\}\) has the same distribution (\(\mathcal{D}_u\)) under \(\mathbf{D}\), \(\mathbf{{H}}^{v}\) and \(\mathbf{{H}}^{v-1}\).

Below, let \({\cal R}_v\) denote the event that \(\sigma\) reaches node \(v\). Using the fact that each node \(w\in [N]\setminus \{v\}\) has the same distribution (either \(\mathcal{D}_w\) or \(\mathcal{E}_w\)) under both \(\mathbf{{H}}^{v}\) and \(\mathbf{{H}}^{v-1}\), we get: \[\label{eq:stab-lemma-conditional-1} \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^v}\left[ f(\sigma, \mathbf{x}) \mid \overline{\cal R}_v \right] - \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^{v-1}}\left[ f(\sigma, \mathbf{x}) \mid \overline{\cal R}_v\right] \,\, = \,\,0.\tag{10}\] We now bound the difference in expectation conditional on event \({\cal R}_v\). Let \(\rho\) denote the subtree of \(\sigma\) rooted at \(v\) (including \(v\) itself). We also use \(\rho\) to denote the set of nodes in this subtree. Let \(L\) denote all leaf nodes in subtree \(\rho\), and for each \(\ell\in L\) let \(f_\ell\) be the function value accrued at leaf node \(\ell\). For any realization of the r.v.s in \(\rho\), \(\{x_w : w\in \rho\}\), we use \(\ell(\{x_w : w\in \rho\})\) to denote the (unique) leaf that is reached when subtree \(\rho\) is executed under this realization. This corresponds to following the branch labeled \(x_w\) out of each node \(w\in \rho\) (starting from node \(v\)). We now define function \(h\) that maps any realization \(\{x_w : w\in \rho\}\) to the function value \(f_k\) at the leaf \(k=\ell(\{x_w : w\in \rho\})\). By our assumption on the objective function of the stochastic problem, \(h\) is bounded between \(0\) and \(f_{max}\). We now define two product distributions on nodes of \(\rho\): \(\mathbf{{V}}_1 = \langle \mathcal{D}_v , \{ \mathcal{E}_{w} : w\in \rho\setminus v\} \rangle and \mathbf{{V}}_2 = \langle \mathcal{E}_v , \{ \mathcal{E}_{w} : w\in \rho\setminus v\} \rangle.\) Note that \(h(\mathbf{{V}}_1) = \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^v}\left[ f(\sigma, \mathbf{x}) \mid {\cal R}_v \right] and h(\mathbf{{V}}_2) = \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^{v-1}}\left[ f(\sigma, \mathbf{x}) \mid {\cal R}_v \right]\). Applying Lemma 2 to function \(h\) and product distributions \(\mathbf{{V}}_1\) and \(\mathbf{{V}}_2\), \[\begin{align} &\bigg| \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^v}\left[ f(\sigma, \mathbf{x}) \mid {\cal R}_v \right] - \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^{v-1}}\left[ f(\sigma, \mathbf{x}) \mid {\cal R}_v\right] \bigg|\notag \\ &\le \,\, f_{max}\cdot \operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathbf{{V}}_1, \mathbf{{V}}_2) \le \,\, f_{max}\cdot \operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathcal{D}_v , \mathcal{E}_v). \label{eq:stab-lemma-conditional-2} \end{align}\tag{11}\] The last inequality is by Lemma 1 and the fact that \(\mathbf{{V}}_1\) and \(\mathbf{{V}}_2\) only differ at node \(v\).

We now combine the conditional expectations from 10 and 11 . Using 9 , the probability of event \({\cal R}_v\) under both distributions \(\mathbf{{H}}^{v-1}\) and \(\mathbf{{H}}^{v}\) is the same, which equals \(Q_v(\sigma)\). So, \[\begin{align} &\mid f(\sigma \mid \mathbf{{H}}^v) - f(\sigma \mid \mathbf{{H}}^{v-1})\mid = \bigg| \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^v}\left[ f(\sigma, \mathbf{x}) \right] - \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^{v-1}}\left[ f(\sigma, \mathbf{x}) \right] \bigg|\\ & = Q_v(\sigma ) \cdot \bigg| \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^v}\left[ f(\sigma, \mathbf{x}) \mid {\cal R}_v \right] - \, \mathbb{E}_{\mathbf{x}\sim \mathbf{{H}}^{v-1}}\left[ f(\sigma, \mathbf{x}) \mid {\cal R}_v\right] \bigg|\\ &\le Q_v(\sigma ) \cdot f_{max}\cdot \operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathcal{D}_v , \mathcal{E}_v) = f_{max}\cdot Q_v(\sigma)\cdot \epsilon_v. \end{align}\] This completes the proof of 7 and Lemma 4.

2.3 Calculating a Stochastically Dominating Empirical Distribution↩︎

We now prove Theorem 3, that given i.i.d. samples from an unknown distribution \(\mathcal{D}\), constructs (w.h.p.) a stochastically dominating distribution \(\mathcal{E}\) with small total-variation distance.

In order to motivate this algorithm, consider the simple case that \(\mathcal{D}\) is a Bernoulli distribution, i.e., \(\mathcal{D}=\mathtt{Bern}(p)\) where \(p\) is the (unknown) probability of realizing to value \(1\). We first compute the empirical mean \(\widehat{p}\) of \(p\) from the \(m\) i.i.d. samples. Then, we set \(\mathcal{E}=\mathtt{Bern}\left(\widehat{p} + \sqrt{\frac{2\widehat{p}(1-\widehat{p})\log(2/\delta)}{m}} + \frac{7\log(2/\delta)}{3m}\right)\), where \(\delta>0\) is the algorithm’s failure probability. By Bernstein inequality [53], with probability \(1-\delta\) we have \(|p- \widehat{p}| \lesssim \sqrt{\frac{\sigma^2 \log(2/\delta)}{m}}+\frac{\log(2/\delta)}{m}\) where \(\sigma^2 = p(1-p)\) is the variance of the Bernoulli distribution (intuitively, \(\widehat{p}\) and \(p\) are roughly the same). It then follows that \(\mathcal{D}\preceq_{\mathsf{SD}}\mathcal{E}\) with probability at least \(1-\delta\). Indeed, this is the strategy used in many algorithms that use the principle of optimism under uncertainty, such as the upper-confidence-bound (UCB) algorithm [21]. We will prove Theorem 3 by giving such a construction for any distribution \(\mathcal{D}\) with finite support. We note that similar constructions and analysis have been used before, for e.g. in [19], [54], but their notion of approximating \(\mathbf{D}\) is different from our \(\operatorname{\mathtt{TV}-\mathtt{Dist}}\) condition.

Consider any distribution \(\mathcal{D}\) with support \(\{a_1,\ldots, a_k\}\) where \(a_1 < \cdots < a_k\), and let \(\{p_i\}_{i=1}^k\) denote the respective probabilities and \(\mathsf{X}\) the corresponding r.v. That is, \(\Pr(\mathsf{X}=a_i)=p_i\) for all \(i\in [k]\). The algorithm takes as input \(m\) i.i.d. samples \(x_1,\ldots, x_m \sim \mathcal{D}\). It defines the empirical distribution as \(\widehat{p}_i := \frac{1}{m} \cdot \sum_{j = 1}^m \mathbf{I}[x_j = a_i]\) for all \(i \in [k]\). Since this empirical distribution might not stochastically dominate \(\mathcal{D}\), the algorithm shifts some mass from lower to higher values in the support. However, this shift of mass needs to ensure that the resulting distribution is close to \(\mathcal{D}\) in terms of \(\operatorname{\mathtt{TV}-\mathtt{Dist}}\). Algorithm 2 describes the entire procedure. The proof proceeds by showing that the distribution \(\mathcal{E}\) returned by our algorithm stochastically dominates \(\mathcal{D}\) and is also a good approximation in terms of \(\operatorname{\mathtt{TV}-\mathtt{Dist}}\).

We will now show that the distribution \(\mathcal{E}\) returned by our algorithm stochastically dominates \(\mathcal{D}\) and is also a good approximation in terms of \(\operatorname{\mathtt{TV}-\mathtt{Dist}}\).

2.3.0.1 \(\mathcal{E}\) is a valid distribution.

We will show that \(\bar{p}_i\ge0\) for all \(i\in [k]\) and \(\sum_{i=1}^k\bar{p}_i=1\). If \(\bar{p}_k = 1\) then it is easy to see that \(\mathcal{E}\) is valid: all other probabilities \(\bar{p}_i=0\). If \(\bar{p}_k < 1\) then \(\widehat{p}_k<1-\epsilon\), which implies \(\sum_{i = 1}^{k-1} \widehat{p}_i = 1- \widehat{p}_k > \epsilon\). So, index \(y\in [k-1]\), and

\[\begin{align} \sum_{i = 1}^k \bar{p}_i \,\, &= \,\, \bar{p}_y + \sum_{i=y+1}^{k-1} \bar{p}_i + \bar{p}_k \\ &= \,\, \sum_{i=1}^y\widehat{p}_i -\epsilon + \sum_{i=y+1}^{k-1} \widehat{p}_i + \widehat{p}_k +\epsilon \, = \, 1. \end{align}\]

2.3.0.2 Stochastic dominance and TV bound.

Instead of using the classical Bernstein inequality, we need to use the “empirical Bernstein” because we only get access to the sample variance. This approach has also been used in [33] for UCB-VI with Bernstein bonus.

For each \(i\in [k]\), the empirical probability \(\widehat{p}_i\) in Algorithm 2 is the average of \(m\) independent Bernoulli random variables with mean \(p_i\); the sample variance of this random variable is \(\frac{m}{m-1} \widehat{p}_i(1-\widehat{p}_i)\). Theorem 4 shows that with probability \(1- \frac{\delta}{k}\) we have: \[|\widehat{p}_i - p_i| < \epsilon_i := \sqrt{\frac{2\widehat{p}_i(1-\widehat{p}_i) \log2k/\delta }{m}} + \frac{7\log2k/\delta}{3m}.\]

Henceforth, we assume the “good” event that \(|\widehat{p}_i - p_i| < \epsilon_i\) for all \(i\in[k]\). This event occurs with probability at least \(1-\delta\), by a union bound argument. Under this event, we will show that \(\mathcal{D}\preceq_{\mathsf{SD}}\mathcal{E}\) and \(\operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathcal{E}, \mathcal{D}) \leq \frac{3}{2}\epsilon\), where \(\mathcal{E}\) and \(\epsilon\) are defined in Algorithm 2. This would complete the proof of Theorem 3.

2.3.0.3 Bounding TV distance between \(\mathcal{D}\) and the empirical distribution.

Let \(\widehat{\mathcal{E}}\) denote the distribution with probabilities \(\{\widehat{p}_i\}_{i=1}^k\), which is just the empirical distribution. We will show that (under the good event), \[\label{eq:tv-emp} \operatorname{\mathtt{TV}-\mathtt{Dist}}(\widehat{\mathcal{E}}, \mathcal{D}) \leq \frac{1}{2} \epsilon.\tag{12}\] Indeed, by the definition of total variation distance, we have: \[\begin{align} &\operatorname{\mathtt{TV}-\mathtt{Dist}}(\widehat{\mathcal{E}}, \mathcal{D}) = \frac{1}{2} \sum_{i=1}^k |\widehat{p}_i-p_i |\leq \frac{1}{2} \sum_{i=1}^k \epsilon_i \\& \le \frac{7k\log2k/\delta}{6m}+\frac{1}{2}\sum_{i=1}^k \sqrt{\frac{2 \log (2k/\delta) }{m} \widehat{p}_i } \\ & \leq \frac{7k\log2k/\delta}{6m}+\frac{k}{2} \sqrt{\frac{2 \log(2k/\delta) }{m}\, \frac{1}{k} \sum_{i=1}^k\widehat{p}_i} \\ & = \frac{7k\log2k/\delta}{6m}+\frac{k}{2} \sqrt{\frac{2\log(2k/\delta) }{km}} \le \frac{1}{2} \epsilon. \end{align}\] The second inequality uses the definition of \(\epsilon_i\) and \(\widehat{p}_i\le 1\). The third inequality is by Jensen’s inequality for the concave function \(\sqrt{x}\). The last equality uses the fact that \(\sum_{i=1}^k \widehat{p}_i =1\) and \(\widehat{p}_i \in [0,1]\) for all \(i \in [k]\). This proves 12 .

2.3.0.4 Bounding TV distance between \(\widehat{\mathcal{E}}\) and \(\mathcal{E}\).

We consider two cases:

• If \(\bar{p}_k = 1\) then we have \(\widehat{p}_k\ge 1-\epsilon\) and \(\bar{p}_i=0\) for \(i\in [k-1]\), which implies: \[\begin{align} \operatorname{\mathtt{TV}-\mathtt{Dist}}(\widehat{\mathcal{E}}, \mathcal{E}) \,\, &= \,\, \frac{1}{2} \cdot \sum_{i =1}^k |\bar{p}_i - \widehat{p}_i| \\ &= \,\, \frac{1}{2} \left( |1-\widehat{p}_k| + \sum_{i =1}^{k-1} \widehat{p}_i \right) \,\, \le \,\, \epsilon. \end{align}\]

• If \(\bar{p}_k < 1\) then \(\bar{p}_k-\widehat{p}_k=\epsilon\) and using the definition of \(\bar{p}\) from [eq:emp-shift], \[\begin{align} &\operatorname{\mathtt{TV}-\mathtt{Dist}}(\widehat{\mathcal{E}}, \mathcal{E}) \,\, = \,\, \frac{1}{2} \cdot \sum_{i =1}^k |\bar{p}_i - \widehat{p}_i| \\ &= \,\, \frac{1}{2} \left( \epsilon + \left| \sum_{i =1}^{y} \widehat{p}_i - \epsilon - \widehat{p}_y \right| + \sum_{i =1}^{y-1} \widehat{p}_i \right) \,\, = \,\, \epsilon, \end{align}\] where the last equality used the choice of index \(y\) to conclude \(\left| \sum_{i =1}^{y} \widehat{p}_i - \epsilon - \widehat{p}_y \right| = \epsilon - \sum_{i=1}^{y-1} \widehat{p}_i\).

Hence, in either case, we have \(\operatorname{\mathtt{TV}-\mathtt{Dist}}(\widehat{\mathcal{E}}, \mathcal{E}) \le \epsilon\), which combined with 12 implies \(\operatorname{\mathtt{TV}-\mathtt{Dist}}(\mathcal{E}, \mathcal{D}) \,\, \le \,\, \operatorname{\mathtt{TV}-\mathtt{Dist}}(\widehat{\mathcal{E}}, \mathcal{E}) + \operatorname{\mathtt{TV}-\mathtt{Dist}}(\widehat{\mathcal{E}}, \mathcal{D}) \,\, < \,\, \frac{3}{2}\epsilon.\)

2.3.0.5 Showing \(\mathcal{D}\preceq_{\mathsf{SD}}\mathcal{E}\).

Again, we consider two cases:

• If \(\bar{p}_k = 1\) then \(\mathcal{E}\) puts all its mass on the highest value \(a_k\): so it is clear that \(\mathcal{D}\preceq_{\mathsf{SD}}\mathcal{E}\).

• If \(\bar{p}_k < 1\), consider any \(v \in \mathbb{R}\). If \(v \leq a_y\), \[\Pr(\mathsf{Z} \geq v) = 1 \geq \Pr(\mathsf{X} \geq v),\] \(\mathsf{X}\sim \mathcal{D}\) and \(\mathsf{Z}\sim \mathcal{E}\). If \(v > a_y\), then let \(i \ge y+1\) be the smallest index such that \(a_i \geq v\). We have \[\begin{align} \Pr(\mathsf{Z} \geq v) \,\, &= \,\, \sum_{j=i}^{k} \bar{p}_j =\sum_{j=i}^{k-1} \widehat{p}_j + \widehat{p}_k + \epsilon \\ &\geq \,\, \sum_{j=i}^{k} (p_i - \epsilon_i) + \epsilon \geq\Pr(\mathsf{X}\geq v)\,, \end{align}\] where the first inequality follows due to the good event. The second inequality uses the same analysis in 12 . Hence, \(\mathcal{D}\preceq_{\mathsf{SD}}\mathcal{E}\).

2.4 Framework for Down-Monotone Problems↩︎

The algorithmic framework described above assumed that the stochastic problem is up-monotone. We now describe the changes needed to handle down-monotone problems. See Definition 1 for the formal definition of up/down monotonicity. The only change to Algorithm 1 is that, at each step \(t\), we now need to compute distribution \(\mathbf{E}^t\) that is stochastically dominated by the true (unknown) distribution \(\mathbf{D}\). That is, we need \(\mathbf{E}^t\preceq_{\mathsf{SD}}\mathbf{D}\) rather than \(\mathbf{D}\preceq_{\mathsf{SD}}\mathbf{E}^t\). Such a distribution can be constructed in exactly the same way as Algorithm 2: we just order the values in the support in decreasing order \(a_1 > \cdots > a_k\) (instead of increasing order). Using the same proof as in §2.3, we obtain:

For the analysis, we use the following analogue of the stablility lemma with down-monotonicity.

The proof of this lemma is identical to that in 2.2 for up-monotonicity. Using Theorem 5 and Lemma 5, the proof of Theorem 1 (for down-monotone problems) is then identical to that for up-monotonicity (done earlier).

2.5 Framework for Maximization Problems↩︎

The algorithm/analysis so far assumed that the stochastic problem \(\mathcal{P}\) has a minimization objective. We now describe the changes needed to handle a maximization problem \(\mathcal{P}\). Given a product distribution \(\mathbf{{U}}\), we have \[\mathtt{OPT}(\mathbf{{U}}) = \max_{\tau\in \mathcal{C}} f(\tau|\mathbf{{U}}),\] where \(\mathcal{C}\) is the set of all feasible policies and \(f(\tau|\mathbf{{U}}) := \mathbb{E}_{\mathbf{x}\sim \mathbf{{U}}}[f(\tau,\mathbf{x})]\) is the expected value of policy \(\tau\) under distribution \(\mathbf{{U}}\). Note that \(f(\tau) = f(\tau|\mathbf{D})\) where \(\mathbf{D}\) is the true distribution. As before, we assume access to a \(\alpha\)-approximation algorithm \(\mathtt{ALG}\) for problem \(\mathcal{P}\); that is, given any problem instance (with item distributions), \(\mathtt{ALG}\) finds a policy of expected value at least \(\alpha\) times the optimum; here \(\alpha\le 1\). Furthermore, we assume that \(\mathcal{P}\) is down-monotone (up-monotone problems can be handled similarly). We note that the algorithm is unchanged: we still use Algorithm 1. The main change is in the expression for regret, which is reflected in the modified stability lemma:

The proof of this lemma follows the same approach as for Lemma 4.

\[\begin{align} \alpha\cdot f(\sigma^*) - f(\sigma) & = \alpha\cdot f(\sigma^*| \mathbf{D}) - f(\sigma| \mathbf{D}) = \alpha\cdot f(\sigma^*| \mathbf{D}) - f(\sigma| \mathbf{E}) +f(\sigma| \mathbf{E}) - f(\sigma| \mathbf{D}) \notag \\ & \le \alpha\cdot f(\sigma^* | \mathbf{D}) - \alpha\cdot \mathtt{OPT}(\mathbf{E}) + f(\sigma| \mathbf{E}) - f(\sigma| \mathbf{D}) \tag{13} \\ & = \alpha\cdot \mathtt{OPT}(\mathbf{D}) - \alpha\cdot \mathtt{OPT}(\mathbf{E}) + f(\sigma| \mathbf{E}) - f(\sigma| \mathbf{D}) \,\,\le\,\, f(\sigma | \mathbf{E}) - f(\sigma | \mathbf{D}) \tag{14}\\ & \le f_{max} \cdot \sum_{i=1}^n \epsilon_i \cdot Q_i(\sigma). \tag{15} \end{align}\] Inequality 13 uses the fact that \(\sigma\) is an \(\alpha\)-approximate policy to the instance with distribution \(\mathbf{E}\). In 14 , the equality uses the fact that \(\sigma^*\) is an optimal policy for the instance with distribution \(\mathbf{D}\), and the inequality is by down-monotonicity (Definition 1) and \(\mathbf{D}\preceq_{\mathsf{SD}}\mathbf{E}\). Finally, 15 follows from the upper bound on \(\bigg| f(\sigma | \mathbf{D}) - f(\sigma | \mathbf{E}) \bigg|\) from 8 . Lemma 6 then implies Theorem 1 for maximization, down-monotone problems: the proof is identical to that for minimization problems. Finally, the same guarantee holds when \(\mathcal{P}\) is up-monotone (per the discussion in §2.4).

3 Handling General Distributions↩︎

In this section, we extend results from the discrete setting to continuous (or even mixed) distributions. Here, each random variable \(\mathsf{X}_i \sim \mathcal{D}_i\) is supported over a bounded interval \([a, b]\).

We will assume that there is an \(\alpha\)-approximation algorithm \(\mathtt{ALG}\) for the stochastic problem \(\mathcal{P}\) that always returns a \(k\)-threshold policy, defined as follows. The policy is represented by a decision tree \(\sigma\), where each internal node is labeled by an item \(i \in [n]\) to probe, along with a list of thresholds \(\langle \tau_1, \dots, \tau_{k-1} \rangle\) that define a partition of \([a, b]\), into intervals \(\{J_1, \dots, J_k\}\). Each branch \(s \in [ k]\) is followed when the observed value \(x_i \in J_s\). This ensures that each node has at most \(k\) outgoing branches. We also assume that for any \(k\)-threshold policy \(\sigma\), the cost function \(f(\sigma, \mathbf{x})\) can be expressed in the following form:

\[\label{eq:representcts} f(\sigma,\mathbf{x})= \sum_{\ell : \text{leaf of } \sigma} \left( \prod_{i \in P_\ell} \mathbf{I}_{x_i \in J_\ell^i} \right) f_{\sigma, \ell}(\mathbf{x}), \qquad \forall~\mathbf{x}\in [a,b]^n,\tag{16}\] where \(f_{\sigma, \ell}(\mathbf{x})\) is the cost function associated with the leaf \(\ell\), \(P_\ell\) is the set of items probed along the path to \(\ell\) and \(J^i_\ell\) is the interval corresponding to the branch out of item \(i\) leading to leaf \(\ell\). We note that, given a realization \(\mathbf{x}\), only one summand in 16 will be non-zero (the one corresponding to the leaf \(\ell\) that \(\mathbf{x}\) traces).

In this section, we use \(f_{\sigma}(\mathbf{x}):[a,b]^n\rightarrow \mathbb{R}_+\) to denote the function \(f(\sigma,\mathbf{x})\) for a fixed policy \(\sigma\).

We need to make some continuity and boundedness assumptions on the leaf functions \(f_{\sigma, \ell}\). In order to state them formally, we start with some definitions.

We list several useful properties of BV functions [56].

• Any monotone function \(g\) over \([a,b]\) is BV and \(V_a^b(g) = |g(b)- g(a)|\).

• If \(g\) is a Lipchitz function over \([a,b]\) then it is BV and \(V_a^b(g) \le L(b-a)\), where \(L\) is the Lipchitz constant.

• For any BV function \(g\) over \([a,b]\), we have \(|g(x)| \,\le\, |g(a)| \,+\, V_a^b(g)\) for all \(x\in [a,b]\).

We now introduce a generalization of BV to high dimensions. Informally, this requires every 1-dimensional “slice” of \(f\) to be BV.

Similarly, we define coordinate-wise continuous functions as follows.

We assume that the objective function is non-negative and bounded, with \(f(\sigma, \mathbf{x})\le f_{\max}\). Additionally, we make the following (mild) assumptions on the “leaf functions” \(f_{\sigma, \ell}\) for any \(k\)-threshold policy.

We will be working with general distributions (discrete or continuous) here. We use the Kolmogorov–Smirnov (KS) distance instead of total variation (TV) distance here, since the TV distance between two distinct continuous distributions can equal \(1\) even when they are arbitrarily close, making TV-based bounds vacuous in this setting. To this end, we now introduce some definitions.

In our proof, we require a few standard results from analysis (stated below).

The following theorem allows us to bound the difference in expectation of a BV function over two different distributions.

3.0.0.1 Online to offline framework.

The overall algorithm and analysis is similar to that in the discrete case. Here, we focus on stochastic problems satisfying Assumption 1 and up-monotonicity. We also assume that there is an \(\alpha\)-approximation algorithm via \(k\)-threshold policies. These results also extend to down-monotone problems in a straightforward way.

At each time step \(t=1,\cdots T\), we first construct a (modified) empirical distribution \(\mathbf{E}^t\) that stochastically dominates the true distribution \(\mathbf{D}\) w.h.p. Then, we obtain a \(k\)-threshold policy \(\sigma^t\) by running the \(\alpha\)-approximation algorithm on distribution \(\mathbf{E}^t\). Finally, we run policy \(\sigma^t\) on a realization \(\mathbf{x}^t \sim \mathbf{D}\) and observe semi-bandit feedback. In the next two subsections, we prove the sampling lemma (that constructs a stochastically dominating distribution) and the stability lemma (that bounds the single-step regret).

3.1 Sampling Algorithm↩︎

Suppose the underlying distribution \(\mathcal{D}\) has CDF \(F(x)\). We will show how to construct an empirical distribution \(\mathcal{E}\) that dominates \(\mathcal{D}\) where \(\mathcal{D}\) and \(\mathcal{E}\) are close enough in terms of KS distance.

3.2 Stability Lemma↩︎

In this subsection, we present a version of the stability lemma that holds for general distributions and \(k\)-threshold policies.

3.3 Overall Regret↩︎

We can now combine the sampling and stability lemmas to obtain our result for general distributions. The proof is identical to that of Theorem 1 where we replace Theorem 3 with Theorem 11 and Lemma 4 with Lemma 7.

4 Censored and Binary Feedback↩︎

We further generalize our framework to accommodate settings with more restrictive feedback, enabling us to model more complex and realistic decision-making problems. Unlike the standard semi-bandit setting discussed so far, the algorithm here does not directly observe the realization \(x_i\) of a probed item \(i\). We consider two feedback models: censored and binary. The first model, called censored feedback, assumes that the algorithm only observes the realization of each random variable up to a chosen “threshold”. The second model, termed binary feedback, is even more limited: the algorithm only receives binary information indicating whether/not the random variable’s realization is above its chosen threshold.

We also focus on a restricted class of “threshold based” stochastic problems. We assume that all random variables are discrete with a finite support set \(\{a_1,\ldots, a_k\}\). A solution/policy for a threshold-based stochastic problem is given by a decision tree \(\sigma\) where each internal node is labeled by a pair \((c, i)\) where \(i\in [n]\) is an item and \(c\in [k]\) corresponds to a threshold value. When the policy \(\sigma\) reaches node \((c, i)\), it probes item \(i\) with threshold \(a_c\) and observes the following partial realization of \(X_i\) (depending on the feedback model).

• In censored feedback, the policy observes the truncated realization of \(\min\{\mathsf{X}_i, a_c\}\) and the branches out node \((c,i)\) correspond to this observation.

• In binary feedback, the policy observes the indicator \(\mathbf{I}_{\mathsf{X}_i \geq a_c}\) and the branches out node \((c,i)\) correspond to this observation.

Given a policy \(\sigma\) and realization \(\mathbf{x}\), we use \(S(\sigma, \mathbf{x})\) to denote the sequence of item-threshold pairs that are probed. We also make the following assumption on the objective function:

We note that this assumption is more restrictive compared to the previous results (Theorems 1 and 12). This is because at any leaf node of policy \(\sigma\) we may not know the precise realizations of probed items. Nevertheless, there are some interesting problems that satisfy this assumption (see below).

In the online setting, at time \(t\in [T]\), if the algorithm implements policy \(\sigma^t\) and the realizations are \(\mathbf{x}^t\sim \mathbf{D}\) then it observes the tuple \[\left\{\min(x_{i}^t ,a_c)\, :\, (c,i)\in S(\sigma^t, \mathbf{x}^t)\right\}\] under censored feedback, and the tuple \[\left\{\mathbf{I}_{x_i^t \geq a_c} \,:\, (c,i)\in S( \sigma^t, \mathbf{x}^t)\right\}\] under binary feedback. The goal is to minimize \(\alpha\)-regret as before.

4.0.0.1 Censored feedback application: Single Resource Revenue Management

A classical instance of censored feedback arises in the single resource revenue management setting [4]. Consider an airline with \(C\) units of seat capacity available for sale across multiple fare classes. The customer demand for each fare class is an independent random variable. We allocate portions of the capacity to different fare classes. When we choose to offer \(m\) seats to a specific fare class, we observe only the number of tickets sold—namely, the minimum of the demand and \(m\). The airline’s revenue (which is the objective function) also depends only on the number sold. This corresponds to censored feedback.

4.0.0.2 Binary feedback application: Sequential Posted Pricing (SPM).

Consider a seller who wants to sell a single item to a group of \(n\) buyers who have random valuations. The buyers arrive sequentially, and the seller presents each buyer \(i\) with a take-it-or-leave-it price \(p_i\). The first buyer \(i\) whose value exceeds the posted price \(p_i\) buys the item and the seller receives \(p_i\) dollars as revenue. Although the seller observes whether/not a particular buyer buys the item, the exact valuations remain unknown. This corresponds to binary feedback.

Naturally, one might attempt to incorporate censored and binary feedback into the semi-bandit framework by introducing additional independent copies of each random variable (one for each threshold). However, this approach can be problematic for several reasons. First, it may significantly increase the complexity of the original problem, making it difficult to find a good approximation result even in the offline setting with known distributions. Second, it can fail to preserve the monotone property of the original problem, which is crucial for our analysis.

Instead, we show how to extend our techniques from prior sections to the new censored/binary feedback settings. Our main results here are the following.

The high-level approach remains the same as in the semi-bandit setting. In the following two subsections, we establish the key sampling theorems and stability lemmas tailored to the new feedback models. We primarily focus on minimization up-monotone problems under the censored feedback setting; the same ideas apply to the binary-feedback setting as well. As with semi-bandit feedback, results for all the other combinations (minimization/maximization objective and up/down monotonicity) follow in an identical manner. The primary technical contribution is the sampling theorem, which addresses the challenge posed by limited observations.

4.1 New Sampling Algorithms↩︎

In this subsection, we focus on up-monotone stochastic problems. The analysis for down-monotone stochastic problems is similar. We will first present the sampling theorem for the censored feedback setting. Then, we provide a similar result for the binary feedback case. The key challenge in these settings is that, due to the limited nature of censored/binary feedback, we cannot directly control the total variation distance between the empirical and the true underlying distribution. Instead, we design an algorithm that controls the total variation distance at different threshold levels.

The sampling algorithm and analysis can be extended to binary feedback in a straightforward way. We now describe the changes needed.

4.2 Stability Lemma↩︎

We now describe the modifications to the stability lemma under censored feedback.

By an identical proof, using distributions \(\mathcal{D}_v \stackrel{d}{=} \mathcal{D}_{c,i}^B\) and \(\mathcal{E}_v \stackrel{d}{=} \mathcal{E}_{c,i}^B\) at each node \(v=(c,i)\), we obtain the following under binary feedback.

4.3 Overall Regret↩︎

We now prove the main theorem for the censored feedback setting (Theorem 15). The overall structure of the proof mirrors that of the semi-bandit setting: we combine a sampling theorem with the stability lemma to bound the regret.

Recall that, \(\mathcal{D}_i\) is the true distribution of item \(i\) and \(\mathcal{E}^t_i\) is the dominating distribution generated by Algorithm [alg:censored32calE32construction] in time step \(t\). For any \(i\in [n]\), \(c\in [k]\), let \(N_{c,i}^t\) be the number times the algorithm sampled \(\min\{\mathsf{X}_i, a_{c}\}\) before time \(t\).

We now define a good event \(G\) that corresponds to the condition in Lemma 10 holding true for all \(c \in[k]\), \(i\in[n]\) and \(t \in[T]\). Next, we complete the proof assuming that \(G\) holds.

4.3.0.1 Bounding the regret as a sum over time \(t\).

To bound the overall regret, it suffices to bound the expected regret \(R^t=f(\sigma^t) - \alpha\cdot f(\sigma^*)\) at each time \(t\in [T]\). For each time \(t\in [T]\), using the good event, we can apply Lemma 8 with distributions \(\mathbf{E}^t\), \(\mathbf{D}\), and parameters \(\epsilon_{c,i}^t = k\cdot \sqrt{\frac{6\log(knT)}{N_{c,i}^t}}\) to obtain \[\label{eq:censored-regret-t-stable} R^t \le f_{\max} \sum_{i=1}^n \sum_{c=1}^k {Q}_{c,i}(\sigma^t) \cdot \epsilon_{c,i}^t .\tag{26}\]

So, the overall regret is \[\alpha\text{-}R(T) \le f_{\max} \sum_{t=1}^T \mathbb{E}_{\mathbf{h}^{t-1}}\left[ \sum_{i=1}^n \sum_{c=1}^k {Q}_{c,i}(\sigma^t) \cdot \epsilon_{c,i}^t \right] = k f_{\max} \sqrt{6 \log(knT)} \cdot \sum_{t=1}^T \mathbb{E}_{\mathbf{h}^{t-1}}\left[ \sum_{i=1}^n \sum_{c=1}^k \frac{{Q}_{c,i}(\sigma^t) }{\sqrt{N^t_{c,i}}} \right] .\] Recall that \(\mathbf{h}^{t-1}=(\mathbf{x}^1,\cdots \mathbf{x}^{t-1})\) is the history until time \(t\). It now suffices to show \[\label{eq:censored-path-regret-sum} \sum_{t=1}^T \mathbb{E}_{\mathbf{h}^{t-1}}\left[ \sum_{i=1}^n \sum_{c=1}^k \frac{{Q}_{c,i}(\sigma^t) }{\sqrt{N^t_{c,i}}} \right] \le 2n\sqrt{kT}.\tag{27}\]

4.3.0.2 Proving 5 as a sum over decision paths.

Similar to the semi-bandit case, we define: \[Z_i^c(\mathbf{h}^T) := \sum_{t=1}^T \frac{\mathbf{I}\left[\text{ i probed by policy }\sigma^t(\mathbf{h}^{t-1})\text{ with threshold a_{c} }\right]}{\sqrt{N^t_{c,i}(\mathbf{h}^{t-1})}}, \quad \forall i\in [n] \, , c \in [k].\] Above, \(\mathbf{I}\) is the indicator function. By linearity of expectation, we have \[\begin{align} \mathbb{E}_{\mathbf{h}^T} \left[ Z_i^c(\mathbf{h}^T) \right] &= \sum_{t=1}^T \mathbb{E}_{\mathbf{h}^T} \left[ \frac{\mathbf{I}\left[i \text{ probed by }\sigma^t(\mathbf{h}^{t-1}) \text{ with } a_{c} \right]}{\sqrt{N^t_{c,i}(\mathbf{h}^{t-1})}}\right] \,\,=\,\,\sum_{t=1}^T \mathbb{E}_{\mathbf{h}^{t-1}, \mathbf{x}^t} \left[ \frac{\mathbf{I}\left[i \text{ probed by }\sigma^t(\mathbf{h}^{t-1}) \text{ with } a_{c} \right]}{\sqrt{N^t_{c,i}(\mathbf{h}^{t-1})}}\right] \notag \\ & =\sum_{t=1}^T \mathbb{E}_{\mathbf{h}^{t-1}} \left[ \frac{1}{\sqrt{N^t_{c,i}}} \cdot \Pr_{\mathbf{x}^t} [i \text{ probed by }\sigma^t \text{ with } a_{c}]\right] \,\, =\,\, \sum_{t=1}^T \mathbb{E}_{\mathbf{h}^{t-1}} \left[ \frac{Q_{c,i}(\sigma^t)}{\sqrt{N^t_{c,i}}} \right],\label{eq:censored-Zi} \end{align}\tag{28}\] where the second equality uses the fact that event {\(i\) probed by \(\sigma^t\) with \(c\)} only depends on \(\mathbf{h}^t = (\mathbf{h}^{t-1}, \mathbf{x}^t)\), the third equality uses the fact that \(N^t_{c,i}\) only depends on \(\mathbf{h}^{t-1}\) and that \(\mathbf{x}^t\) is independent of \(\mathbf{h}^{t-1}\), and the last equality is by the definition of \(Q_{c,i}(\sigma^t)\) and the fact that \(\mathbf{x}^t \sim \mathbf{D}\).

Using 28 and adding over \(i\in [n]\) and \(c\in [k]\), we get \[\sum_{t=1}^T \sum_{c=1}^k \sum_{i=1}^n \mathbb{E}_{\mathbf{h}^{t-1}}\left[ \frac{{Q}_{c,i}(\sigma^t) }{\sqrt{N^t_i}} \right] = \sum_{i=1}^n \sum_{c=1}^k \mathbb{E}_{\mathbf{h}^T} \left[ Z_i^c(\mathbf{h}^T) \right].\]

Therefore, proving 27 is equivalent to: \[\sum_{i=1}^n \sum_{c=1}^k \mathbb{E}_{\mathbf{h}^T}[Z_i^c(\mathbf{h}^T)] \le 2n\sqrt{kT}\label{eq:censored-path-regret-sum-2}.\tag{29}\]

Now, for any \(i \in [n]\) and \(c \in[k]\), we obtain: \[Z_i^c(\mathbf{h}^T) = \sum_{t=1}^T \frac{\mathbf{I}\left[i\text{ probed by }\sigma^t(\mathbf{h}^{t-1}) \text{ with } a_c \right]}{\sqrt{N^t_{c,i}(\mathbf{h}^{t-1})}} \leq \sum_{t=1}^{N^T_{c,i}} \frac{1}{\sqrt{t}} \leq 2 \sqrt{N^T_{c,i}}.\] The first inequality uses the fact that if item \(i\) gets probed with threshold \(a_{c}\) at time \(t\) then \(N_{c,i}^t =N_{c,i}^{t-1} +1\). Using Jensen’s inequality and the fact that the total number of probes for one item \(i\) is at most \(T\), we have: \[\sum_{c=1}^k \sqrt{N^T_{c,i}} \leq k \sqrt{\frac{\sum_{c=1}^k N^T_{c,i}}{k}} \le \sqrt{kT}.\] This completes the proof of 29 and hence 27 .

We note that our good event \(G\) holds with probability at least \(1 - \frac{1}{nT}\). As in the semi-bandit setting, we can convert the high-probability regret bound into an expected regret bound. This concludes the proof of Theorem 15.

The proof of Theorem 16 is identical: we just need to use the appropriate sampling result (Theorem 21) and stability lemma (Lemma 9).

5 Applications↩︎

In this section, we show that several stochastic optimization problems are covered by our framework, resulting in \(\sqrt{T\log T}\) regret online learning algorithm for all these problems. In each of these problems, the distributions of the random parameters are unknown to the online algorithm; all other (deterministic) parameters are known. We summarize the overall guarantees in 1, highlighting the dependence on \(n\), \(T\), the support size \(k\) of the underlying distributions (where applicable), and the distributional assumptions needed. See the corresponding subsection for more details and exact bounds.

5.1 Series Testing↩︎

We start with a simple problem: there are \(n\) components, where each component \(i\) is “working” independently with some known probability \(p_i\). To determine if any component \(i\in [n]\) is working, we need to perform a test, which costs \(c_i\). All \(n\) components must be working for the system to be functional. The goal is to test components sequentially to determine whether/not the system is functional, at the minimum expected cost. Note that testing stops once a failed component is found: so we do not observe all the outcomes and only have semi-bandit feedback. It is easy to show that this problem is up-monotone: this is a (simple) special case of Lemma 13 below. It is well-known that the natural greedy policy achieves the optimal cost [17]. So, using Theorem 1 with \(k=2\) (all r.v.s are binary), we obtain a polynomial time online learning algorithm for series testing having \(1\)-regret \(O(nC \sqrt{T\log T})\) where \(C = \sum_{i=1}^n c_i\) is the total cost.

5.2 Prophet Inequality↩︎

The Prophet Inequality [2], [59] is a fundamental problem in optimal stopping, which has also been used extensively in algorithmic game theory. The input consists of \(n\) rewards which arrive in a given fixed sequence, say \(\mathsf{X}_1, \ldots, \mathsf{X}_n\). Each reward \(\mathsf{X}_i\) is drawn independently from a known distribution \(\mathcal{D}_i\). We are interested in online policies, that upon observing each reward, selects or discards it immediately. The policy can select at most one reward, and it terminates right after making a selection (without observing any future reward). Note that we have semi-bandit feedback because only some of the rewards are observed in any policy execution. The goal is to maximize the expected selected reward. The classical results obtain a \(\frac{1}{2}\)-approximate policy relative to the “clairvoyant” optimal value \(\mathbb{E}[\max_{i=1}^n \mathsf{X}_i]\); there are also instances where no policy can achieve a better approximation to this benchmark. Here, we will compare to a more realistic non-clairvoyant benchmark: the optimal policy which is also constrained to make selection decisions in the given order (same as an algorithm). It is known that there is an optimal threshold-based policy: given thresholds \(\{\tau_i\}_{i=1}^n\), the policy selects \(i\) if and only if \(\mathsf{X}_i > \tau_i\). This is a \(2\)-threshold policy, as defined in 3.

Moreover, the prophet inequality problem is strongly monotone (see Lemma 28 in [19]), which implies that it is down-monotone. Finally, for any policy \(\sigma\) and leaf \(\ell\) (see 16 for details), the corresponding reward function is \(f_{\sigma,\ell}(\mathbf{x}) = x_\ell,\) where \(x_\ell\) denotes the value of the random variable at leaf \(\ell\). It is straightforward to verify that \(f_{\sigma,\ell}\) is coordinate-wise monotone (see Remark 14). Using Theorem 12, we get a polynomial time online learning algorithm for the the prophet inequality problem with unknown distributions that has \(1\)-regret \(O(n U \sqrt{T\log T})\) where all r.v.s are \([0,U]\) bounded. This improves upon the \(O(n^{3} U \sqrt{T} \log T)\) bound from [20], although the previous result holds in the stronger bandit-feedback model. We note that there are other learning-based results [60], [61] based on limited number of samples, that imply \(\frac{1}{2}\)-regret algorithms by comparing to the clairvoyant benchmark. Note that our guarantee and that of [20] are stronger because they do not incur any multiplicative approximation factor.

5.2.0.1 Combinatorial Prophet Inequalities.

The basic prophet inequality concept has also been extended to settings where there is some combinatorial feasibility constraint on the selected items. Here, we have \(n\) items with reward \(\mathsf{X}_i\sim \mathcal{D}_i\) for each \(i\in [n]\). In addition, there is a downward-closed set family \({\cal F}\subseteq 2^{[n]}\) that represents a generic feasibility constraint; the selected subset must be in \({\cal F}\). The \(n\) items arrive in a given fixed sequence. When item \(i\) arrives, if \(S\cup\{i\}\not\in {\cal F}\) where \(S\) is the set of previously selected items then item \(i\) is not considered for selection (and we do not observe \(\mathsf{X}_i\)); otherwise, the policy observes the value of \(\mathsf{X}_i\) and selects/discards item \(i\). Again, note that we only have semi-bandit feedback because only a subset of items is observed by the policy.

The performance of an online policy is compared to the clairvoyant optimum \(\mathtt{OPT}^{*}=\mathbb{E}[\max_{S\in {\cal F}} \sum_{i\in S}\) \(\mathsf{X}_i ]\). Many specific problems can be modeled in this manner:

• When \({\cal F}=\{S: |S|\le 1\}\), we get the classic prophet inequality, which has a \(\frac{1}{2}\) approximation.

• When \({\cal F}=\{S: |S|\le \kappa\}\), there is a \(1-\frac{1}{\sqrt{\kappa+3}}\) approximation [62], [63].

• When \({\cal F}\) corresponds to independent sets in a matroid, we obtain the matroid prophet inequality where again a \(\frac{1}{2}\) approximation is known [64].

• When \({\cal F}\) is the intersection of \(p\) matroids, a \(\frac{1}{e(p+1)}\) approximation is known [25].

• When \({\cal F}\) is given by matchings in a graph, a \(0.337\) approximation is known [65].

For the monotone property, note that we are comparing to the clairvoyant optimum \(\mathtt{OPT}^*\) (not the optimal policy). So, it suffices to prove down-monotonicity for \(\mathtt{OPT}^*\), which is immediate by stochastic dominance. The online policies in all these results are \(2\)-threshold policies. For any fixed policy \(\sigma\) and leaf \(\ell\) (see 16 ), we have \[\label{eq:32combinatorial32PI} f_{\sigma,\ell}(\mathbf{x}) = \sum_{i\in S_\ell} x_i ,\tag{30}\] where \(S_{\ell}\) denotes the set of r.v.s selected by the policy \(\sigma\) along the root-\(\ell\) path. It is clear that this function is coordinate-wise monotone. Therefore, using Theorem 12, we obtain \(\alpha\)-regret \(O(n U \sqrt{T\log T})\) for all the above combinatorial prophet inequalities where \(\alpha\) is the best (offline) approximation ratio; we assume that the r.v.s are \([0,U]\) bounded.

Some approximate regret bounds can also be obtained from previous work on single-sample prophet inequalities [60], [61], [66]. While the regret bounds via this approach are better (independent of \(T\)), they need to compare to approximation ratios that are often worse than the usual (known distribution) setting. In particular, [67] obtained an approximation ratio of \((\frac{1}{4}-\epsilon)\) for general matroids using \(O_\epsilon(n\log^4n)\) total samples, which implies a learning algorithm having \(\left(\frac{1}{4}-\epsilon\right)\)-regret of \(O_\epsilon(n\log^4n)\). In contrast, our results imply \(\frac{1}{2}\)-regret of \(\sqrt{T\log T }\), exactly matching the best-possible approximation ratio from [64].

5.3 Pandora’s Box↩︎

In this problem [1], we are given distributions \(\mathcal{D}_1, \ldots, \mathcal{D}_n\) such that r.v. \(\mathsf{X}_i \sim \mathcal{D}_i\). The realization of \(\mathsf{X}_i\) can be ascertained by paying a known inspection cost \(c_i\). Now, the goal is to find a policy to (adaptively) inspect a subset \(S \subseteq[n]\) of the random variables to maximize \(\mathbb{E}\left[\max_{i \in S} \mathsf{X}_i - \sum_{i \in S} c_i\right]\). Note that any policy only inspects a subset of items and we only receive feedback from these items, which corresponds to semi-bandit feedback. [1] obtained an optimal policy based on the “reservation value” for each item and probing items according to this value until the reward for an item exceeds all remaining reservation values. The reservation value \(r_i\) for an item \(i\) is such that \(\mathbb{E}[(\mathsf{X}_i - r_i)_+] = c_i\). We note that this optimal policy is \(2\)-threshold.

For the online setting, we assume that the r.v.s \(\mathsf{X}_i\) are \([0,U]\) bounded; the distributions may be discrete or continuous. It was shown in [19] (see Lemma 31 in that paper) that the Pandora’s box problem is strongly monotone, which implies that it is down-monotone. Similar to Prophet Inequality, for any policy \(\sigma\) and leaf \(\ell\) , the corresponding reward function is \(f_{\sigma,\ell}(\mathbf{x}) = \max_{i\in S_\ell} x_i -\sum_{i\in S_\ell} c _{i},\) where \(S_\ell\) is the set of inspected r.v.s at leaf \(\ell\). Hence \(f_{\sigma,\ell}\) is coordinate-wise monotone. Then combined with Theorem 12, we get a polynomial time online learning algorithm for the Pandora’s box problem with unknown distributions that has \(1\)-regret \(O(n (C+U) \sqrt{T\log T})\) where \(C = \sum_{i \in [n]} c_i\) is the total cost. Our regret bound improves upon the \(O(n^{4.5} (C+U) \sqrt{T} \log T)\) bound from [20], although the previous result holds in the stronger bandit-feedback model.

5.3.0.1 Variants of Pandora’s Box.

Our framework also applies to more general versions of Pandora’s problem that have been studied in prior work. We mention two such variants here.

In Pandora’s box with order constraints, in addition to the \(n\) r.v.s, there are precedence constraints that enforce that any r.v. \(\mathsf{X}_i\) may be selected only after all its predecessors have been selected. Although the original policy of [1] does not apply to this extension, [26] obtained a different optimal policy when the precedence constraints form a directed tree: this policy is also a 2-threshold policy. Hence, Theorem 12 implies an online learning algorithm for Pandora’s box with tree order constraints having \(1\)-regret \(O(n (C+U) \sqrt{T\log T})\), where \(C = \sum_{i \in [n]} c_i\) is the total cost and \(U\) is the bound on the r.v.s.

In the matroid Pandora’s box problem [23], [24], in addition to the \(n\) r.v.s \(\{\mathsf{X}_i\}_{i=1}^n\), there is a matroid \(\cal M\) with ground set \([n]\). The goal is to inspect a subset \(S\subseteq [n]\) of r.v.s and select a subset \(B\subseteq S\) such that \(B\) is independent in matroid \(\cal M\). The objective is to maximize \(\mathbb{E}\left[\sum_{j\in B} \mathsf{X}_j - \sum_{i\in S} c_i\right]\), the difference between the total selected value and inspection cost. We recover the original Pandora’s box problem when \(\cal M\) is a rank-1 uniform matroid. There is an optimal 2-threshold policy known for this variant [24]. This policy is also non-adaptive. By a similar argument as above, we can apply Theorem 12. Thus, we obtain an online learning algorithm for matroid Pandora’s box having \(1\)-regret \(O(n (C+U) \sqrt{T\log T})\), where \(C = \sum_{i \in [n]} c_i\) is the total cost and \(U\) is the bound on the r.v.s.

5.4 Stochastic Knapsack↩︎

This is a classic problem in stochastic optimization, which was introduced in [14] and has been studied extensively since [27], [68], [69]. There are \(n\) items with deterministic rewards \(\{r_i\}_{i=1}^n\) and random costs \(\{C_i \sim \mathcal{D}_i \}_{i=1}^n\). The realized cost \(C_i\) of item \(i\) is only known after selecting it. Given a knapsack budget \(B\), a policy selects items sequentially until the total cost exceeds \(B\). The objective is to maximize the expected total reward from items that fit in the knapsack. If there is an item that overflows the budget then it does not contribute to the objective. Note that only some subset of items is selected by a policy, and we only observe those costs as feedback. In 11 below, we show that this problem is up-monotone (assuming that the costs are discrete r.v.s).

There is an adaptive algorithm for stochastic knapsack, which is a \((\frac{1}{2}-\epsilon)\) approximation (for any \(\epsilon>0\)) [27]. Theorem 1 then implies an online learning algorithm with \((\frac{1}{2}-\epsilon)\)-regret of \(O(n R \sqrt{kT\log T })\) where \(k\) is the maximum support size and \(R = \sum_{i=1}^n r_i\) is the total reward. Our results also apply to the more general stochastic orienteering problem, where items are located at vertices in a metric space and we want to find a path with budget \(B\) on the total distance (from the edges in the path) plus cost (of the visited items). There is a non-adaptive \(\Omega(\frac{1}{\log\log B})\) approximation algorithm for this problem [28]. Here, we obtain \(\Omega(\frac{1}{\log\log B})\)-regret of \(O(nR \sqrt{kT\log T })\).

The proof requires the following theorem (also referred to as Strassen’s monotone coupling theorem) on coupling random variables under stochastic dominance [70], [71].

5.5 Stochastic Matching and Probing↩︎

In the stochastic matching problem [15], [16], there is an undirected graph \(G=(V,E)\) with edge-weights \(\{w_e\}_{e\in E}\), edge-probabilities \(\{p_e\}_{e\in E}\), and vertex bounds \(\{t_v\}_{v\in V}\). Each edge \(e\) is active independently with probability \(e\). However, the status (active/inactive) of an edge can only be determined by probing it. There is also a constraint on the set of probed edges: for any vertex \(v\), the number of probed edges incident to \(v\) must be at most \(t_v\). A solution/policy needs to to probe a subset of edges and select a matching \(M\) consisting of active edges. The objective is to maximize the expected weight of \(M\). Finally, there is a “query commit” requirement that any probed edge which is active must be included in the selected matching \(M\). Observe that in any policy execution, we only see the status of some subset of edges, which corresponds to semi-bandit feedback. This problem has been extensively studied, see e.g., [15], [16], [72], [73]. The current best approximation ratio is \(0.5\) for the unweighted case [72] and \(0.382\) for the weighted case [73]. We show in Lemma 12 below that the stochastic matching problem is down-monotone. So, Theorem 1 with \(k=2\) (as all r.v.s are binary) implies an online learning algorithm for stochastic matching having \(0.382\)-regret of \(O(n W \sqrt{T\log T })\) where \(W = \sum_{e\in E} w_e\) is the total weight.

In fact, our result applies to the much more general stochastic probing problem, as defined in [10]. Here, we have a set \(E\) of stochastic items with weights \(\{w_e\}_{e\in E}\) and probabilities \(\{p_e\}_{e\in E}\). Each item is active independently with probability \(p_e\), and this status can only be determined by probing \(e\). We now have two downward-closed constraints: an inner constraint \({\cal F}_{in}\) and an outer constraint \({\cal F}_{out}\). We want to probe a set \(Q\) of items subject to the outer constraint (i.e. \(Q\in {\cal F}_{out}\)) and select a subset \(S\subseteq Q\) of active (probed) items satisfying the inner constraint (i.e. \(S\in {\cal F}_{in}\)). The objective is to maximize the expected weight of the selected items \(S\). We again have the query-commit requirement that any active probed item must be selected into the solution \(S\). When both inner/outer constraints are \(k_{in}\) and \(k_{out}\) systems, there is a \(\frac{1}{k_{in} + k_{out}}\) approximation for the unweighted case and an \(\Omega(\frac{1}{(k_{in} + k_{out})^2})\) approximation for the weighted case [10]. When the \(k\)-systems are intersections of matroids, [11] gave an improved adaptive algorithm with approximation ratio \(\frac{1}{k_{in} + k_{out}}\), even for the weighted case.

5.6 Stochastic Covering Knapsack↩︎

Here, we have \(n\) items with deterministic costs \(\{c_i\}_{i \in [n]}\) and (independent) random rewards \(\{\mathsf{R}_i\}_{i \in [n]}\). There is a known probability distribution \(\mathcal{D}_i\) for \(\mathsf{R}_i\); we assume discrete distributions here. Given a target \(Q\), we need to select items until the total observed reward is at least \(Q\) (or we run out of items). The objective is to minimize the expected cost. Note that we only observe items until the target is achieved, which corresponds to semi-bandit feedback. There is an adaptive \(3\)-approximation algorithm for this problem [13]. By a proof identical to that of Lemma 11, we get:

So, using Theorem 1, we obtain a polynomial time online learning algorithm for stochastic min-knapsack having \(3\)-regret \(O(n C \sqrt{kT\log T })\) where \(C = \sum_{i=1}^n c_i\) is the total cost and \(k\) is the maximum support size.

5.6.0.1 Stochastic \(Q\)-TSP.

This is the stochastic variant of the classical \(Q\)-TSP problem [74]. An instance of the problem comprises a metric \((V, d)\) with a root vertex \(r \in V\). There are random rewards \(\{\mathsf{R}_v\}_{v \in V}\) associated with the vertices. All reward distributions are given as input, but the realized reward \(\mathsf{R}_v\) is only known when vertex \(v\) is visited. We assume that all reward distributions are discrete. Given a target \(Q\), the goal is to find an (adaptive) tour originating from \(r\) that collects a total reward at least \(Q\) (or runs out of vertices), at the minimum expected length.

A constant-factor approximation algorithm for stochastic \(Q\)-TSP was obtained in [75]. Applying 1, we obtain a polynomial time online learning algorithm for stochastic \(Q\)-TSP having \(O(1)\)-regret \(O(nD \sqrt{kT\log T })\) where \(D = \sum_{v\in V} d_{rv}\) corresponds to an upper bound on the (full) TSP cost.

5.7 Stochastic Submodular Optimization↩︎

Consider a monotone submodular function \(f:2^E\rightarrow \mathbb{Z}_+\) defined on a groundset \(E\). Constrained submodular maximization involves selecting a subset \(S\subseteq E\) of items in a downward-closed family \({\cal F}\subseteq 2^E\), that maximizes the function value \(f(S)\). This is a fundamental problem in combinatorial optimization and good approximation algorithms are known for a variety of constraints \({\cal F}\) such as cardinality, matroids and knapsacks [76]–[79]. We consider a stochastic variant, as in [7], [12], and [80], where each item \(i\in E\) is active independently with some probability \(p_i\) (and inactive otherwise).⁵ Moreover, the function value is accrued only on active items. The active/inactive status of any item is only known after selecting it. The goal now is to select a subset \(S\in {\cal F}\) sequentially (and adaptively) so as to maximize the expected function value from the selected active items, i.e., \(\mathbb{E}_{S,A}\left[ f(S\cap A)\right]\) where \(A\subseteq E\) is the random set of active items. Note that we can only select (and observe) a constrained subset of items, which corresponds to semi-bandit feedback. When \({\cal F}\) is a single matroid constraint, [7] obtained a \((1-\frac{1}{e}-\epsilon)\)-approximation algorithm for the stochastic submodular maximization problem. Later, [12] and [80] showed that a \(\rho\)-approximation algorithm for deterministic submodular maximization under any constraint \({\cal F}\) can be used to obtain a \(\frac{\rho{2}}{None}\)-approximation algorithm for the stochastic problem under constraint \({\cal F}\). It is easy to see that this problem is down-monotone. So, Theorem 1 with \(k=2\) (binary r.v.s) implies a \((1-\frac{1}{e}-\epsilon)\)-regret of \(O(n F \sqrt{T\log T })\) for stochastic submodular maximization over a matroid constraint, where \(F\) is the maximum function value. Combined with the result of [80], we also obtain online learning algorithms for more general constraints \({\cal F}\). Notably, our result improves upon the prior result of [81] that obtains \(\left(1 - \frac{1}{e}\right)\)-regret of \(\widetilde{O}(nFT^{2/3})\) in the semi-bandit feedback model for the stochastic submodular maximization problem when \(\mathcal{F}\) corresponds to a cardinality constraint.

5.7.0.1 Stochastic Submodular Cover.

In the classic submodular cover problem [82], there is a monotone submodular function \(f:2^E\rightarrow \mathbb{Z}_+\) defined on a groundset \(E\), where each item \(i\in E\) has some cost \(c_i\). We assume that the function is integer-valued with maximal value \(Q\). The goal is to select a subset \(S\subseteq E\) that “covers” the function, i.e., \(f(S)=Q\). The objective is to minimize the total cost \(\sum_{i\in S} c_i\) of the chosen items. Note that the submodular cover problem generalizes set cover. It is well-known that this problem can be approximated within a factor \(1+\ln(Q)\) [82], and no better approximation is possible [83]. We consider a stochastic version, where each item \(i\in E\) is active independently with probability \(p_i\), and the function value is accrued only on active items. The goal now is to select items sequentially (and adaptively) so as to cover function \(f\) (or run out of items to select), at the minimum expected cost. This problem has been studied extensively [8], [9], [84], and [84] obtained a \(1+\ln(Q)\) approximation algorithm for it. Using the fact that the function \(f\) is monotone, it is easy to see that stochastic submodular cover is up-monotone. So, using Theorem 1 with \(k=2\), we obtain a polynomial time online learning algorithm for stochastic submodular cover having \((1 + \ln Q)\)-regret \(O(nC \sqrt{T\log T})\) where \(C = \sum_{i=1}^n c_i\) is the total cost.

5.8 Single Resource Revenue Management↩︎

We now consider the single resource revenue management problem (\(\mathsf{SRM}\)). A firm (say, airline) has \(C\) units of a certain resource (for example, seats on a flight). This resource must be allocated among \(n\) fare classes, where each unit sold in class \(i\) generates revenue \(p_i\). Demands for these fare classes arrive sequentially: we use the convention from [4] that classes arrive in the order \(n, n-1,\ldots ,1\). This problem is often studied under the “low before high” assumption that \(p_n < \cdots < p_1\), which reflects the fact that cheaper fares are offered earlier.

The demands are random and independent across classes: we use \(\mathsf{X}_i\sim \mathcal{D}_i\) to denote the demand for class \(i\). We assume that each \(\mathsf{X}_i\) is a discrete r.v. with support \(\{0, 1, \ldots, C\}\). The goal is to decide how much capacity to make available for each fare class so as to maximize the expected total revenue. For each class \(i=n,\ldots,1\), the firm needs to first decide on the number \(b\) of units offered (which cannot exceed the available units) and then the demand \(\mathsf{X}_i\) materializes, which reduces the available units by \(\min(\mathsf{X}_i , b)\). When the demand distributions are unknown, censored feedback is the most natural, where we observe only the minimum of the actual demand and the offered capacity. As an application of Theorem 15 we obtain a polynomial-time online learning algorithm for \(\mathsf{SRM}\) with \(1\)-regret \(O(nC^2 p_{\max}\sqrt{CT\log(CT)})\) where \(p_{\max}\) is the maximum price. This result directly improves the dependence on \(T\) compared to [85], whose algorithm achieves a regret of \(\widetilde{O}\left(T^{1-\frac{\beta}{2^{n-1}}}\right)\) for some constant \(\beta \in (0, 1)\). Moreover, it also improves upon the result of [86], who obtain regret \(O( \sqrt{p_{\max}}C^{2n-3} \cdot \sqrt{T})\), thereby removing the exponential dependence on \(n\) in the regret.

In order to apply Theorem 15, we first note that the objective satisfies Assumption 2. Indeed, any policy for \(\mathsf{SRM}\) involves setting a threshold at each step \(i\) corresponding to the number of units offered to class \(i\). Moreover, the increase in the \(\mathsf{SRM}\) objective at any step is completely determined by the (censored) observation at that step: so the function value at each leaf node of the policy is a constant. Next, we prove that \(\mathsf{SRM}\) is down-monotone. This proof relies on some known structural properties of the exact dynamic programming algorithm for \(\mathsf{SRM}\)(with known distributions). We now summarize these properties; see [4] for more details.

The value functions in the dynamic program (DP) are as follows. For each \(i\in [n]\) and \(c\le C\), let \(V_i(c)\) denote the optimal total expected revenue from classes \(i,i-1, \ldots, 1\) given that we have \(c\) units of capacity remaining before the arrival of class \(i\) demand. The optimal value of the \(\mathsf{SRM}\) instance is \(\mathtt{OPT}=V_n(C)\).

The decision for class \(i\) is to determine the number of units offered to class \(i\) demand; equivalently, we need to decide the number of units to protect for future classes \(i-1, \ldots, 1\). Specifically, if \(b \in \{0, 1, \ldots, c\}\) units are protected, then \(c - b\) units are available for class \(i\) demand. The amount sold to class \(i\) equals \(\min(c-b, \mathsf{X}_i)\) and the remaining capacity is \(c - \min(c-b, \mathsf{X}_i)\), which are both random. The revenue generated, also a random variable, is \(p_i \cdot \min(c-b, \mathsf{X}_i)\). We let \(W_i(b, c)\) denote the optimal expected revenue from classes \(i,i-1, \ldots, 1\) given that we have \(c\) units of capacity remaining before the arrival of class \(i\) and we protect \(b \leq c\) units. Based on the discussion above,

\[\begin{align} W_i(b, c) &= \,\, p_i \cdot \mathbb{E}[\min(c- b, \mathsf{X}_i)] \notag \\ & \qquad + \mathbb{E}[V_{i-1}(c - \min(c-b, \mathsf{X}_i))].\label{eqn:decision-dp} \end{align}\tag{31}\] The first term is the expected revenue obtained from class \(i\) given that we offered \(c-b\) units, and the second term is the expected revenue from classes \(i-1, \ldots, 1\) when \(\max(b, c-\mathsf{X}_i)\) units of capacity remain. Now, observe that \(V_i(c) = \max \left\{ W_i(b, c)\,:\, 0\le b\le c\right\}\). The base case \(V_1(c)=p_1\cdot \mathbb{E}[\min(c,\mathsf{X}_1)]\) involves protecting \(0\) units regardless of \(c\) (as there is no demand after this).

We will use the following two properties of this DP (see Proposition 1.5 and Theorem 1.6 in [4]).

5.9 Sequential Posted Pricing↩︎

We now consider a pricing problem. A seller offers a service to \(n\) customers, where each customer’s valuation is modeled as a discrete independent random variable \(\mathsf{X}_i \sim \mathcal{D}_i\). We assume (by scaling) that the values are bounded in \([0,1]\) and that \(k\) denotes the maximum support size. The seller must satisfy a feasibility constraint given by a downward-closed set family \(\mathcal{F} \subseteq 2^{[n]}\). This means that a subset \(S\) of customers can be served if and only if \(S\in {\cal F}\). We are interested in designing a truthful mechanism that maximizes the expected revenue. [5] provides an optimal mechanism for this class of problems, but it is computationally hard to implement. Therefore, there has been much focus on simpler mechanisms that are approximately optimal. We consider

Sequential Posted-Price Mechanisms (SPMs) that were introduced by [6]. Here, each buyer \(i\) is offered a take-it-or-leave-it price \(p_i\) in some sequence. We consider two variants: Adaptive Sequential Posted-Price Mechanism (ASPM) where the seller can (adaptively) choose the order in which to offer customers, and Fixed Order Sequential Posted-Price Mechanism (FSPM) where the order of customers is fixed and known upfront. Formally, in ASPM, the seller’s policy is represented as a decision tree, where each internal node is labeled with a tuple \((i, p_i)\), denoting that customer \(i\) is offered price \(p_i\); each node has two outgoing branches corresponding to whether the customer accepts or rejects the offer. In FSPM, the policy only needs to choose the prices \(p_i\) as the customers will be considered in a fixed order \(1, \ldots, n\). The seller collects revenue from all customers who accept their offered price, and the selected set of customers must lie in \(\mathcal{F}\).

For the setting with unknown distributions \(\mathcal{D}_i\), we use our online framework with binary feedback: in each period, the seller chooses a policy and only observes which customers accepted their offers. As an application of Theorem 16, we obtain \(\alpha\)-regret of \(O\left(n \sqrt{kT \log(knT)}\right)\), where \(\alpha\) is the best approximation ratio for the SPM instance with known distributions. Below, we list some concrete SPM applications.

• When \(\mathcal{F} = \{S \subseteq [n] : |S| \leq \kappa\}\) (uniform matroid of rank \(\kappa\)), the optimal policy for FSPM can be computed efficiently using dynamic programming; so \(\alpha=1\). For ASPM under this feasibility constraint, [87] provide a polynomial-time approximation scheme, so \(\alpha=1-\epsilon\) for any fixed \(\epsilon>0\).

• When \(\mathcal{F}\) corresponds to the independent sets of a general matroid, [18] provides a \((1-\frac{1}{e})\)- approximation algorithm for ASPM.

• When \(\mathcal{F}\) is an intersection of a constant number of matroid, knapsack and matching constraints, [25] provide a framework to achieve an \(\alpha=\Omega(1)\)-approximation algorithm for ASPM.

Previous work by [88] obtained online algorithms for FSPM under a uniform matroid of rank one, i.e., the seller can serve only one customer and the customers arrive in a fixed order. Notably, they considered the bandit feedback model, which, in this specific setting, coincides with the binary feedback model. Although the bandit feedback model only reveals the final revenue, one can recover the identity of the customer who accepted the service by introducing arbitrarily small perturbations to the posted prices. Our result for this case is a \(1-\)regret of \(O\left(n \sqrt{kT \log(knT)}\right)\), which improves upon the \(O(n^{2.5}k\sqrt{T} \log T+ n^5 k \log^2 T)\) bound from  [88]. We note that this paper also obtained \(poly(n)\cdot \sqrt{T}\) regret for continuous distributions (under some regularity assumption).

Note that any SPM policy chooses a threshold (the price \(p_i\)) for each customer \(i\). Moreover, the increase in the objective value for any customer \(i\) is determined by the binary observation \(\mathbf{I}_{\mathsf{X}_i \geq p_i}\). So, SPM satisfies Assumption 2. We now prove monotonicity of SPM. Without loss of generality, for any decision tree (policy) \(\Pi\), we assume that the left branch out of a node \((i,p_i)\) corresponds to customer \(i\) accepting while the right branch corresponds to rejection.

Using an identical proof as above, we can also prove that FSPM (the fixed order variant) is down-monotone.

6 Conclusion↩︎

In this paper, we presented a general online learning framework that achieves \(\widetilde{O}(\sqrt{T})\) regret for monotone stochastic optimization problems under semi-bandit feedback. We also extended our results to the more restrictive censored and binary feedback settings. We conclude by highlighting several interesting directions for future work.

6.0.0.1 Strong monotonicity.

Our framework requires only the (weaker) monotonicity condition. A natural question is whether leveraging the stronger condition of strong monotonicity [19] can yield improved dependence on \(n\) and \(f_{\max}\) in the regret bound. Recent work of [89] has made progress in this direction for Pandora’s box and prophet inequality, obtaining bounds with an improved \(\sqrt{n}\) factor. Extending such improvements to all strongly monotone problems remains an interesting open question.

6.0.0.2 Dynamic environments.

Our framework assumes that the underlying distributions remain identical across rounds, which is necessary for sublinear regret in the worst case (as evidenced by the \(\Omega(T)\) lower bound in the adversarial setting for prophet inequality [20]). Designing algorithms for more structured dynamic environments (e.g., through the lens of distributionally robust optimization) is an interesting direction for future work.

6.0.0.3 Restrictive action selection.

Another natural extension is to settings where the set of available actions itself varies across rounds; for example, a random subset of items is available in each round, akin to the sleeping bandits setting. Such an extension would require redefining the benchmark because a static optimal policy may no longer be sufficient.

Acknowledgement↩︎

We thank Ziyun Chen for pointing out some missing assumptions in our result for continuous distributions, which was stated in an earlier version of this paper. This observation lead us to the corrected statement and proof of Theorem 12.

Appendix↩︎

7 Sampling-based Algorithms↩︎

A stronger monotonicity condition is that of strong monotonicity [19], defined next.

We note that strong monotonicity implies monotonicity. In prior work, [19] gave optimal sample complexity bounds for stochastic optimization problems that exhibit the strong monotonicity condition. They also proved this property for problems including Prophet inequality and Pandora’s box. We make use of this property in §5, when we apply our result to these problems. Below, we assume that \(f_{max}=1\) by scaling.

Below, we discuss what regret bounds can be achieved via this sampling-based approach, in order to compare to our results. In the full-feedback model, one can obtain regret bounds of \(\sqrt{nT\log T}\), which is nearly optimal. However, for semi-bandit feedback that we consider (and for bandit feedback), such a “reduction” from sample-complexity bounds only provides a sub-optimal \(\widetilde{O}(T^{2/3})\) regret. Therefore, we need new ideas to get the optimal \(\widetilde{O}(\sqrt{T})\) regret bound in the semi-bandit model, which we do in this paper.

7.0.0.1 Full-feedback.

Recall that, in the full-feedback model, we get one sample from each r.v. in every time-step. We now describe the algorithm. The algorithm is straightforward: for each \(t = 1, 2, \ldots T\), we use estimates from the prior \(t-1\) time steps to obtain a policy to use for the \(t^{\text{th}}\) time-step. As a consequence of Theorem 23, with probability at least \(1-\frac{1}{T^2}\), we have that \(\mathtt{OPT}(\mathbf{{\widehat{D}_t}})\) is an \(\epsilon_t\)-additive approximation to \(\mathtt{OPT}(\mathbf{{D}})\) where \(\epsilon_t \leq \sqrt{\frac{Cn\log(nT)}{t}}\). (To keep calculation simple, we ignore the \(\log\frac{1}{\epsilon}\) dependence in Theorem 23; so we are actually assuming a slightly stronger sample-complexity bound.) By union bound, this is true for all \(t = 1, \ldots, T\) with probability at least \(1 - \frac{1}{T}\). We consider this to be a good event, \(G\). Under this event, the total regret, say \(R_T\), can be bounded as follows. \[\mathbb{E}[R_T \mid G] \leq \sum_{t=1}^{T}\sqrt{\frac{{Cn\log\left(nT\right)}}{t}} = O\left(\sqrt{nT\log(nT)}\right).\] By law of total expectation we have \[\mathbb{E}[R_T] \leq \mathbb{E}[R_T \mid G] \cdot \Pr(G) + \mathbb{E}[R_T \mid \overline{G}] \cdot \Pr(\overline{G}) \leq O\left(\sqrt{nT\log(nT)}\right) + T \cdot \frac{1}{T} = O\left(\sqrt{nT\log (nT)}\right).\]

7.0.0.2 Semi-bandit feedback.

A significant challenge in the semi-bandit feedback model arises from our lack of control over the r.v.s from which we get samples. One potential strategy to address this issue is to artificially generate samples for an item \(i\) by probing item \(i\) first in the algorithm’s policy for that period. However, this approach comes with an inherent drawback – probing item \(i\) first may result in a poor policy, and so we suffer a high regret in such periods. The standard explore-then-exploit algorithm that first gets \(T^{2/3}\) samples for each r.v., and then plays the optimal policy (for the empirical distribution) for the remaining time steps only achieves regret \(\widetilde{O}(T^{2/3})\). We are not aware of any generic approach that reduces sample-complexity bounds to regret minimization in the semi-bandit have \(o(T^{2/3})\) regret.

7.0.0.3 Remark 1.

The sampling approach for semi-bandit feedback also applies to many problems (e.g., prophet inequality, Pandora’s box and series testing) in the bandit feedback model. Basically, for each item \(i\) we need a policy where its objective corresponds to the value of r.v. \(\mathsf{X}_i\). So, we can directly get \(\widetilde{O}(T^{2/3})\) regret for these problems even with bandit feedback.

7.0.0.4 Remark 2.

We note that [19] also give (slightly worse) sample complexity bounds for a broader class of problems that need not satisfy any monotonicity property, but have a finite support-size \(k\). Using the approaches described above, we can convert these sample-complexity guarantees to obtain \(O\left( \sqrt{nkT\log(nT)} \right)\) regret under full-feedback and \(O\left((nkT)^{2/3}(\log T)^{1/3}\right)\) regret under semi-bandit (and bandit) feedback.

8 Lower Bounds↩︎

We now state some regret lower bound results for monotone problems under the semi-bandit and binary feedback models. We highlight particular applications for which lower bounds are already known, and observe that since these problems can be captured by our framework, the corresponding lower bounds also apply to our setting.

Hence, our upper bounds match this lower bound up to a factor of \(\sqrt{n}\) and logarithmic terms. The next result, also observed in [88], shows that stochastic problems under binary feedback with continuous distributions are fundamentally harder to learn than with discrete distributions.

References↩︎

---

1. Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India.↩︎

2. Department of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA.↩︎

3. Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA. Research supported in part by NSF grant CCF-2418495.↩︎

4. For policy \(\sigma\) and distribution \(\mathbf{D}\), \(f(\sigma | \mathbf{{D}})\) is the expected objective of \(\sigma\) when the r.v.s have distribution \(\mathbf{D}\).↩︎

5. These papers also handle a more general setting where items have an arbitrary outcome space (not just binary).↩︎