Blackjack-v1¶

In [1]:
%matplotlib inline

import sys
import logging
import itertools

import numpy as np
np.random.seed(0)
import gym
import matplotlib.pyplot as plt

logging.basicConfig(level=logging.INFO,
        format='%(asctime)s [%(levelname)s] %(message)s',
        stream=sys.stdout, datefmt='%H:%M:%S')

Use Environment¶

In [2]:
env = gym.make('Blackjack-v1')
for key in vars(env):
    logging.info('%s: %s', key, vars(env)[key])
for key in vars(env.spec):
    logging.info('%s: %s', key, vars(env.spec)[key])

00:01:34 [INFO] env: <StepAPICompatibility<PassiveEnvChecker<BlackjackEnv<Blackjack-v1>>>>
00:01:34 [INFO] _action_space: None
00:01:34 [INFO] _observation_space: None
00:01:34 [INFO] _reward_range: None
00:01:34 [INFO] _metadata: None
00:01:34 [INFO] new_step_api: True
00:01:34 [INFO] _has_reset: False
00:01:34 [INFO] _disable_render_order_enforcing: False
00:01:34 [INFO] id: Blackjack-v1
00:01:34 [INFO] entry_point: gym.envs.toy_text.blackjack:BlackjackEnv
00:01:34 [INFO] reward_threshold: None
00:01:34 [INFO] nondeterministic: False
00:01:34 [INFO] max_episode_steps: None
00:01:34 [INFO] order_enforce: True
00:01:34 [INFO] autoreset: False
00:01:34 [INFO] disable_env_checker: False
00:01:34 [INFO] new_step_api: False
00:01:34 [INFO] kwargs: {'sab': True, 'natural': False}
00:01:34 [INFO] namespace: None
00:01:34 [INFO] name: Blackjack
00:01:34 [INFO] version: 1
In [3]:
def ob2state(observation):
    return observation[0], observation[1], int(observation[2])

def play_policy(env, policy=None, verbose=False):
    observation, _ = env.reset()
    reward, terminated, truncated = 0., False, False
    episode_reward, elapsed_steps = 0., 0
    if verbose:
        logging.info('observation = %s', observation)
    while True:
        if verbose:
            logging.info('player = %s, dealer = %s', env.player, env.dealer)
        if policy is None:
            action = env.action_space.sample()
        else:
            state = ob2state(observation)
            action = np.random.choice(env.action_space.n, p=policy[state])
        if verbose:
            logging.info('action = %s', action)
        observation, reward, terminated, truncated, _ = env.step(action)
        if verbose:
            logging.info('observation = %s', observation)
            logging.info('reward = %s', reward)
            logging.info('terminated = %s', terminated)
            logging.info('truncated = %s', truncated)
        episode_reward += reward
        elapsed_steps += 1
        if terminated or truncated:
            break
    return episode_reward, elapsed_steps

episode_reward, elapsed_steps = play_policy(env, verbose=True)
logging.info("episode reward: %.2f", episode_reward)

00:01:34 [INFO] observation = (20, 5, False)
00:01:34 [INFO] player = [10, 10], dealer = [5, 10]
00:01:34 [INFO] action = 0
00:01:34 [INFO] observation = (20, 5, False)
00:01:34 [INFO] reward = 1.0
00:01:34 [INFO] terminated = True
00:01:34 [INFO] truncated = False
00:01:34 [INFO] episode reward: 1.00

On-policy Monte Carlo¶

Monte Carlo prediction

In [4]:
def evaluate_action_monte_carlo(env, policy, episode_num=500000):
    q = np.zeros_like(policy)  # action value
    c = np.zeros_like(policy)  # count
    for _ in range(episode_num):
        # play an episode
        state_actions = []
        observation, _ = env.reset()
        while True:
            state = ob2state(observation)
            action = np.random.choice(env.action_space.n, p=policy[state])
            state_actions.append((state, action))
            observation, reward, terminated, truncated, _ = env.step(action)
            if terminated or truncated:
                break  # end of episode
        g = reward  # return
        for state, action in state_actions:
            c[state][action] += 1.
            q[state][action] += (g - q[state][action]) / c[state][action]
    return q
In [5]:
policy = np.zeros((22, 11, 2, 2))
policy[20:, :, :, 0] = 1  # stand when >=20
policy[:20, :, :, 1] = 1  # hit when <20

q = evaluate_action_monte_carlo(env, policy)  # action value
v = (q * policy).sum(axis=-1)  # state value
In [6]:
def plot(data):
    fig, axes = plt.subplots(1, 2, figsize=(9, 4))
    titles = ['without ace', 'with ace']
    have_aces = [0, 1]
    extent = [12, 22, 1, 11]
    for title, have_ace, axis in zip(titles, have_aces, axes):
        dat = data[extent[0]:extent[1], extent[2]:extent[3], have_ace].T
        axis.imshow(dat, extent=extent, origin='lower')
        axis.set_xlabel('player sum')
        axis.set_ylabel('dealer showing')
        axis.set_title(title)
In [7]:
plot(v)

Test Policy

In [8]:
episode_rewards = []
for episode in range(100):
    episode_reward, elapsed_steps = play_policy(env, policy)
    episode_rewards.append(episode_reward)
    logging.info('test episode %d: reward = %.2f, steps = %d',
            episode, episode_reward, elapsed_steps)
logging.info('average episode reward = %.2f ± %.2f',
        np.mean(episode_rewards), np.std(episode_rewards))

00:05:08 [INFO] test episode 0: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 1: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 2: reward = 1.00, steps = 4
00:05:08 [INFO] test episode 3: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 4: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 5: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 6: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 7: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 8: reward = 1.00, steps = 2
00:05:08 [INFO] test episode 9: reward = 1.00, steps = 3
00:05:08 [INFO] test episode 10: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 11: reward = 1.00, steps = 2
00:05:08 [INFO] test episode 12: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 13: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 14: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 15: reward = 1.00, steps = 2
00:05:08 [INFO] test episode 16: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 17: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 18: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 19: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 20: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 21: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 22: reward = 0.00, steps = 2
00:05:08 [INFO] test episode 23: reward = -1.00, steps = 4
00:05:08 [INFO] test episode 24: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 25: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 26: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 27: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 28: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 29: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 30: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 31: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 32: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 33: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 34: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 35: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 36: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 37: reward = 1.00, steps = 3
00:05:08 [INFO] test episode 38: reward = 1.00, steps = 2
00:05:08 [INFO] test episode 39: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 40: reward = 0.00, steps = 1
00:05:08 [INFO] test episode 41: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 42: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 43: reward = 0.00, steps = 2
00:05:08 [INFO] test episode 44: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 45: reward = 1.00, steps = 3
00:05:08 [INFO] test episode 46: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 47: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 48: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 49: reward = 1.00, steps = 7
00:05:08 [INFO] test episode 50: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 51: reward = 1.00, steps = 3
00:05:08 [INFO] test episode 52: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 53: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 54: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 55: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 56: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 57: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 58: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 59: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 60: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 61: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 62: reward = 1.00, steps = 2
00:05:08 [INFO] test episode 63: reward = 0.00, steps = 1
00:05:08 [INFO] test episode 64: reward = 1.00, steps = 2
00:05:08 [INFO] test episode 65: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 66: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 67: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 68: reward = 1.00, steps = 2
00:05:08 [INFO] test episode 69: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 70: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 71: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 72: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 73: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 74: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 75: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 76: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 77: reward = 1.00, steps = 1
00:05:08 [INFO] test episode 78: reward = 0.00, steps = 2
00:05:08 [INFO] test episode 79: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 80: reward = 1.00, steps = 2
00:05:08 [INFO] test episode 81: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 82: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 83: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 84: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 85: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 86: reward = 1.00, steps = 4
00:05:08 [INFO] test episode 87: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 88: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 89: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 90: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 91: reward = -1.00, steps = 3
00:05:08 [INFO] test episode 92: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 93: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 94: reward = 1.00, steps = 2
00:05:08 [INFO] test episode 95: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 96: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 97: reward = -1.00, steps = 1
00:05:08 [INFO] test episode 98: reward = -1.00, steps = 2
00:05:08 [INFO] test episode 99: reward = 1.00, steps = 2
00:05:08 [INFO] average episode reward = -0.35 ± 0.91
In [9]:
observation, _ = env.reset()
logging.info("observation = %s", observation)
state = ob2state(observation)
logging.info("state = %s", state)
probs = policy[state]
logging.info("probs = %s", probs)

00:05:08 [INFO] observation = (12, 5, False)
00:05:08 [INFO] state = (12, 5, 0)
00:05:08 [INFO] probs = [0. 1.]

Monte Carlo update with exploring start¶

In [10]:
def monte_carlo_with_exploring_start(env, episode_num=500000):
    policy = np.zeros((22, 11, 2, 2))
    policy[:, :, :, 1] = 1.
    q = np.zeros_like(policy)  # action values
    c = np.zeros_like(policy)  # counts
    for _ in range(episode_num):
        # choose initial state randomly
        state = (np.random.randint(12, 22),
                 np.random.randint(1, 11),
                 np.random.randint(2))
        action = np.random.randint(2)
        # play an episode
        env.reset()
        if state[2]:  # has ace
            env.unwrapped.player = [1, state[0] - 11]
        else:  # no ace
            if state[0] == 21:
                env.unwrapped.player = [10, 9, 2]
            else:
                env.unwrapped.player = [10, state[0] - 10]
        env.unwrapped.dealer[0] = state[1]
        state_actions = []
        while True:
            state_actions.append((state, action))
            observation, reward, terminated, truncated, _ = env.step(action)
            if terminated or truncated:
                break  # end of episode
            state = ob2state(observation)
            action = np.random.choice(env.action_space.n, p=policy[state])
        g = reward  # return
        for state, action in state_actions:
            c[state][action] += 1.
            q[state][action] += (g - q[state][action]) / c[state][action]
            a = q[state].argmax()
            policy[state] = 0.
            policy[state][a] = 1.
    return policy, q
In [11]:
policy, q = monte_carlo_with_exploring_start(env)
v = q.max(axis=-1)
In [12]:
plot(policy.argmax(-1))
plot(v)

Monte Carlo update with soft poicy

In [13]:
def monte_carlo_with_soft(env, episode_num=500000, epsilon=0.1):
    policy = np.ones((22, 11, 2, 2)) * 0.5  # soft policy
    q = np.zeros_like(policy)  # action values
    c = np.zeros_like(policy)  # counts
    for _ in range(episode_num):
        # play an episode
        state_actions = []
        observation, _ = env.reset()
        while True:
            state = ob2state(observation)
            action = np.random.choice(env.action_space.n, p=policy[state])
            state_actions.append((state, action))
            observation, reward, terminated, truncated, _ = env.step(action)
            if terminated or truncated:
                break  # end of episode
        g = reward  # return
        for state, action in state_actions:
            c[state][action] += 1.
            q[state][action] += (g - q[state][action]) / c[state][action]
            # soft update
            a = q[state].argmax()
            policy[state] = epsilon / 2.
            policy[state][a] += (1. - epsilon)
    return policy, q
In [14]:
policy, q = monte_carlo_with_soft(env)
v = q.max(axis=-1)
In [15]:
plot(policy.argmax(-1))
plot(v)

Test Policy

In [16]:
episode_rewards = []
for episode in range(100):
    episode_reward, elapsed_steps = play_policy(env, policy)
    episode_rewards.append(episode_reward)
    logging.info('test episode %d: reward = %.2f, steps = %d',
            episode, episode_reward, elapsed_steps)
logging.info('average episode reward = %.2f ± %.2f',
        np.mean(episode_rewards), np.std(episode_rewards))

00:11:20 [INFO] test episode 0: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 1: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 2: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 3: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 4: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 5: reward = 0.00, steps = 2
00:11:20 [INFO] test episode 6: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 7: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 8: reward = 0.00, steps = 1
00:11:20 [INFO] test episode 9: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 10: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 11: reward = -1.00, steps = 3
00:11:20 [INFO] test episode 12: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 13: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 14: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 15: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 16: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 17: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 18: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 19: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 20: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 21: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 22: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 23: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 24: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 25: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 26: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 27: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 28: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 29: reward = -1.00, steps = 3
00:11:20 [INFO] test episode 30: reward = -1.00, steps = 3
00:11:20 [INFO] test episode 31: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 32: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 33: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 34: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 35: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 36: reward = 0.00, steps = 1
00:11:20 [INFO] test episode 37: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 38: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 39: reward = 1.00, steps = 4
00:11:20 [INFO] test episode 40: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 41: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 42: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 43: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 44: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 45: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 46: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 47: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 48: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 49: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 50: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 51: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 52: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 53: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 54: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 55: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 56: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 57: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 58: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 59: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 60: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 61: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 62: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 63: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 64: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 65: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 66: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 67: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 68: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 69: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 70: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 71: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 72: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 73: reward = 0.00, steps = 2
00:11:20 [INFO] test episode 74: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 75: reward = 0.00, steps = 2
00:11:20 [INFO] test episode 76: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 77: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 78: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 79: reward = -1.00, steps = 2
00:11:20 [INFO] test episode 80: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 81: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 82: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 83: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 84: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 85: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 86: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 87: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 88: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 89: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 90: reward = -1.00, steps = 3
00:11:20 [INFO] test episode 91: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 92: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 93: reward = -1.00, steps = 1
00:11:20 [INFO] test episode 94: reward = 1.00, steps = 2
00:11:20 [INFO] test episode 95: reward = 0.00, steps = 3
00:11:20 [INFO] test episode 96: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 97: reward = 1.00, steps = 1
00:11:20 [INFO] test episode 98: reward = 1.00, steps = 3
00:11:20 [INFO] test episode 99: reward = 1.00, steps = 2
00:11:20 [INFO] average episode reward = -0.06 ± 0.97

Off-Policy Monte Carlo Update¶

Monte Carlo evaluation with importance sampling

In [17]:
def evaluate_monte_carlo_importance_sample(env, policy, behavior_policy,
        episode_num=500000):
    q = np.zeros_like(policy)  # action values
    c = np.zeros_like(policy)  # counts
    for _ in range(episode_num):
        # play episode using behavior policy
        state_actions = []
        observation, _ = env.reset()
        while True:
            state = ob2state(observation)
            action = np.random.choice(env.action_space.n,
                    p=behavior_policy[state])
            state_actions.append((state, action))
            observation, reward, terminated, truncated, _ = env.step(action)
            if terminated or truncated:
                break  # finish the episode
        g = reward  # return
        rho = 1.  # importance sampling ratio
        for state, action in reversed(state_actions):
            c[state][action] += rho
            q[state][action] += (rho / c[state][action] * (g - q[state][action]))
            rho *= (policy[state][action] / behavior_policy[state][action])
            if rho == 0:
                break  # early stop
    return q
In [18]:
policy = np.zeros((22, 11, 2, 2))
policy[20:, :, :, 0] = 1  # stand when >=20
policy[:20, :, :, 1] = 1  # hit when <20
behavior_policy = np.ones_like(policy) * 0.5
q = evaluate_monte_carlo_importance_sample(env, policy, behavior_policy)
v = (q * policy).sum(axis=-1)
In [19]:
plot(v)

Monte Carlo update with importance sampling

In [20]:
def monte_carlo_importance_sample(env, episode_num=500000):
    policy = np.zeros((22, 11, 2, 2))
    policy[:, :, :, 0] = 1.
    behavior_policy = np.ones_like(policy) * 0.5  # soft policy
    q = np.zeros_like(policy)  # action values
    c = np.zeros_like(policy)  # counts
    for _ in range(episode_num):
        # play using behavior policy
        state_actions = []
        observation, _ = env.reset()
        while True:
            state = ob2state(observation)
            action = np.random.choice(env.action_space.n,
                    p=behavior_policy[state])
            state_actions.append((state, action))
            observation, reward, terminated, truncated, _ = env.step(action)
            if terminated or truncated:
                break  # finish the episode
        g = reward  # return
        rho = 1.  # importance sampling ratio
        for state, action in reversed(state_actions):
            c[state][action] += rho
            q[state][action] += (rho / c[state][action] * (g - q[state][action]))
            # improve the policy
            a = q[state].argmax()
            policy[state] = 0.
            policy[state][a] = 1.
            if a != action:  # early stop
                break
            rho /= behavior_policy[state][action]
    return policy, q
In [21]:
policy, q = monte_carlo_importance_sample(env)
v = q.max(axis=-1)
In [22]:
plot(policy.argmax(-1))
plot(v)

Test Policy

In [23]:
episode_rewards = []
for episode in range(100):
    episode_reward, elapsed_steps = play_policy(env, policy)
    episode_rewards.append(episode_reward)
    logging.info('test episode %d: reward = %.2f, steps = %d',
            episode, episode_reward, elapsed_steps)
logging.info('average episode reward = %.2f ± %.2f',
        np.mean(episode_rewards), np.std(episode_rewards))

00:17:35 [INFO] test episode 0: reward = 1.00, steps = 3
00:17:35 [INFO] test episode 1: reward = 0.00, steps = 1
00:17:35 [INFO] test episode 2: reward = -1.00, steps = 3
00:17:35 [INFO] test episode 3: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 4: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 5: reward = -1.00, steps = 3
00:17:35 [INFO] test episode 6: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 7: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 8: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 9: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 10: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 11: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 12: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 13: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 14: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 15: reward = -1.00, steps = 3
00:17:35 [INFO] test episode 16: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 17: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 18: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 19: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 20: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 21: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 22: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 23: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 24: reward = 0.00, steps = 1
00:17:35 [INFO] test episode 25: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 26: reward = 0.00, steps = 3
00:17:35 [INFO] test episode 27: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 28: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 29: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 30: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 31: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 32: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 33: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 34: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 35: reward = -1.00, steps = 3
00:17:35 [INFO] test episode 36: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 37: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 38: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 39: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 40: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 41: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 42: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 43: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 44: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 45: reward = -1.00, steps = 3
00:17:35 [INFO] test episode 46: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 47: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 48: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 49: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 50: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 51: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 52: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 53: reward = 0.00, steps = 1
00:17:35 [INFO] test episode 54: reward = 1.00, steps = 4
00:17:35 [INFO] test episode 55: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 56: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 57: reward = 0.00, steps = 3
00:17:35 [INFO] test episode 58: reward = -1.00, steps = 4
00:17:35 [INFO] test episode 59: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 60: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 61: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 62: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 63: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 64: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 65: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 66: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 67: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 68: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 69: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 70: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 71: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 72: reward = 1.00, steps = 3
00:17:35 [INFO] test episode 73: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 74: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 75: reward = 1.00, steps = 6
00:17:35 [INFO] test episode 76: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 77: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 78: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 79: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 80: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 81: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 82: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 83: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 84: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 85: reward = 1.00, steps = 2
00:17:35 [INFO] test episode 86: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 87: reward = -1.00, steps = 3
00:17:35 [INFO] test episode 88: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 89: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 90: reward = 0.00, steps = 2
00:17:35 [INFO] test episode 91: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 92: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 93: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 94: reward = 1.00, steps = 1
00:17:35 [INFO] test episode 95: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 96: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 97: reward = -1.00, steps = 1
00:17:35 [INFO] test episode 98: reward = -1.00, steps = 2
00:17:35 [INFO] test episode 99: reward = -1.00, steps = 1
00:17:35 [INFO] average episode reward = 0.06 ± 0.97
In [24]:
env.close()