Suppose we have an unfair coin, \(p(H) = p\). At each time step, the gambler can bet on each coin, winning their bet if it comes up heads. The game ends when the gambler is broke, or has accumulated a wealth of \(N\).

The source code for this project can be found here.

In RL terms, we may describe this as an undiscounted stochastic markov process. We have \(S = \{1, \ldots, N - 1 \}\), \(S^+ = S \cap \{N\}\), \(a \in \{ 1, \ldots, \mathrm{min}(s, N - s) \}\), and \(\gamma = 1\). Further, we describe \(R = \delta_{s, N}\). (consider \(R = -1\) always to incentivize higher bets).

We shall set every value initially to \(0\).

We shall first proceed by a policy iteration approach. Thus, we can choose a deterministic policy \(\pi_0\), with \(\pi_0(s) = s\)

def v_0():
    return {x: 0 for x in range(1, N)}
    
def pi_0():
    return {x : 
        {y: 1 if y == x else 0 for y in range(1, N)}
        for x in range(1, N)
    }

and the reward criteria

def reward(s, a):
    return p * int(state + action == N) + (1-p) * int(state - action == N)
    
def value(state, action, values):
    return p * values[state + action] + (1-p) * values[state - action]

Then, we implement our policy evaluation subroutine

def update_value(pi, state, values):
    return sum(
        pi[state][action] * (reward(state, action) + value(state, action, values))
        for action in range(1, min(state, N - state))
    )
    
def diff(value, new_value):
    return max(
        abs(value[s] - new_value[s]) s in range(1, N)
    )
    
def evaluation(pi, values):
    new_value = {s: update_value(pi, s, values) for s in range(1, N)}
    while diff(value, new_value) > threshhold:
        new_value = {s: update_value(pi, s, values) for s in range(1, N)}
    return new_value

and implementing the policy iteration subroutine,

def argmax(state, values):
    best_action = 1
    best_value = 0
    
    for action in range(1, min(state, N - state)):
        new_value = value(pi, state, values)
        if new_value > best_value:
            best_action = action
            best_value = new_value
    
    return best_action
    
def iteration(pi, values):
    return {
        x: {
            {y: 1 if y == argmax(values, x) else 0}
        }
    }

Finally, putting this together, we have the following

def optimal_policy():
    pi = pi_0()
    values = v_0()
    
    for _ in range(iterations):
        values = evaluation(pi, values)
        pi = iteration(pi, values)
        
    return pi

Alternatively, we may consider an initial stochastic policy that chooses uniformly from the action space.

Back