<p>This answer doesn't answer whether or not this is a special case of some kind of game that is studied in TCS.  But hopefully the answer helps understand the nature of the game.</p>
<p>The value of the game is <span class="math-container">$\Theta(n^{3/4})$</span>:</p>
<p><strong>Lemma 1.</strong> <em>Alice has a strategy that guarantees <span class="math-container">$\sum_{t=1}^T x_t \ge n^{3/4}$</span>.</em></p>
<p><strong>Lemma 2.</strong> <em>Bob has a strategy that guarantees <span class="math-container">$\sum_{t=1}^T x_t = O(n^{3/4})$</span> in expectation.</em></p>
<p>(I'm pretty sure the upper bound can be shown to hold w.h.p.,
and can be tightened to <span class="math-container">$(1+o(1))n^{3/4}$</span>.)</p>
<p><em>Proof of Lemma 1.</em>
Suppose Alice plays <span class="math-container">$x_t = n^{-1/4}$</span> at every time step,
and Bob plays any legal strategy.</p>
<p>For the game to terminate at some time <span class="math-container">$t&lt;n$</span>, it must be that
<span class="math-container">$\sum_{s=1}^t y_s x_s &gt; \sqrt{\sum_{s=1}^t y_s}.$</span>
Substituting <span class="math-container">$x_t = n^{-1/4}$</span> and simplifying,
this is equivalent to <span class="math-container">$\sum_{s=1}^t y_s &gt; n^{1/2}.$</span>
But this cannot happen without Bob violating his &quot;budget&quot; <span class="math-container">$\sum_{s=1}^n y_s \le \sqrt n$</span>.</p>
<p>So the game does not terminate early.
So the &quot;payoff&quot; <span class="math-container">$\sum_{t=1}^T x_t$</span> equals <span class="math-container">$n \cdot n^{-1/4} = n^{3/4}$</span>.
<span class="math-container">$~~~\Box$</span></p>
<p><em>Proof sketch for Lemma 2.</em>
We let r.v. <span class="math-container">$S$</span> be the first round <span class="math-container">$t$</span>
after which Bob is constrained by his budget constraint,
that is, when <span class="math-container">$\sum_{s=1}^{t} y_s \ge \sqrt n$</span>,
so that Bob is forced to set <span class="math-container">$y_s = 0$</span> for <span class="math-container">$s &gt; S$</span>.
(If it never happens, we let <span class="math-container">$S=T$</span>.)</p>
<p>Now suppose that Alice plays any legal (possibly randomized) strategy,
while Bob plays as follows:
for each round <span class="math-container">$t \le S$</span> independently,
Bob plays <span class="math-container">$y_t = 1$</span> with fixed probability <span class="math-container">$p = 0.5 n^{-1/2}$</span>,
and otherwise plays <span class="math-container">$y_t = 0$</span>.
(For each round <span class="math-container">$t &gt; S$</span>, Bob plays <span class="math-container">$y_t=0$</span>, per the definition of <span class="math-container">$S$</span>.)</p>
<p>The total payoff to Alice is then
<span class="math-container">$$\textstyle
\sum_{t=1}^T x_t \le T-S + \sum_{t=1}^{S} x_t.~~~~~~(1)$$</span>
We bound the expectations of <span class="math-container">$T-S$</span> and <span class="math-container">$\sum_{t=1}^S x_t$</span> separately.</p>
<p>At the start of any round <span class="math-container">$t\le S$</span>,
conditioned on all events so far,
<span class="math-container">$E[x_t - p^{-1} x_t y_t] = 0$</span>.
Also, <span class="math-container">$S$</span> is a stopping time.
So by Wald's equation
<span class="math-container">$$\textstyle E\big[\sum_{t=1}^{S} (x_t - p^{-1} x_t y_t) \big] = 0.$$</span>
This implies that</p>
<p><span class="math-container">$$
\begin{align}\textstyle
E\big[\sum_{t=1}^{S} x_t \big] 
&amp; \textstyle{} = p^{-1} E\big[\sum_{t=1}^{S} x_t y_t\big] \\
&amp; \textstyle{} \le p^{-1} E\big[1+\sqrt{\sum_{t=1}^S y_t}\big] \\
&amp; \textstyle{} \le p^{-1} (1+\sqrt{n p})
= O(n^{3/4}). ~~(2)
\end{align}
$$</span></p>
<p>(The first inequality above uses <span class="math-container">$\sum_{t=1}^{S-1} y_t x_t \le \sqrt{\sum_{t=1}^{S-1} y_t}$</span> and <span class="math-container">$y_S x_S \le 1$</span>.
The second inequality uses the concavity of the square root,
linearity of expectation, <span class="math-container">$E[y_t] = p$</span>, and <span class="math-container">$S\le n$</span>.)</p>
<p>To finish we bound <span class="math-container">$E[T-S]$</span>.
First we observe that the event <span class="math-container">$S&lt;T$</span> is unlikely.
Recalling that the <span class="math-container">$y_t$</span>'s are independent
0/1-r.v.s with expectation <span class="math-container">$p$</span>
and <span class="math-container">$T\le n$</span>, by a standard Chernoff bound,
<span class="math-container">$$\textstyle\Pr\big[\sum_{t=1}^T y_t \ge 2 np\big] \le \exp(-np / 3).$$</span>
Substituting <span class="math-container">$p = 0.5 n^{-1/2}$</span> gives
<span class="math-container">$$\textstyle\Pr\big[\sum_{t=1}^T y_t \ge \sqrt n\big] \le \exp(-\sqrt n / 6).$$</span>
Finally, <span class="math-container">$T - S \le n$</span>, and <span class="math-container">$T&gt;S$</span> only if <span class="math-container">$\sum_{t=1}^T y_t \ge \sqrt n$</span>,
so
<span class="math-container">$$\textstyle
E[T- S] \le n \Pr[T &gt; S] \le n \Pr[\sum_{t=1}^T y_t \ge \sqrt n]
\le n \exp(- \sqrt n / 6) = O(n^{3/4}).~~~~(3)
$$</span></p>
<p>Inequalities (1), (2), and (3) imply
that <span class="math-container">$E\big[\sum_{t=1}^T x_t\big] = O(n^{3/4})$</span>. <span class="math-container">$~~~~~\Box$</span></p>

CC BY-SA 4.0
2024-03-01T21:13:33.023Z
2024-03-01T21:18:36.863Z
2024-03-01T21:18:36.863Z
Neal Young
<p>Alice and Bob play a game over <span class="math-container">$n$</span> rounds. At each round, Alice picks a number <span class="math-container">$x_t \in [0,1]$</span> and Bob simultaneously chooses whether to &quot;peek&quot; at the number <span class="math-container">$x_t$</span> which is represented by a variable <span class="math-container">$y_t \in \{0,1\}$</span>. The game is over at round <span class="math-container">$t$</span> if the &quot;revealed&quot; sub-total to Bob <span class="math-container">$\sum_{s=1}^t y_s \cdot x_s$</span> exceeds some threshold <span class="math-container">$\sqrt{y_1+\cdots+y_t}$</span>. But, Bob also has a total budget <span class="math-container">$\sum_{t=1}^n y_t \leq \sqrt{n}$</span> on the allowed number of peeks which is known to alice at the beginning.</p>
<p>Therefore, Alice's goal is to maximize <span class="math-container">$\sum_{t=1}^T x_t$</span> where <span class="math-container">$T \leq n$</span> is the realized number of rounds played before the game ends, while Bob's goal is to minimize <span class="math-container">$\sum_{t=1}^T x_t$</span> by scheduling peeks accordingly. Both players make decisions adaptively (although Bob only has bandit information of <span class="math-container">$x_t$</span> values on peeked rounds where <span class="math-container">$y_t=1$</span>) and are allowed to use randomization.</p>
<p>I am not a TCS person, but am wondering if this kind of problem is already studied or reducible to some other well known problem. And, if so, what guarantees are known for Alice and/or Bob. For context, one can think of Bob here as an adversarial multi-armed bandit algorithm which is trying to do some kind of change-point detection in the environment (set by adversary Alice).</p>

CC BY-SA 4.0
2024-02-29T19:19:44.447Z
(i) So $n$ is known in advance to both players?  What about $F$?  (ii) What do you know about simple special cases, e.g. where $F$ and $B$ are known constants and $n=\infty$?  (iii) What happens if the threshold is not exceeded in the first $n$ rounds?
Neal Young
CC BY-SA 4.0
2024-02-29T21:48:05.380Z
$n,F,B$ are known in advance to both players. If $F,B$ are constants (say, Bob only has one round to peek), then there is probably not much Bob can do as Alice can use randomization to achieve a linear $\Omega(T)$ cost with constant probability. I am more interested in the cases where Bob can force Alice to get sublinear value even while constrained to a budget of $B(n)=\sqrt{n}$. For my use case, we have $F(y_1,\ldots,y_t) = \sqrt{y_1+\cdots+y_t}$.
Amaryllis 
CC BY-SA 4.0
2024-02-29T21:54:41.940Z
I've edited the question to be more specific and avoid ambiguity about some uninteresting cases.
Amaryllis 
CC BY-SA 4.0
2024-03-01T16:29:05.870Z
What do Alice and Bob know about each other's strategies?  E.g. do you assume that at the start of round $t$, Alice knows the probability distribution induced on $y_t$ by Bob's strategy?  And/or vice versa (Bob knows the probability distribution induced on $x_t$ by Alice's strategy)?  (In both cases, conditioned on all events that have occurred before round $t$.)
Neal Young
<machine-learning><gt.game-theory><two-player-games>
Sequential Two-player Game related to "Bandit Detection"
Amaryllis 
# Sequential Two-player Game related to "Bandit Detection"

(Asked by: username_0 on 2024-02-29)

Alice and Bob play a game over $n$ rounds. At each round, Alice picks a number $x\_t \in [0,1]$ and Bob simultaneously chooses whether to "peek" at the number $x\_t$ which is represented by a variable $y\_t \in \{0,1\}$. The game is over at round $t$ if the "revealed" sub-total to Bob $\sum\_{s=1}^t y\_s \cdot x\_s$ exceeds some threshold $\sqrt{y\_1+\cdots+y\_t}$. But, Bob also has a total budget $\sum\_{t=1}^n y\_t \leq \sqrt{n}$ on the allowed number of peeks which is known to alice at the beginning.

Therefore, Alice's goal is to maximize $\sum\_{t=1}^T x\_t$ where $T \leq n$ is the realized number of rounds played before the game ends, while Bob's goal is to minimize $\sum\_{t=1}^T x\_t$ by scheduling peeks accordingly. Both players make decisions adaptively (although Bob only has bandit information of $x\_t$ values on peeked rounds where $y\_t=1$) and are allowed to use randomization.

I am not a TCS person, but am wondering if this kind of problem is already studied or reducible to some other well known problem. And, if so, what guarantees are known for Alice and/or Bob. For context, one can think of Bob here as an adversarial multi-armed bandit algorithm which is trying to do some kind of change-point detection in the environment (set by adversary Alice).

**Tags:** machine-learning, gt.game-theory, two-player-games
> **Comments:**
> **username_1**: (i) So $n$ is known in advance to both players?  What about $F$?  (ii) What do you know about simple special cases, e.g. where $F$ and $B$ are known constants and $n=\infty$?  (iii) What happens if the threshold is not exceeded in the first $n$ rounds?  
> **username_0**: $n,F,B$ are known in advance to both players. If $F,B$ are constants (say, Bob only has one round to peek), then there is probably not much Bob can do as Alice can use randomization to achieve a linear $\Omega(T)$ cost with constant probability. I am more interested in the cases where Bob can force Alice to get sublinear value even while constrained to a budget of $B(n)=\sqrt{n}$. For my use case, we have $F(y_1,\ldots,y_t) = \sqrt{y_1+\cdots+y_t}$.  
> **username_0**: I've edited the question to be more specific and avoid ambiguity about some uninteresting cases.  
> **username_1**: What do Alice and Bob know about each other's strategies?  E.g. do you assume that at the start of round $t$, Alice knows the probability distribution induced on $y_t$ by Bob's strategy?  And/or vice versa (Bob knows the probability distribution induced on $x_t$ by Alice's strategy)?  (In both cases, conditioned on all events that have occurred before round $t$.)  

---

## 1 answers

### Answer by username_1 on 2024-03-01. Score: 1 | Accepted answer

This answer doesn't answer whether or not this is a special case of some kind of game that is studied in TCS. But hopefully the answer helps understand the nature of the game.

The value of the game is $\Theta(n^{3/4})$:

**Lemma 1.** *Alice has a strategy that guarantees $\sum\_{t=1}^T x\_t \ge n^{3/4}$.*

**Lemma 2.** *Bob has a strategy that guarantees $\sum\_{t=1}^T x\_t = O(n^{3/4})$ in expectation.*

(I'm pretty sure the upper bound can be shown to hold w.h.p.,
and can be tightened to $(1+o(1))n^{3/4}$.)

*Proof of Lemma 1.*
Suppose Alice plays $x\_t = n^{-1/4}$ at every time step,
and Bob plays any legal strategy.

For the game to terminate at some time $t, it must be that
$\sum\_{s=1}^t y\_s x\_s > \sqrt{\sum\_{s=1}^t y\_s}.$
Substituting $x\_t = n^{-1/4}$ and simplifying,
this is equivalent to $\sum\_{s=1}^t y\_s > n^{1/2}.$
But this cannot happen without Bob violating his "budget" $\sum\_{s=1}^n y\_s \le \sqrt n$.

So the game does not terminate early.
So the "payoff" $\sum\_{t=1}^T x\_t$ equals $n \cdot n^{-1/4} = n^{3/4}$.
$~~~\Box$

*Proof sketch for Lemma 2.*
We let r.v. $S$ be the first round $t$
after which Bob is constrained by his budget constraint,
that is, when $\sum\_{s=1}^{t} y\_s \ge \sqrt n$,
so that Bob is forced to set $y\_s = 0$ for $s > S$.
(If it never happens, we let $S=T$.)

Now suppose that Alice plays any legal (possibly randomized) strategy,
while Bob plays as follows:
for each round $t \le S$ independently,
Bob plays $y\_t = 1$ with fixed probability $p = 0.5 n^{-1/2}$,
and otherwise plays $y\_t = 0$.
(For each round $t > S$, Bob plays $y\_t=0$, per the definition of $S$.)

The total payoff to Alice is then
$$\textstyle
\sum\_{t=1}^T x\_t \le T-S + \sum\_{t=1}^{S} x\_t.~~~~~~(1)$$
We bound the expectations of $T-S$ and $\sum\_{t=1}^S x\_t$ separately.

At the start of any round $t\le S$,
conditioned on all events so far,
$E[x\_t - p^{-1} x\_t y\_t] = 0$.
Also, $S$ is a stopping time.
So by Wald's equation
$$\textstyle E\big[\sum\_{t=1}^{S} (x\_t - p^{-1} x\_t y\_t) \big] = 0.$$
This implies that

$$
\begin{align}\textstyle
E\big[\sum\_{t=1}^{S} x\_t \big]
& \textstyle{} = p^{-1} E\big[\sum\_{t=1}^{S} x\_t y\_t\big] \\
& \textstyle{} \le p^{-1} E\big[1+\sqrt{\sum\_{t=1}^S y\_t}\big] \\
& \textstyle{} \le p^{-1} (1+\sqrt{n p})
= O(n^{3/4}). ~~(2)
\end{align}
$$

(The first inequality above uses $\sum\_{t=1}^{S-1} y\_t x\_t \le \sqrt{\sum\_{t=1}^{S-1} y\_t}$ and $y\_S x\_S \le 1$.
The second inequality uses the concavity of the square root,
linearity of expectation, $E[y\_t] = p$, and $S\le n$.)

To finish we bound $E[T-S]$.
First we observe that the event $S is unlikely.
Recalling that the $y\_t$'s are independent
0/1-r.v.s with expectation $p$
and $T\le n$, by a standard Chernoff bound,
$$\textstyle\Pr\big[\sum\_{t=1}^T y\_t \ge 2 np\big] \le \exp(-np / 3).$$
Substituting $p = 0.5 n^{-1/2}$ gives
$$\textstyle\Pr\big[\sum\_{t=1}^T y\_t \ge \sqrt n\big] \le \exp(-\sqrt n / 6).$$
Finally, $T - S \le n$, and $T>S$ only if $\sum\_{t=1}^T y\_t \ge \sqrt n$,
so
$$\textstyle
E[T- S] \le n \Pr[T > S] \le n \Pr[\sum\_{t=1}^T y\_t \ge \sqrt n]
\le n \exp(- \sqrt n / 6) = O(n^{3/4}).~~~~(3)
$$

Inequalities (1), (2), and (3) imply
that $E\big[\sum\_{t=1}^T x\_t\big] = O(n^{3/4})$. $~~~~~\Box$


---

