# Multiple sequences Prophet Inequality Under Observation Constraints.

Aristomenis Tsopelakos, Olgica Milenkovic  Coordinated Science Laboratory,
University of Illinois at Urbana-Champaign.

###### Abstract

In our problem, we are given access to a number of sequences of nonnegative
i.i.d. random variables, whose realizations are observed sequentially. All
sequences are of the same finite length. The goal is to pick one element from
each sequence in order to maximize a reward equal to the expected value of the
sum of the selections from all sequences. The decision on which element to
pick is irrevocable, i.e., rejected observations cannot be revisited.
Furthermore, the procedure terminates upon having a single selection from each
sequence. Our observation constraint is that we cannot observe the current
realization of all sequences at each time instant. Instead, we can observe
only a smaller, yet arbitrary, subset of them. Thus, together with a stopping
rule that determines whether we choose or reject the sample, the solution
requires a sampling rule that determines which sequence to observe at each
instant. The problem can be solved via dynamic programming, but with an
exponential complexity in the length of the sequences. In order to make the
solution computationally tractable, we introduce a decoupling approach and
determine each stopping time using either a single-sequence dynamic
programming, or a Prophet Inequality inspired threshold method, with
polynomial complexity in the length of the sequences. We prove that the
decoupling approach guarantees at least $0.745$ of the optimal expected reward
of the joint problem. In addition, we describe how to efficiently compute the
optimal number of samples for each sequence, and its’ dependence on the
variances.

##  I Introduction

In many applications, multiple data sequences are monitored sequentially with
an aim to decide the best instant to terminate the observation procedure, and
use the collected information to maximize an objective. Financial applications
include the design of posted pricing mechanisms for auctions [1, 2, 3] and
contention resolution schemes [4]. Recent engineering applications focus on
the optimization of computer hardware performance, such as computational
sprinting [5, 6], which provides a significant performance boost to
microchips. These applications, among many others, have motivated a large body
of work in optimal stopping theory, with the dynamic programming [7, Ch. 24]
being the primary resolution method for a broad class of them.

In systems with multiple data sequences, it is not always possible to observe
the current sample of each sequence due to resource limitations or other
observation constraints [8, 9]. For example, when following a large number of
auctions in parallel, it is difficult to analyze all offers at all times. In
computational sprinting hardware mechanisms, a software predicts the
performance boost of a microchip when we allow short-term overheating, but
limited computational resources render it impossible to run the software for
all microchips, at each instant. In both cases, only a smaller number of
sequences can be processed at any given instant, but without restrictions on
which they are. This type of observation constraints leads to a problem at the
intersection of optimal stopping and multi-armed bandit theory [10].

In our problem, we assume that the data sequences comprise i.i.d. random
variables that are independent of each other, and whose distributions are
allowed to differ. Our constraint is that we can only observe a fixed-size
subset of the sequences, at each instant. Our goal is to determine which
sequences to observe at each instant, and when to stop sampling at each
sequence, in order to maximize our reward, which is the sum of the expected
values of the observations at the selected stopping times. This is a combined
optimal stopping and sampling problem, which could be treated by dynamic
programming with an exponential complexity on the length of the sequences. In
order to reduce the complexity, we introduce a decoupling approach, based on
the Prophet Inequality [3, 11, 12, 13, 14], that reduces the complexity to
polynomial, and guarantees at least $0.745$ of the optimal expected reward of
the joint problem.

The Prophet Inequality compares the expected value of the picked element at
the optimal stopping time, for each sequence, with the expected value of its’
maximum element, by providing a tight lower bound on the ratio of the
respective expected values. The lower bound is proven to be equal to $0.745$,
for an i.i.d. sequence, in [3, 15], independent of the distribution and of the
length of the sequence. This benchmark has motivated the design of stopping
rules for our problem, which always satisfy the Prophet Inequality, although
they might be sub-optimal in some cases. In [3, Corollary 4.7], an algorithm
is provided for the computation of the thresholds of such a stopping rule,
which is simpler compared to that of the single-sequence dynamic programming
(Single-DP), although both methods have linear complexity on the length of the
sequences. We refer to the algorithm in [3], as Prophet Inequality
thresholding method (PI-thresholding).

The basic requirement of the decoupling approach, is the calculation of the
optimal number of samples for each sequence, based on which we can apply
Single-DP, or PI-thresholding on each sequence separately. This results in a
constrained optimization problem that depends on the distributions of all
sequences. The computation might be intensive for large sequences, thus, under
some smoothness assumptions on the optimization objective, we develop an
approximation technique for the number of samples, whose error converges to
zero as the length of the sequences goes to infinity.

The paper is organized as follows. In Section II, we present the problem
formulation, while in Section III we prove our first result, pertaining to the
approximation ratio of the decoupling approach. Then, in Section IV, we
describe the approximation technique for the computation of the optimal number
of samples for each sequence. In our last Section V, we present computational
examples, which support the efficiency of the decoupling approach, for both
the Single-DP and the PI-thresholding method.

##  II Problem formulation

Let $(\mathbb{R}_{+},\mathcal{S})$ be an arbitrary measurable space and
$(\Omega,\mathcal{F},\mathsf{P})$ be a probability space which hosts $M$
independent sequences of $n$ i.i.d. $\mathbb{R}_{+}$-valued random variables,

$X_{i}:=\\{X_{i}(m)\,:\,m\in[n]\\},\quad\quad i\in[M],$

where $[n]:=\\{1,\ldots,n\\}$, $[M]:=\\{1,\ldots,M\\}$. We aim to find the
stopping time $\tau_{i}\in[n]$, for each sequence $i\in[M]$, that attains

$\sup_{\tau_{i}\in\mathcal{T}}\mathsf{E}[X_{i}(\tau_{i})],$ (1)

where $\mathcal{T}$ the class of all stopping times that take values in $[n]$.
Formally, a stopping time is a random variable $\tau_{i}$, $i\in[M]$, for
which the event $\\{\tau_{i}=m\\}$, $m\in[n]$, is fully determined by the
observations up to time $m$. Since each sequence $i\in[M]$ is associated to a
stopping time $\tau_{i}$, we make subsequent use of the vector of stopping
times of all sequences, i.e., $T:=(\tau_{1},\ldots,\tau_{M})$.

The observations from each sequence $i\in[M]$ are made sequentially and our
decision to stop at time $\tau_{i}$ and pick $X_{i}(\tau_{i})$ as our “best”
choice for the optimization problem (1) is irrevocable, i.e., we cannot
revisit samples we rejected, nor we can examine samples that follow after we
stop. The Prophet inequality [3, 15] provides a tight lower bound of $0.745$
on the ratio of (1) over $\mathsf{E}[\max_{m\in[n]}X_{i}(m)]$, for each
$i\in[M]$. By the term “tight”, we mean that for any $n$, there exists a
distribution that satisfies the inequality by equality, [15].

The main aspect that distinguishes our problem from the relevant bibliography,
is the introduction of observation constraints to our model, i.e., it is not
possible to observe the current element of each sequence at each instant
$m\in[n]$, but only from a subset of them of size $K<M$, independent of which
they actually are. Hence, we denote by $R(m)$ the subset of sequences that are
observed at time $m$, i.e.,

$R(m):=\left\\{i\in[M]\,:\,R_{i}(m)=1\right\\},$

where

$R_{i}(m):=\mathbf{1}\left\\{\mbox{observe}\;X_{i}(m)\right\\}.$

We say that $R$ is a sampling rule if, for every $m\in[n-1]$, the $R(m+1)$ is
$\mathcal{F}^{R}(m)$-measurable, where $\mathcal{F}^{R}(m)$ is the
$\sigma$-algebra generated by the observed elements up to time $m$ according
to rule $R$, i.e.,

$\displaystyle\mathcal{F}^{R}(m):=$
$\displaystyle\begin{cases}\emptyset,\;&\mbox{ if }\;m=0,\\\
\sigma\left(\mathcal{F}^{R}(m-1),\\{X_{i}(m)\,:\,i\in R(m)\\}\right),\;&\mbox{
if }\;m\in[n].\end{cases}$

The policy $(R,T)$ belongs to the class $\mathcal{C}(K)$ if the number of
sequences observed at each sampling instant is equal to $K$, i.e.,

$\sum_{i=1}^{M}R_{i}(m)=K,\quad\forall\;m\in[n].$ (2)

Our goal is to find a policy $(R,T)\in\mathcal{C}(K)$ that optimizes the
objective

$\sup_{(R,T)\in\mathcal{C}(K)}\sum_{i=1}^{M}\mathsf{E}\left[X_{i}(\tau_{i})\right],$
(3)

under the assumption that for each $i\in[M]$, the i.i.d. sequence $X_{i}$ has
a finite first moment.

##  III The Decoupling Approach

The optimization problem (3) can be solved via dynamic programming, with a
computational complexity of $O\left({M\choose K}^{n}\right)$. In order to
reduce the complexity, we describe a decoupling approach that produces a
$0.745$-constant approximation for (3), with complexity polynomial in $n$.

For any sampling rule $R$, we denote by

$N^{R}_{i}(n):=\sum_{m=1}^{n}R_{i}(m),\quad i\in[M],$

the total number of elements we have observed from sequence $i$ up to time
$n$, and by $\tau^{R}_{i}$ the optimal stopping time of sequence $i$,
associated with the sampling rule $R$. The decoupling approach consists of the
following steps:

  1. (i)

Since for each $i\in[M],$ the sequence $X_{i}$ is i.i.d., it suffices to
determine the number of observations $N_{i}(n)$ for sequence $i$, without
pinpointing the exact times at which we observe. The values
$\\{N_{i}(n)\,:\,i\in[M]\\}$ shall satisfy a particular optimization
criterion, independent of $R$.

  2. (ii)

We design a sampling rule $R^{d}$ which guarantees $N_{i}(n)$ observations for
each $i\in[M]$, and respects the sampling constraint (2), which implies

$\displaystyle N_{i}^{R^{d}}(n)$
$\displaystyle=N_{i}(n),\quad\forall\;i\in[M],$ (4)
$\displaystyle\sum_{i=1}^{M}N_{i}^{R^{d}}(n)$ $\displaystyle=Kn.$

  3. (iii)

Given the $N_{i}^{R^{d}}(n)$ observations for each $i\in[M]$, in order to
determine the decoupled optimal stopping times $\tau_{i}^{R^{d}}$, $i\in[M]$,
we can use either the single-sequence dynamic programming [7, Chapter 24], or
the Prophet Inequality thresholding method in [3, Corollary 4.7]. The latter,
although computationally simpler, it may provide a sub-optimal reward.

In order to formulate the optimization criterion that the
$\\{N_{i}(n):i\in[M]\\}$ must satisfy, we note that since the elements of each
sequence are i.i.d., all subsequences of $N_{i}(n)$ elements have the same
statistical behavior, and thus, by Prophet inequality [3, 15], for $R^{d}$,
and for each $i\in[M]$,

$\mathsf{E}\left[X_{i}(\tau^{R^{d}}_{i})\right]\geq
D\,\mathsf{E}\left[\max_{1\leq m\leq N^{R^{d}}_{i}(n)}X_{i}(m)\right],$ (5)

where $D:=0.745$. Thus, the $\\{N_{i}(n):i\in[M]\\}$ are chosen as the
maximizers of

$\max_{(n_{1},\ldots,n_{M})\in\mathfrak{C}(K)}\sum_{i=1}^{M}\mathsf{E}\left[\max_{1\leq
m\leq n_{i}}X_{i}(m)\right],$ (6)

where

$\mathfrak{C}(K):=\left\\{(n_{1},\ldots,n_{M})\in[n]^{M}\,:\,\sum_{i=1}^{M}=Kn\right\\},$
(7)

because by (5), the criterion (6) guarantees that

$\displaystyle\sup_{(R,T)\in\mathcal{C}(K)}\sum_{i=1}^{M}\mathsf{E}\left[X_{i}(\tau_{i})\right]$
(8) $\displaystyle\quad\geq
D\max_{(n_{1},\ldots,n_{M})\in\mathfrak{C}(K)}\sum_{i=1}^{M}\mathsf{E}\left[\max_{1\leq
m\leq n_{i}}X_{i}(m)\right].$

###### Theorem III.1

The decoupling approach achieves at least $0.745$ of the optimal expected
reward of the joint optimization problem (3), provided that the number of
samples from each sequence is optimized as of (6).

###### Proof:

In view of (8), it suffices to show that

$\displaystyle\sup_{(R,T)\in\mathcal{C}(K)}\sum_{i=1}^{M}\mathsf{E}\left[X_{i}(\tau_{i})\right]$
(9)
$\displaystyle\quad\leq\max_{(n_{1},\ldots,n_{M})\in\mathfrak{C}(K)}\sum_{i=1}^{M}\mathsf{E}\left[\max_{1\leq
m\leq n_{i}}X_{i}(m)\right].$

Let us denote by $R^{*}$ the optimal sampling rule for (3), as determined by
the dynamic programming algorithm, which we denote by $\mathcal{A}$ throughout
the proof. Thus,

$\sup_{(R,T)\in\mathcal{C}(K)}\sum_{i=1}^{M}\mathsf{E}\left[X_{i}(\tau_{i})\right]=\sum_{i=1}^{M}\mathsf{E}\left[X_{i}\left(\tau^{R^{*}}_{i}\right)\right].$
(10)

The event

$\displaystyle\\{\tau^{R^{*}}_{1}=t_{1},\ldots,\tau^{R^{*}}_{M}=t_{M}\\}$ (11)

is fully determined by the elements we observed up to the respective times
$t_{1},\ldots,t_{M}\in[n]$, i.e.,

$\bigcup_{i=1}^{M}\left\\{X_{i}(k)R^{*}_{i}(k)\,:\,1\leq k\leq
t_{i}\right\\}.$ (12)

The algorithm $\mathcal{A}$, generates also the conditions, which based on the
samples of each sequence up to times $\\{t_{i}:i\in[M]\\}$ respectively,
determine the event (11). Thus, if we denote by $\mathcal{A}_{t_{1},..,t_{M}}$
the conditions of $\mathcal{A}$ for the times $\\{t_{i}:i\in[M]\\}$, with a
slight abuse of notation we have

$\displaystyle\mathsf{P}\\{{\tau^{R^{*}}_{1}=t_{1},..,\tau^{R^{*}}_{M}=t_{M}\\}}$
$\displaystyle=\mathsf{P}\left(\mathcal{A}_{t_{1},..,t_{M}}\left(\bigcup_{i=1}^{M}\left\\{X_{i}(k)R^{*}_{i}(k):1\leq
k\leq t_{i}\right\\}\right)\right).$

Since all sequences are i.i.d. and independent of each other, the random
variables in (12) are interchangeable with the first $N^{R^{*}}_{i}(t_{i})$
random variables in each sequence $i\in[M]$. As a result,

$\displaystyle\mathsf{P}\left(\tau^{R^{*}}_{1}=t_{1},..,\tau^{R^{*}}_{M}=t_{M}\right)$
$\displaystyle=\mathsf{P}\left(\mathcal{A}_{t_{1},..,t_{M}}\left(\bigcup_{i=1}^{M}\left\\{X_{i}(k):1\leq
k\leq N^{R^{*}}_{i}(t_{i})\right\\}\right)\right).$

Thus, for a sampling rule $\widetilde{R}$ which examines the elements one by
one, without missing the elements that it can not observe, as they remain
stand by, one has

$\sum_{i=1}^{M}\mathsf{E}\left[X_{i}\left(\tau^{R^{*}}_{i}\right)\right]=\sum_{i=1}^{M}\mathsf{E}\left[X_{i}\left(\tau^{\widetilde{R}}_{i}\right)\right],$
(13)

and

$\tau^{\widetilde{R}}_{i}=N^{R^{*}}_{i}\left(\tau^{R^{*}}_{i}\right),\quad\mbox{a.s.,
}\;\forall\;i\in[M].$ (14)

Hence, for each $i\in[M]$,

$\displaystyle\mathsf{E}\left[X_{i}\left(\tau^{\widetilde{R}}_{i}\right)\right]$
$\displaystyle=\mathsf{E}\left[X_{i}\left(N^{R^{*}}_{i}\left(\tau^{R^{*}}_{i}\right)\right)\right]$
(15) $\displaystyle\leq\mathsf{E}\left[\max_{1\leq m\leq
N^{R^{*}}_{i}\left(\tau^{R^{*}}_{i}\right)}X_{i}(m)\right].$

Therefore, it suffices to show that

$\displaystyle\sum_{i=1}^{M}\mathsf{E}\left[\max_{1\leq m\leq
N^{R^{*}}_{i}(\tau^{R^{*}}_{i})}X_{i}(m)\right]$ (16)
$\displaystyle\quad\leq\max_{(n_{1},\ldots,n_{M})\in\mathfrak{C}(K)}\sum_{i=1}^{M}\mathsf{E}\left[\max_{1\leq
m\leq n_{i}}X_{i}(m)\right].$

Indeed, by sampling constraint (2), and since $\tau^{R^{*}}_{i}\leq n$, for
all $i\in[M]$, we have

$\sum_{i=1}^{M}N_{i}^{R^{*}}(\tau^{R^{*}}_{i})\leq\sum_{i=1}^{M}\sum_{m=1}^{n}R^{*}_{i}(m)\leq
Kn.$

Since each term in (6) is increasing in $n_{i}$, we conclude (16). ∎

##  IV Maximization Problem

We focus on the computation of the maximizers $n_{1}^{*},\ldots,n_{M}^{*}$ of
(6). For large $n$, finding the exact values is computationally demanding, and
thus we suggest an approximation technique along with error guarantees.

For each $i\in[M]$, we restrict our attention to absolutely continuous random
variables, whose probability density and cumulative distribution functions are
denoted by $f_{i}$ and $F_{i}$, respectively. The density of the maximum of
$n_{i}$ observations from sequence $i$ is denoted by $g_{i}$, i.e.,

$g_{i}(x):=n_{i}\left(F_{i}(x)\right)^{n_{i}-1}f_{i}(x),\quad x\geq 0.$

The maximization problem (6) turns into Problem $\mathbf{P_{1}}$:

$\max_{n_{1},\ldots,n_{M}}\sum_{i=1}^{M}n_{i}\int_{0}^{\infty}x\left(F_{i}(x)\right)^{n_{i}-1}f_{i}(x)dx,$
(17)

subject to

$\displaystyle\sum_{i=1}^{M}n_{i}=Kn,$ (18)

and $n\geq n_{i}\geq 0$, for all $i\in[M]$.

A solution approach to $\mathbf{P_{1}}$ is the exhaustive search, of
computational complexity $O\left(n^{M}\right)$. Thus, in the following
subsection, we introduce a computationally simpler approximation method, whose
computational complexity is $O\left(2^{M}\right)$, and hence independent of
$n$, with an approximation error converging to $0$ as $n\to\infty$.

###  IV-A The approximation problem

For each $i\in[M]$, we set $c_{i}:=n_{i}/n$ and rewrite problem
$\mathbf{P_{1}}$ as Problem $\mathbf{P_{2}}$:

$\max_{c_{1},\ldots,c_{M}}\sum_{i=1}^{M}c_{i}n\int_{0}^{\infty}x\left(F_{i}(x)\right)^{c_{i}n-1}f_{i}(x)dx,$
(19)

subject to

$\sum_{i=1}^{M}c_{i}=K,$ (20)

and $1\geq c_{i}\geq 0$, for all $i\in[M]$. We denote by
$G(c_{1},\ldots,c_{M})$ the objective function (19), where
$(c_{1},\ldots,c_{M})$ lies in the set

$\mathcal{D}:=\left\\{(c_{1},\ldots,c_{M})\in[0,1]^{M}\,:\,\sum_{i=1}^{M}c_{i}=K\right\\}.$

For simplicity, we assume that the function $G(c_{1},\ldots,c_{M})$ is
differentiable everywhere on $\mathcal{D}$. Thus, the function
$G(c_{1},\ldots,c_{M})$ is continuous everywhere on the compact set
$\mathcal{D}$, and by the Extreme value theorem [16, Theorem 4.16] it achieves
a maximum on $\mathcal{D}$. By the Lagrange multipliers method and provided
that the induced system of equations has a solution, we obtain the solution of
$\mathbf{P_{2}}$, denoted by $(\hat{c}_{1},\ldots,\hat{c}_{M})$. Then, within
$\mathbf{P_{1}}$, we replace $n\geq n_{i}\geq 0$ by

$\lfloor\hat{c}_{i}n\rfloor\leq
n_{i}\leq\lceil\hat{c}_{i}n\rceil,\quad\forall\;i\in[M],$

which reduces the number of possible solutions from $n+1$ to $2$, for all
$i\in[M]$. Hence, we obtain Problem $\mathbf{P_{3}}$:

$\max_{n_{1},\ldots,n_{M}}\sum_{i=1}^{M}n_{i}\int_{0}^{\infty}x\left(F_{i}(x)\right)^{n_{i}-1}f_{i}(x)dx,$
(21)

subject to

$\displaystyle\sum_{i=1}^{M}n_{i}$ $\displaystyle=Kn,$ (22)
$\displaystyle\lfloor\hat{c}_{i}n\rfloor\leq n_{i}$
$\displaystyle\leq\lceil\hat{c}_{i}n\rceil,\quad\forall\;i\in[M].$

Solving $\mathbf{P_{3}}$ using exhaustive search, we compute an approximation
of the optimal solution of $\mathbf{P_{1}}$.

###  IV-B The cost of approximation

We provide a bound on the approximation error for the sample sizes $n_{i}$,
which converges to $0$ as $n$ increases. We denote by $H(n_{1},\ldots,n_{M})$
the objective function of problems $\mathbf{P_{1}}$, $\mathbf{P_{3}}$, and by

  1. (i)

$(n^{*}_{1},\ldots,n^{*}_{M})$ the optimal solution of problem
$\mathbf{P_{1}}$, with $c^{*}_{i}:=n^{*}_{i}/n$, for all $i\in[M]$.

  2. (ii)

$(\check{n}_{1},\ldots,\check{n}_{M})$ the optimal solution of problem
$\mathbf{P_{3}}$, with $\check{c}_{i}:=\check{n}_{i}/n$, for all $i\in[M]$.

We define the cost of approximation as

$C:=\big{|}H(n^{*}_{1},\ldots,n^{*}_{M})-H(\check{n}_{1},\ldots,\check{n}_{M})\big{|}.$
(23)

Next, we prove that under smoothness conditions on $G$, the cost $C$ is
bounded by a constant multiplied by $e$,

$e:=\|(\hat{c}_{1},\ldots,\hat{c}_{M})-(\check{c}_{1},\ldots,\check{c}_{M})\|.$
(24)

###### Theorem IV.1

If $G$ is everywhere differentiable on $\mathcal{D}$, with bounded derivative,
then $C\leq Q\,e$, where

$Q:=\max\left\\{\|\nabla
G(c_{1},..,c_{M})\|:(c_{1},..,c_{M}){\in}\mathcal{D}\right\\}.$ (25)

###### Proof:

By definition of the objective functions $H$, $G$, we observe that for any
$n_{1},\ldots,n_{M}\in[n]$ it holds

$G\left(\frac{n_{1}}{n},\ldots,\frac{n_{M}}{n}\right)=H(n_{1},\ldots,n_{M}),$
(26)

which implies that

$\displaystyle G(c^{*}_{1},..,c^{*}_{M})=$ $\displaystyle
H(n^{*}_{1},..,n^{*}_{M})$ (27) $\displaystyle\geq
H(\check{n}_{1},..,\check{n}_{M})=G(\check{c}_{1},..,\check{c}_{M}),$

where the inequality follows by the optimality of
$(n^{*}_{1},\ldots,n^{*}_{M})$ for problem $\mathbf{P_{1}}$. Also, by the
optimality of $(\hat{c}_{1},\ldots,\hat{c}_{M})$ for problem $\mathbf{P_{2}}$,
we have

$G(\hat{c}_{1},\ldots,\hat{c}_{M})\geq G(c^{*}_{1},\ldots,c^{*}_{M}).$ (28)

By definition (23), and inequalities (27)-(28) we have

$C\leq\big{|}G(\hat{c}_{1},\ldots,\hat{c}_{M})-G(\check{c}_{1},\ldots,\check{c}_{M})\big{|}.$
(29)

Since $G$ is everywhere differentiable with bounded derivative on
$\mathcal{D}$, and $\mathcal{D}$ is convex, by Rademacher’s theorem [17,
Theorem 1.41] we deduce that

$\displaystyle\|G$
$\displaystyle(\hat{c}_{1},\ldots,\hat{c}_{M})-G(\check{c}_{1},\ldots,\check{c}_{M})\|$
(30) $\displaystyle\leq
Q\,\|(\hat{c}_{1},\ldots,\hat{c}_{M})-(\check{c}_{1},\ldots,\check{c}_{M})\|,$

where $Q$ is as defined in (25). This proves the claim. ∎

Remark: By the second constraint in (22), it holds

$\hat{c}_{i}-1/n\leq\check{c}_{i}\leq\hat{c}_{i}+1/n,$ (31)

which implies that $e\to 0$ as $n\to\infty$, and by Theorem IV.1, we conclude
that $C\to 0$ as $n\to\infty$.

###  IV-C Uniform densities example

We consider $M$ sequences of $n$ i.i.d. random variables each, which follow a
$U[a_{i},b_{i}]$ uniform distribution, where $0<a_{i}<b_{i}$, for each
$i\in[M]$. We can observe only $K$ sequences at each time instant. In this
case, problem $\mathbf{P_{2}}$ takes the form

$\max_{c_{1},\ldots,c_{M}}\left\\{\sum_{i=1}^{M}b_{i}-\frac{b_{i}-a_{i}}{c_{i}n+1}\right\\},$

subject to its underlying constraints. By the Lagrange multipliers method, for
each $i\in[M]$, we have

$\hat{c}_{i}=\frac{\sqrt{b_{i}-a_{i}}}{\left(\sum_{j=1}^{M}\sqrt{b_{j}-a_{j}}\right)/M}\left(\frac{K}{M}+\frac{1}{n}\right)-\frac{1}{n}.$
(32)

Remark: For all $i\in[M]$, the differences $b_{i}-a_{i}$ determine the values
of $\hat{c}_{i}$, which implies that the variances $(b_{i}-a_{i})^{2}/12,$
govern the sampling rates.

###  IV-D Gaussian densities example

In various frameworks, e.g. [5, Section 5.1], the sequences follow a Gaussian
density $\mathcal{N}(\mu_{i},\sigma^{2}_{i})$, for each $i\in[M]$, and we can
observe $K$ sequences at each instant. We assume that the means of the
Gaussians are large enough, and the variances relatively small, so that the
random variables are positive with probability practically equal to one.
According to Blom’s formula [18], and the approximation of the
$\operatorname{erf}$ function presented in [19], for $n_{i}$ large enough, and
for each $i\in[M]$,

$E\left[\max_{1\leq m\leq
n_{i}}X_{i}(m)\right]{\simeq}\mu_{i}+\sigma_{i}\sqrt{\frac{\pi}{2}}\frac{10}{8}\left(\frac{1}{n_{i}+0.25}-0.8\right).$

Thus, problem $\mathbf{P_{2}}$ reduces to

$\max_{c_{1},\ldots,c_{M}}\sum_{i=1}^{M}\frac{\sigma_{i}}{c_{i}\,n+0.25},$
(33)

subject to its defining constraints. By Lagrange multipliers method, we obtain

$\hat{c}_{i}=\frac{\sqrt{\sigma_{i}}}{\left(\sum_{i=1}^{n}\sqrt{\sigma_{i}}\right)/M}\left(\frac{K}{M}+\frac{0.25}{n}\right),\;\;i\in[M].$
(34)

We observe that except for the change in a constant multiplier of $1/n$, the
$\hat{c}_{i}$ in (34) exhibit the same dependence on the variances as those in
(32), especially for large $n$.

##  V Computational examples

We compare the expected reward of the joint dynamic programming problem (3)
versus that of the decoupled problem. For the decoupled problem, we precompute
the optimal number of observations for each sequence, and then on each
individual sequence, we run either (i) a single-sequence dynamic programming
(Single-DP), or (ii) a Prophet Inequality thresholding (PI-thresholding)
method [3, Corollary 4.7].

We consider $M=3$ sequences that follow three different uniform distributions
$U[0,3]$, $U[0.5,2.5]$, $U[1,2]$, which have the same mean but different
variances, and of lengths $n=5,\ldots,10$. We consider two cases $K=1$ and
$K=2$, and we plot the ratio of the expected reward of the decoupled problem,
for both Single-DP and PI-thresholding, over that of the joint problem.

For $K=1$ the decoupling approach offers a very good approximation for the
problem (3), with a ratio above $0.92$ for the Single-DP case, and above
$0.91$ for the PI-thresholding, for all $n$. We also note that the ratio of
the PI-thresholding method is no more than $1\%$ smaller than that of the
Single-DP method which is always optimal for a single sequence.

For $K=2$ the ratio is smaller compared to the former case, but it is still a
good approximation, with a ratio above $0.88$ for the Single-DP, and above
$0.87$ for the PI-thresholding method, for all $n$. In this case the gap
between Single-DP and PI-thresholding is larger, but no more than $10\%$.

(a) $M=3$, $K=1$

(b) $M=3$, $K=2$

Figure 1: Joint/Decoupled for Single-DP, PI-thresholding.

## Acknowledgments

The work was supported in part by NSF awards 2008125 and 1956384, through
Coordinated Science Laboratory, University of Illinois at Urbana-Champaign.

## References

  * [1] S. Alaei, “Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers,” _SIAM Journal on Computing_ , vol. 43, no. 2, pp. 930–972, 2014.
  * [2] M. Feldman, N. Gravin, and B. Lucier, “Combinatorial auctions via posted prices,” in _Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms_. SIAM, 2014, pp. 123–135.
  * [3] J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld, “Posted price mechanisms for a random stream of customers,” in _Proceedings of the 2017 ACM Conference on Economics and Computation_ , 2017, pp. 169–186.
  * [4] E. Lee and S. Singla, “Optimal online contention resolution schemes via ex-ante prophet inequalities,” in _26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland_ , vol. 112, 2018, pp. 57:1–57:14.
  * [5] Z. Huang, J. A. Joao, A. Rico, A. D. Hilton, and B. C. Lee, “Dynasprint: Microarchitectural sprints with dynamic utility and thermal management,” in _Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture_ , 2019, pp. 426–439.
  * [6] M. Epitropou and R. Vohra, “Optimal on-line allocation rules with verification,” in _Algorithmic Game Theory: 12th International Symposium, SAGT 2019, Athens, Greece, September 30–October 3, 2019, Proceedings 12_. Springer, 2019, pp. 3–17.
  * [7] R. N. Bhattacharya and E. C. Waymire, _Random walk, Brownian motion, and martingales_. Springer, 2021.
  * [8] S. Nitinawarat, G. K. Atia, and V. V. Veeravalli, “Controlled sensing for multihypothesis testing,” _IEEE Transactions on automatic control_ , vol. 58, no. 10, pp. 2451–2464, 2013.
  * [9] Q. Xu, Y. Mei, and G. V. Moustakides, “Optimum multi-stream sequential change-point detection with sampling control,” _IEEE Transactions on Information Theory_ , vol. 67, no. 11, pp. 7627–7636, 2021.
  * [10] Q. Zhao, _Multi-armed bandits: Theory and applications to online learning in networks_. Springer Nature, 2022.
  * [11] U. Krengel and L. Sucheston, “On semiamarts, amarts, and processes with finite value,” _Probability on Banach spaces_ , vol. 4, pp. 197–266, 1978.
  * [12] D. Assaf and E. Samuel-Cahn, “Simple ratio prophet inequalities for a mortal with multiple choices,” _Journal of applied probability_ , vol. 37, no. 4, pp. 1084–1091, 2000.
  * [13] J. Correa, R. Saona, and B. Ziliotto, “Prophet secretary through blind strategies,” _Mathematical Programming_ , vol. 190, no. 1-2, pp. 483–521, 2021.
  * [14] A. Bubna and A. Chiplunkar, “Prophet inequality: Order selection beats random order,” in _Proceedings of the 24th ACM Conference on Economics and Computation_ , 2023, pp. 302–336.
  * [15] R. P. Kertz, “Stop rule and supremum expectations of iid random variables: a complete comparison by conjugate duality,” _Journal of multivariate analysis_ , vol. 19, no. 1, pp. 88–112, 1986.
  * [16] W. Rudin, _Principles of mathematical analysis_ , 1953.
  * [17] N. Weaver, _Lipschitz algebras_. World Scientific, 2018.
  * [18] J. Royston, “Algorithm as 177: Expected normal order statistics (exact and approximate),” _Journal of the royal statistical society. Series C (Applied statistics)_ , vol. 31, no. 2, pp. 161–165, 1982.
  * [19] D. Dominici, “Some properties of the inverse error function,” _Contemporary Mathematics_ , vol. 457, pp. 191–204, 2008.