<p>I imagine there are lots of possible approaches to this problem (many of which I'm sure you considered) -- here are a few ideas/references.</p>
<ul>
<li>You could play this as <span class="math-container">$N$</span> independent parallel single-arm bandit games, deciding to pull or not pull each arm independently.  This should work especially well if the rewards are independently distributed.</li>
<li>Allow each set of arms to be a new arm and run an Exp3-type algorithm.  This gives a <span class="math-container">$O(2^{N/2} T^{1/2})$</span> regret - not so great.</li>
<li>In an upcoming NIPS 2010 paper, Satyen Kale, Rob Schapire, and I <a href="https://papers.nips.cc/paper_files/paper/2010/hash/390e982518a50e280d8e2b535462ec1f-Abstract.html" rel="nofollow noreferrer">consider</a> the case where one plays a slate of arms at once.  In our work, however, the size of the slate is fixed.  This paper also considers a similar problem.  Another <a href="https://doi.org/10.1007/978-3-642-16108-7_30" rel="nofollow noreferrer">similar work</a> appeared in ALT 2010.  Perhaps some of the ideas transfer.</li>
<li>If you treat it as an experts problem (each expert recommends a different one of <span class="math-container">$2^N$</span> subsets), by following one expert, you can get estimate the performance of other experts who have non-empty intersections in their choice of arms to pull by using <a href="https://en.wikipedia.org/wiki/Importance_sampling" rel="nofollow noreferrer">importance weighting</a>.  An Exp4 type analysis might get you <span class="math-container">$O(N\sqrt{T})$</span> regret but <span class="math-container">$O(2^N T)$</span> running time.</li>
</ul>
<p>EDIT below:</p>
<p>It seems to me that the budget constraint (not going below <span class="math-container">$0$</span>) makes the problem intractable.  Imagine you have a budget of <span class="math-container">$1$</span>.  The adversary can make one of the  arms always pay off and the rest never pay off.  So w.p. <span class="math-container">$(n-1)/n$</span> you go bust in the first round while the optimal strategy gets <span class="math-container">$T$</span> dollars after <span class="math-container">$T$</span> rounds.  So your expected regret is at least <span class="math-container">$(n-1)T/n$</span> and you can't hope for a high probability bound at all.</p>
<p>It also seems that this can work for any initial budget.  Say you start with <span class="math-container">$B$</span> dollars.  Then the adversary can set all but one arms to pay <span class="math-container">$0$</span> and one arm to pay something like <span class="math-container">$2B$</span> w.p. <span class="math-container">$1/B$</span>.  I guess if you have a limit on the possible payout amount and a high enough initial budget, then this might leave room for an interesting problem.</p>

CC BY-SA 2.5
2010-10-23T01:01:59.383Z
Hi Lev, thanks for the pointers. I agree that if I had an unlimited initial budget playing N parallel single arm bandits would solve the problem. The budget constraint however introduces coupling among arms and makes things interesting. In particular, in the first step you only have budget to play one arm. In the second step you can play either 11 arms or just 1 arm, depending on whether you got lucky in the first step and so on. So it is important to find a bunch of profitable arms early on that you then use tofund further exploration.
Martin Pál
CC BY-SA 2.5
2010-10-23T02:15:59.683Z
I didn't realize there was an initial budget (I now understand the "non-negative balance" part, but perhaps you can make it clearer in the question?) -- that makes the problem more interesting.  Also the "contextual" or experts version might be fun to consider.  Unfortunately, I do not know any more relevant references for this problem.
Lev Reyzin
CC BY-SA 2.5
2010-10-23T15:05:11.600Z
If I got the problem formulation right, you gain an extra $1 each round. Martin, could you perhaps clarify the question?
Jukka Suomela
CC BY-SA 2.5
2010-10-23T15:14:57.683Z
I think you gain whatever a machine pays if you play it and win and lose $1 whenever you decide to play.
Lev Reyzin
CC BY-SA 4.0
2010-10-22T20:44:48.450Z
2023-04-26T11:21:42.327Z
2023-04-26T11:21:42.327Z
Lev Reyzin
<p>Here is an abstraction of an online learning / bandit problem that I've been working on in the summer. I haven't seen a problem like this before, and it looks quite interesting. If you know of any related work, I would appreciate references. </p>

<p><strong>The Problem</strong>
The setting is that of multi-armed bandits. You have N arms. Each arm i has an unknown but fixed probability distribution over rewards that can be earned by playing it. For concreteness, let's assume that each arm <em>i</em> pays reward $10 with probability <em>p[i]</em> and reward $0 with prob. <em>1-p[i]</em>. </p>

<p>In every round <em>t</em> you select a set <em>S[t]</em> of arms to play. For each arm you select, you pay a fee of <em>$1</em> up front. For each selected arm, you collect a reward that is drawn from the (unknown) reward probability distribution of that arm. All rewards are credited to your bank account, and all fees are deducted from that account. In addition, you get a credit of <em>$1</em> at the beginning of every iteration. </p>

<p>The problem is to develop a policy to select a subset of arms to play in each iteration to maximize profit (i.e. rewards minus fees for playing) over a long enough horizon, subject to the constraint that it must maintain a non-negative account balance at all times.</p>

<p>I did not specify whether the per-arm reward distributions are chosen from a prior distribution or chosen by an adversary. Both choices make sense. The adversary formulation is more appealing to me, but probably harder to make progress on. Here, the adversary chooses a vector (D1, D2, .., DN) of distributions. Given the distributions, the optimal budget balanced policy is to play all arms whose expected reward is greater than $1. Let P be the per-step profit of this optimal omniscient policy. I want my online policy to minimize regret (i.e. loss of profit over a time window T) wrt this omniscient policy.</p>

CC BY-SA 4.0
2023-04-26T17:36:20.067Z
Surely the regret of any online strategy will depend on the maximum payment in any distribution?  (E.g., for some $M\gg N$, you could have one distribution that, at each draw, has probability $1/M$ of paying $M^2$ and otherwise pays zero.  And all other distributions just pay zero all the time.  The expected number of steps until the first positive payoff is $NM$ for the online algorithm and $M$ for the optimal, and after that they are the same.  So expected regret will be $(N-1)M$.
Neal Young
CC BY-SA 2.5
2010-10-22T20:24:35.810Z
Are you sure that the best policy is to play all arms whose expected reward is greater than $1 in every round? If you have the strict constraint that you have to maintain a non-negative account balance at all times, there may be rounds in which you aren't even allowed to play.
Matthias
CC BY-SA 2.5
2010-10-22T21:00:57.657Z
So you don't know the reward probabilities, but you can tell the payoff from each individual arm?
David Thornley
CC BY-SA 2.5
2010-10-23T00:54:22.690Z
You don't know probabilities and you don't know expected rewards. An omniscient "optimal" policy that I want to compare myself against can however play all arms with reward greater than 1 because it's omniscient.
Martin Pál
CC BY-SA 2.5
2010-10-23T01:32:39.247Z
I'll make a wild guess that after $\Theta(N)$ rounds you can get your expected income to within a constant factor of the optimal, after which the problem seems to have lost most of its unusual character. A lower-bound of $\Omega(N)$ follows from an instance where only one arm has a non-zero payoff. I don't see an upper-bound immediately.
Warren Schudy
CC BY-SA 2.5
2010-10-23T01:37:45.477Z
Correction: after $\Theta(N)$ rounds you probably can't guarantee to get within a constant factor of optimal income. You can however probably get that guarantee relative to the income available from arms that have expected return at least say 2 dollars.
Warren Schudy
CC BY-SA 2.5
2010-10-23T16:18:33.877Z
meta discussion on whether to retag this post is here: http://meta.cstheory.stackexchange.com/questions/549/the-warren-buffet-question
Suresh Venkat
<machine-learning><lg.learning><online-learning>
The Warren Buffett Problem
Martin Pál
# The Warren Buffett Problem

(Asked by: username_0 on 2010-10-22)

Here is an abstraction of an online learning / bandit problem that I've been working on in the summer. I haven't seen a problem like this before, and it looks quite interesting. If you know of any related work, I would appreciate references.

**The Problem**
The setting is that of multi-armed bandits. You have N arms. Each arm i has an unknown but fixed probability distribution over rewards that can be earned by playing it. For concreteness, let's assume that each arm *i* pays reward $10 with probability *p[i]* and reward $0 with prob. *1-p[i]*.

In every round *t* you select a set *S[t]* of arms to play. For each arm you select, you pay a fee of *$1* up front. For each selected arm, you collect a reward that is drawn from the (unknown) reward probability distribution of that arm. All rewards are credited to your bank account, and all fees are deducted from that account. In addition, you get a credit of *$1* at the beginning of every iteration.

The problem is to develop a policy to select a subset of arms to play in each iteration to maximize profit (i.e. rewards minus fees for playing) over a long enough horizon, subject to the constraint that it must maintain a non-negative account balance at all times.

I did not specify whether the per-arm reward distributions are chosen from a prior distribution or chosen by an adversary. Both choices make sense. The adversary formulation is more appealing to me, but probably harder to make progress on. Here, the adversary chooses a vector (D1, D2, .., DN) of distributions. Given the distributions, the optimal budget balanced policy is to play all arms whose expected reward is greater than $1. Let P be the per-step profit of this optimal omniscient policy. I want my online policy to minimize regret (i.e. loss of profit over a time window T) wrt this omniscient policy.

**Tags:** machine-learning, lg.learning, online-learning
> **Comments:**
> **username_2**: Are you sure that the best policy is to play all arms whose expected reward is greater than $1 in every round? If you have the strict constraint that you have to maintain a non-negative account balance at all times, there may be rounds in which you aren't even allowed to play.  
> **username_3**: So you don't know the reward probabilities, but you can tell the payoff from each individual arm?  
> **username_0**: You don't know probabilities and you don't know expected rewards. An omniscient "optimal" policy that I want to compare myself against can however play all arms with reward greater than 1 because it's omniscient.  
> **username_4**: I'll make a wild guess that after $\Theta(N)$ rounds you can get your expected income to within a constant factor of the optimal, after which the problem seems to have lost most of its unusual character. A lower-bound of $\Omega(N)$ follows from an instance where only one arm has a non-zero payoff. I don't see an upper-bound immediately.  
> **username_4**: Correction: after $\Theta(N)$ rounds you probably can't guarantee to get within a constant factor of optimal income. You can however probably get that guarantee relative to the income available from arms that have expected return at least say 2 dollars.  
> **username_5**: meta discussion on whether to retag this post is here: http://meta.cstheory.stackexchange.com/questions/549/the-warren-buffet-question  
> **username_1**: Surely the regret of any online strategy will depend on the maximum payment in any distribution?  (E.g., for some $M\gg N$, you could have one distribution that, at each draw, has probability $1/M$ of paying $M^2$ and otherwise pays zero.  And all other distributions just pay zero all the time.  The expected number of steps until the first positive payoff is $NM$ for the online algorithm and $M$ for the optimal, and after that they are the same.  So expected regret will be $(N-1)M$.  

---

## 1 answers

### Answer by username_6 on 2010-10-22. Score: 13

I imagine there are lots of possible approaches to this problem (many of which I'm sure you considered) -- here are a few ideas/references.

* You could play this as $N$ independent parallel single-arm bandit games, deciding to pull or not pull each arm independently. This should work especially well if the rewards are independently distributed.
* Allow each set of arms to be a new arm and run an Exp3-type algorithm. This gives a $O(2^{N/2} T^{1/2})$ regret - not so great.
* In an upcoming NIPS 2010 paper, Satyen Kale, Rob Schapire, and I [consider](https://papers.nips.cc/paper_files/paper/2010/hash/390e982518a50e280d8e2b535462ec1f-Abstract.html) the case where one plays a slate of arms at once. In our work, however, the size of the slate is fixed. This paper also considers a similar problem. Another [similar work](https://doi.org/10.1007/978-3-642-16108-7_30) appeared in ALT 2010. Perhaps some of the ideas transfer.
* If you treat it as an experts problem (each expert recommends a different one of $2^N$ subsets), by following one expert, you can get estimate the performance of other experts who have non-empty intersections in their choice of arms to pull by using [importance weighting](https://en.wikipedia.org/wiki/Importance_sampling). An Exp4 type analysis might get you $O(N\sqrt{T})$ regret but $O(2^N T)$ running time.

EDIT below:

It seems to me that the budget constraint (not going below $0$) makes the problem intractable. Imagine you have a budget of $1$. The adversary can make one of the arms always pay off and the rest never pay off. So w.p. $(n-1)/n$ you go bust in the first round while the optimal strategy gets $T$ dollars after $T$ rounds. So your expected regret is at least $(n-1)T/n$ and you can't hope for a high probability bound at all.

It also seems that this can work for any initial budget. Say you start with $B$ dollars. Then the adversary can set all but one arms to pay $0$ and one arm to pay something like $2B$ w.p. $1/B$. I guess if you have a limit on the possible payout amount and a high enough initial budget, then this might leave room for an interesting problem.

> **Comments:**
> **username_0**: Hi Lev, thanks for the pointers. I agree that if I had an unlimited initial budget playing N parallel single arm bandits would solve the problem. The budget constraint however introduces coupling among arms and makes things interesting. In particular, in the first step you only have budget to play one arm. In the second step you can play either 11 arms or just 1 arm, depending on whether you got lucky in the first step and so on. So it is important to find a bunch of profitable arms early on that you then use tofund further exploration.  
> **username_6**: I didn't realize there was an initial budget (I now understand the "non-negative balance" part, but perhaps you can make it clearer in the question?) -- that makes the problem more interesting.  Also the "contextual" or experts version might be fun to consider.  Unfortunately, I do not know any more relevant references for this problem.  
> **username_7**: If I got the problem formulation right, you gain an extra $1 each round. Martin, could you perhaps clarify the question?  
> **username_6**: I think you gain whatever a machine pays if you play it and win and lose $1 whenever you decide to play.  

---

