3
$\begingroup$

I am trying to calculate the expected payout of the following strategy:

You have two one-armed bandits: one pays out \$$1$ with probability $0.4$, the other pays out \$$1$ with probability $0.5$, you don't know which is which.

You start with one of the bandits by chance and play this bandit while you're winning. As soon as you lose you switch to the other bandit and again play this bandit while you're winning... and so on for $1,000$ games altogether.

My question
How do you calculate the expected payout of the above strategy?

A thought
Intuitively this strategy should perform better than a completely random strategy (\$$450$) because you stick longer with the winning bandit.

$\endgroup$
9
  • $\begingroup$ The random strategy has an expectation of $\$450,$ not $\$900.$ Intuitively it must be better than yours because every time you get a winning signal you abandon the bandit! You should be switching when you lose, not when you win. Your strategy has an asymptotic expectation of $\$4/9\approx 0.444$ per game rather than $\$9/20=0.45.$ $\endgroup$
    – whuber
    Nov 16, 2018 at 21:09
  • $\begingroup$ @whuber: The last section was obviously not well thought through. I deleted it. Thank you. $\endgroup$
    – vonjd
    Nov 16, 2018 at 21:39
  • $\begingroup$ @whuber: ...but I think you misunderstood my question because I switch as soon as I lose. $\endgroup$
    – vonjd
    Nov 16, 2018 at 21:41
  • 1
    $\begingroup$ Let $p=2/5$ and $q=1/2$ be the payout chances and write $f(n,p)(t)$ for the probability generating function of the payout after $n$ plays when starting with the probability-$p$ bandit. These can be encapsulated as a vector $f(n)=(f(n,p),f(n,q))^\prime.$ Your strategy is $$f(n+1)=\pmatrix{tp&1-p\\1-q&tq}f(n)$$ with initial condition $f(0)=(1,1)^\prime.$ The solution obviously is $f(n)=P^nf(0)$ where $P$ is the foregoing transition matrix. As usual, the matrix powers can be found by diagonalizing $P$ and the expectation can be found by evaluating $d/dt(f(n,p)+f(n,q))/2$ at $t=1.$ $\endgroup$
    – whuber
    Nov 16, 2018 at 22:42
  • 1
    $\begingroup$ @whuber: I tried something along the same lines but you brought me on the right track - Thank you! $\endgroup$
    – vonjd
    Nov 17, 2018 at 8:54

1 Answer 1

1
$\begingroup$

First you construct the matrix with the transition probabilities, then you calculate the long run staying proportions via the normalized eigenvector of the biggest eigenvalue and last you weight this with the probability of payout to arrive at the expectation:

(P <- matrix(c(.4, .6, .5, .5), ncol = 2))
##      [,1] [,2]
## [1,]  0.4  0.5
## [2,]  0.6  0.5
lr <- eigen(P)$vectors[ , 1]
sum(c(.4, .5) * (lr / sum(lr)))
## [1] 0.4545455

This strategy is called "stick with the winners" and is especially effective when the differences in probability are big (which can easily be seen in the case of extreme cases). The soccer coach van Gaal is known to use it for penalty kicks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.