An RL Approach for Inventory Management (Part 9)

Back to Portfolio of Projects | LearnableLoopAI.com | Blog |

1 Generalized Policy Iteration (GPI)

In previous projects we have only dealt with the prediction problem. In this project we move on to the control problem. We stay in the model-free or learning domain (rather than planning), i.e. making use of Reinforcement Learning algorithms. We will explore the depth of update dimension, considering both bootstrapping and non-bootstrapping methods like Temporal-Difference (TD) and Monte-Carlo (MC) algorithms respectively.

What is different about Control, rather than Prediction, is the depence on the concept of Generalized Policy Iteration (GPI).

The key concept of GPI is that we can: - Evaluate a policy with any Policy Evaluation method - Improve a policy with any Policy Improvement method

2 GPI with Evaluation as Monte-Carlo (MC)

Here is a reasonable way to approach MC Control based on what we have done so far: - do MC Policy Evaluation (which is essentially MC Prediction) - do greedy Policy Improvement - do MC Policy Evaluation on the improved policy - etc., etc.

However, this naive approach leads to some complications.

2.1 Greedy Policy Improvement requires $P$ and $R$

The first complication is that: - Greedy Policy Improvement requires the - state transition probability function $P$ - reward function $R$ This is not available in the model-free domain. (They were, however, available in the model-based domain when we performed dynamic programming).

We address this complication by noting that

$π_{D}^{'} (s) = \underset{a \in A}{arg max} {R (s, a) + γ \sum_{s^{'} \in N} P (s, a, s^{'}) \cdot V^{π} (s^{'})} for all s \in N$

can be expressed more concisely as:

$π_{D}^{'} (s) = \underset{a \in A}{arg max} Q^{π} (s, a) for all s \in N$

This is valuable because: - Instead of doing - Policy Evaluation to calculate $V^{π}$ - We do - Policy Evaluation to calculate $Q^{π}$ (i.e. MC Prediction for the Action Value Function, $Q$ )

2.2 Biased initial random occurrences of returns

The second complication is that updates can get biased by initial random occurrences of returns. This could prevent certain actions from being sufficiently chosen. This will lead to inaccurate estimates of the action values for those actions. We want to exploit actions that provide better returns but at the same time also be sure to explore all possible actions. This problem is known as the exploration-exploitation dilemma.

The way to address this complication is to modify our Tabular MC Control algorithm: - Instead of doing - greedy Policy Improvement - we want to do - $ϵ$ -greedy Policy Improvement

This impoved stochastic policy is defined as:

$π^{'} (s, a) = {\begin{cases} \frac{ϵ}{| A |} + 1 - ϵ & if a = {arg max}_{b \in A} Q (s, b) \\ \frac{ϵ}{| A |} & otherwise \end{cases}$

This means the: - exploit probability is: $1 - ϵ$ - select the action that maximizes $Q$ for a given state - explore probability is: $ϵ$ - uniform-randomly select an allowable action

The deterministic greedy policy $π_{D}^{'}$ is a special case of the $ϵ$ -greedy policy $π^{'}$ . This happens when $ϵ = 0$ .

!python --version

Python 3.7.15

from typing import Tuple, Callable, Sequence, Mapping, Iterator, Iterable
import itertools
import inspect
from pprint import pprint

3 Monte-Carlo (MC) Control

3.1 TAB MC Control

We need to consider two more aspects:

Adequate exploration of:
- actions
  - enabled by $ϵ$ -greedy Policy Improvement
- states
  - uniform-sample the initial state of a trace experience the non-terminal states $N$
Reduced exploration as:
- Action Value Function keeps improving
- Zero $ϵ$ as number of episodes goes to infinity
- also known as GLIE: Greedy in the Limit with Infinite Exploration
  - all state-action pairs are explored infinitely many times
  - the policy converges to a greedy policy
- reduce $ϵ$ as a function of the number of episodes $k$ , to be $ϵ_{k} = \frac{1}{k}$

Here is a summary of the GLIE Tabular Monte-Carlo Control algorithm.

For each episode (terminating trace experience): - Generate the trace experience (episode) with actions sampled from the $ϵ$ -greedy policy $π$ coming from the latest estimate of the Action Value Function $Q$ - Sample the initial state of the trace experience uniformly from the non-terminal states $N$ - We now have a trace experience: $ S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, …, R_T, S_T$ - The return $G_{t}$ associated with $(S_{t}, A_{t})$ is: $G_{t} = R_{t + 1} + γ R_{t + 2} + γ^{2} R_{t + 3} + . . . + γ^{T - t - 1} R_{T}$ - End of trace updates:

$C o u n t (S_{t}, A_{t}) \leftarrow C o u n t (S_{t}, A_{t}) + 1$

$Q (S_{t}, A_{t}) \leftarrow Q (S_{t}, A_{t}) + \frac{1}{C o u n t (S_{t}, A_{t})} \cdot [G_{t} - Q (S_{t}, A_{t})]$

$ϵ \leftarrow \frac{1}{k}$

3.2 FAP MC Control

The adaptation for Function Approximation is simple. Instead of the above udpate, we have:

$Δ w = α \cdot [G_{t} - Q (S_{t}, A_{t}; w)] \cdot \nabla_{w} Q (S_{t}, A_{t}; w)$

where $α$ is the learning rate and $G_{t}$ is the trace experience return from state $S_{t}$ after taking action $A_{t}$ at time $t$ on a trace experience.

3.3 Generalized implementation of GLIE Monte-Carlo Control

The following code can handle both TAB and FAP cases.

def greedy_policy_from_qvf(
    q: QValueFunctionApprox[S, A],
    actions: Callable[[NonTerminal[S]], Iterable[A]]
) -> DeterministicPolicy[S, A]:
    def optimal_action(s: S) -> A:
        _, a = q.argmax((NonTerminal(s), a) for a in actions(NonTerminal(s)))
        return a
    return DeterministicPolicy(optimal_action)

def epsilon_greedy_policy(
    q: QValueFunctionApprox[S, A],
    mdp: MarkovDecisionProcess[S, A],
    ε: float = 0.0
) -> Policy[S, A]:
    def explore(s: S, mdp=mdp) -> Iterable[A]:
        return mdp.actions(NonTerminal(s))
    return RandomPolicy(Categorical(
        {UniformPolicy(explore): ε,
         greedy_policy_from_qvf(q, mdp.actions): 1 - ε}
    ))

def glie_mc_control(
    mdp: MarkovDecisionProcess[S, A],
    states: NTStateDistribution[S],
    approx_0: QValueFunctionApprox[S, A],
    γ: float,
    ϵ_as_func_of_episodes: Callable[[int], float],
    episode_length_tolerance: float = 1e-6
) -> Iterator[QValueFunctionApprox[S, A]]:
    q: QValueFunctionApprox[S, A] = approx_0
    p: Policy[S, A] = epsilon_greedy_policy(q, mdp, 1.0)
    yield q

    num_episodes: int = 0
    while True:
        trace: Iterable[TransitionStep[S, A]] = \
            mdp.simulate_action(states, p) #.
            # mdp.simulate_actions(states, p) #.
        num_episodes += 1
        for step in returns(trace, γ, episode_length_tolerance):
            q = q.update([((step.state, step.action), step.return_)])
        p = epsilon_greedy_policy(q, mdp, ϵ_as_func_of_episodes(num_episodes))
        yield q

We run the GLIE TAB MC Control algorithm on the Inventory problem.

Let us set the capacity $C = 5$ , but keep the other parameters as before.

# capacity: int = 2
capacity: int = 5
poisson_lambda: float = 1.0
holding_cost: float = 1.0
stockout_cost: float = 10.0
gamma: float = 0.9

si_mdp: SimpleInventoryMDPCap = SimpleInventoryMDPCap(
    capacity=capacity,
    poisson_lambda=poisson_lambda,
    holding_cost=holding_cost,
    stockout_cost=stockout_cost
)

mc_episode_length_tol: float = 1e-5
epsilon_as_func_of_episodes: Callable[[int], float] = lambda k: k**-0.5
initial_learning_rate: float = 0.1
half_life: float = 10000.0
exponent: float = 1.0

initial_qvf_dict: Mapping[Tuple[NonTerminal[InventoryState], int], float] = {
    (s, a): 0. for s in si_mdp.non_terminal_states for a in si_mdp.actions(s)
}
# initial_qvf_dict

learning_rate_func: Callable[[int], float] = learning_rate_schedule(
    initial_learning_rate=initial_learning_rate,
    half_life=half_life,
    exponent=exponent
)

qvfas: Iterator[QValueFunctionApprox[InventoryState, int]] = glie_mc_control(
    mdp=si_mdp, 
    states=Choose(si_mdp.non_terminal_states),
    approx_0=Tabular(
        values_map=initial_qvf_dict, 
        count_to_weight_func=learning_rate_func
    ), 
    γ=gamma, 
    ϵ_as_func_of_episodes=epsilon_as_func_of_episodes, 
    episode_length_tolerance=mc_episode_length_tol
)
qvfas

<generator object glie_mc_control at 0x7ff9e1b4d350>

Now we get the final estimate of the Optimal Action-Value Function after n_episodes. Then we extract from it the estimate of the Optimal State-Value Function and the Optimal Policy.

n_episodes = 10_000

%%time
qvfa_lst = [qvfa for qvfa in itertools.islice(qvfas, n_episodes)]

CPU times: user 2min 50s, sys: 7.34 s, total: 2min 57s
Wall time: 2min 48s

final_qvfa: QValueFunctionApprox[InventoryState, int] = iterate.last(qvfa_lst)

final_qvfa

Tabular(values_map={(NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 0): -34.03322148393033, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 1): -29.020209183999388, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 2): -26.627145648076866, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 3): -29.14229159609633, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 4): -29.083772263900514, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 5): -30.59031203906599, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 0): -25.32177188084976, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 1): -20.960023620302074, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 2): -19.771390238869504, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 3): -21.918336203169535, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 4): -22.204214961666906, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 0): -21.59608715735911, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 1): -18.514480015418165, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 2): -19.729972311340145, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 3): -20.670368262219455, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 0): -22.505027675244786, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 1): -18.498951466322506, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 2): -23.631308215603628, (NonTerminal(state=InventoryState(on_hand=0, on_order=4)), 0): -21.064211166622616, (NonTerminal(state=InventoryState(on_hand=0, on_order=4)), 1): -25.700858037710592, (NonTerminal(state=InventoryState(on_hand=0, on_order=5)), 0): -23.87449284911821, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 0): -24.28212841574819, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 1): -23.07702634694885, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 2): -20.08614993159479, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 3): -22.578766436037245, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 4): -23.67197364066413, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 0): -23.1976582684385, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 1): -19.28700559050116, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 2): -21.194611200755286, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 3): -20.787724580885936, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 0): -21.920701267313003, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 1): -20.436319583369052, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 2): -22.716447291896973, (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 0): -22.639086837096524, (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 1): -24.14606280853149, (NonTerminal(state=InventoryState(on_hand=1, on_order=4)), 0): -24.284458257076704, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 0): -22.688895113138887, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 1): -20.353379740767895, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 2): -22.30071399052781, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 3): -23.729150109387337, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 0): -22.827065624947515, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 1): -21.25757526657738, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 2): -24.68781063371742, (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 0): -22.75024821444209, (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 1): -24.83171253975065, (NonTerminal(state=InventoryState(on_hand=2, on_order=3)), 0): -24.809513898197483, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 0): -24.40754279540118, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 1): -22.718947367168315, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 2): -24.324439592173484, (NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 0): -23.388534356752288, (NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 1): -24.26983392987888, (NonTerminal(state=InventoryState(on_hand=3, on_order=2)), 0): -26.345027269838162, (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 0): -24.387050038557934, (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 1): -26.536561759412, (NonTerminal(state=InventoryState(on_hand=4, on_order=1)), 0): -25.347216865676412, (NonTerminal(state=InventoryState(on_hand=5, on_order=0)), 0): -29.056513846485817}, counts_map={(NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 1): 2698, (NonTerminal(state=InventoryState(on_hand=4, on_order=1)), 0): 3805, (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 0): 78127, (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 1): 4287, (NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 0): 122974, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 2): 2009, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 1): 82490, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 1): 205196, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 3): 1250, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 1): 2826, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 0): 1140, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 5): 71, (NonTerminal(state=InventoryState(on_hand=0, on_order=5)), 0): 550, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 1): 84122, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 3): 1201, (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 0): 1920, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 0): 473, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 3): 902, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 0): 632, (NonTerminal(state=InventoryState(on_hand=3, on_order=2)), 0): 2696, (NonTerminal(state=InventoryState(on_hand=5, on_order=0)), 0): 6130, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 2): 250, (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 0): 6067, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 2): 3552, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 0): 9349, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 0): 100, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 2): 7695, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 4): 546, (NonTerminal(state=InventoryState(on_hand=0, on_order=4)), 1): 38, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 1): 52886, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 0): 442, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 0): 52, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 3): 1225, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 4): 99, (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 1): 453, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 2): 109272, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 4): 151, (NonTerminal(state=InventoryState(on_hand=1, on_order=4)), 0): 708, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 2): 4748, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 2): 4694, (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 1): 1474, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 2): 3203, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 0): 10985, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 0): 25991, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 3): 931, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 1): 8558, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 1): 169733, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 0): 636, (NonTerminal(state=InventoryState(on_hand=0, on_order=4)), 0): 982, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 2): 13227, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 3): 873, (NonTerminal(state=InventoryState(on_hand=2, on_order=3)), 0): 1645, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 1): 40806, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 1): 1986, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 1): 259, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 2): 776}, count_to_weight_func=<function learning_rate_schedule.<locals>.lr_func at 0x7ff9e1b4bc20>)

def get_vf_and_policy_from_qvf(
    mdp: FiniteMarkovDecisionProcess[S, A],
    qvf: QValueFunctionApprox[S, A]
) -> Tuple[V[S], FiniteDeterministicPolicy[S, A]]:
    opt_vf: V[S] = {
        s: max(qvf((s, a)) for a in mdp.actions(s))
        for s in mdp.non_terminal_states
    }
    opt_policy: FiniteDeterministicPolicy[S, A] = \
        FiniteDeterministicPolicy({
            s.state: qvf.argmax((s, a) for a in mdp.actions(s))[1]
            for s in mdp.non_terminal_states
        })
    return opt_vf, opt_policy

opt_svf, opt_pol = get_vf_and_policy_from_qvf(
    mdp=si_mdp,
    qvf=final_qvfa
)

print(f"GLIE MC Optimal Value Function with {n_episodes:d} episodes")
pprint(opt_svf)

GLIE MC Optimal Value Function with 10000 episodes
{NonTerminal(state=InventoryState(on_hand=0, on_order=0)): -26.627145648076866,
 NonTerminal(state=InventoryState(on_hand=0, on_order=1)): -19.771390238869504,
 NonTerminal(state=InventoryState(on_hand=0, on_order=2)): -18.514480015418165,
 NonTerminal(state=InventoryState(on_hand=0, on_order=3)): -18.498951466322506,
 NonTerminal(state=InventoryState(on_hand=0, on_order=4)): -21.064211166622616,
 NonTerminal(state=InventoryState(on_hand=0, on_order=5)): -23.87449284911821,
 NonTerminal(state=InventoryState(on_hand=1, on_order=0)): -20.08614993159479,
 NonTerminal(state=InventoryState(on_hand=1, on_order=1)): -19.28700559050116,
 NonTerminal(state=InventoryState(on_hand=1, on_order=2)): -20.436319583369052,
 NonTerminal(state=InventoryState(on_hand=1, on_order=3)): -22.639086837096524,
 NonTerminal(state=InventoryState(on_hand=1, on_order=4)): -24.284458257076704,
 NonTerminal(state=InventoryState(on_hand=2, on_order=0)): -20.353379740767895,
 NonTerminal(state=InventoryState(on_hand=2, on_order=1)): -21.25757526657738,
 NonTerminal(state=InventoryState(on_hand=2, on_order=2)): -22.75024821444209,
 NonTerminal(state=InventoryState(on_hand=2, on_order=3)): -24.809513898197483,
 NonTerminal(state=InventoryState(on_hand=3, on_order=0)): -22.718947367168315,
 NonTerminal(state=InventoryState(on_hand=3, on_order=1)): -23.388534356752288,
 NonTerminal(state=InventoryState(on_hand=3, on_order=2)): -26.345027269838162,
 NonTerminal(state=InventoryState(on_hand=4, on_order=0)): -24.387050038557934,
 NonTerminal(state=InventoryState(on_hand=4, on_order=1)): -25.347216865676412,
 NonTerminal(state=InventoryState(on_hand=5, on_order=0)): -29.056513846485817}

print(f"GLIE MC Optimal Policy with {n_episodes:d} episodes")
pprint(opt_pol)

GLIE MC Optimal Policy with 10000 episodes
For State InventoryState(on_hand=0, on_order=0): Do Action 2
For State InventoryState(on_hand=0, on_order=1): Do Action 2
For State InventoryState(on_hand=0, on_order=2): Do Action 1
For State InventoryState(on_hand=0, on_order=3): Do Action 1
For State InventoryState(on_hand=0, on_order=4): Do Action 0
For State InventoryState(on_hand=0, on_order=5): Do Action 0
For State InventoryState(on_hand=1, on_order=0): Do Action 2
For State InventoryState(on_hand=1, on_order=1): Do Action 1
For State InventoryState(on_hand=1, on_order=2): Do Action 1
For State InventoryState(on_hand=1, on_order=3): Do Action 0
For State InventoryState(on_hand=1, on_order=4): Do Action 0
For State InventoryState(on_hand=2, on_order=0): Do Action 1
For State InventoryState(on_hand=2, on_order=1): Do Action 1
For State InventoryState(on_hand=2, on_order=2): Do Action 0
For State InventoryState(on_hand=2, on_order=3): Do Action 0
For State InventoryState(on_hand=3, on_order=0): Do Action 1
For State InventoryState(on_hand=3, on_order=1): Do Action 0
For State InventoryState(on_hand=3, on_order=2): Do Action 0
For State InventoryState(on_hand=4, on_order=0): Do Action 0
For State InventoryState(on_hand=4, on_order=1): Do Action 0
For State InventoryState(on_hand=5, on_order=0): Do Action 0

For comparison, we run a Value Iteration to find the true Optimal Value Function and Optimal Policy.

true_opt_svf, true_opt_pol = value_iteration_result(mdp=si_mdp, gamma=gamma)

print("True Optimal State Value Function")
pprint(true_opt_svf)

True Optimal State Value Function
{NonTerminal(state=InventoryState(on_hand=0, on_order=0)): -26.98163492786722,
 NonTerminal(state=InventoryState(on_hand=0, on_order=1)): -19.9909558006178,
 NonTerminal(state=InventoryState(on_hand=0, on_order=2)): -18.86849301795165,
 NonTerminal(state=InventoryState(on_hand=0, on_order=3)): -19.934022635857023,
 NonTerminal(state=InventoryState(on_hand=0, on_order=4)): -20.91848526863397,
 NonTerminal(state=InventoryState(on_hand=0, on_order=5)): -22.77205311116058,
 NonTerminal(state=InventoryState(on_hand=1, on_order=0)): -20.9909558006178,
 NonTerminal(state=InventoryState(on_hand=1, on_order=1)): -19.86849301795165,
 NonTerminal(state=InventoryState(on_hand=1, on_order=2)): -20.934022635857026,
 NonTerminal(state=InventoryState(on_hand=1, on_order=3)): -21.918485268633972,
 NonTerminal(state=InventoryState(on_hand=1, on_order=4)): -23.77205311116058,
 NonTerminal(state=InventoryState(on_hand=2, on_order=0)): -20.86849301795165,
 NonTerminal(state=InventoryState(on_hand=2, on_order=1)): -21.934022635857023,
 NonTerminal(state=InventoryState(on_hand=2, on_order=2)): -22.91848526863397,
 NonTerminal(state=InventoryState(on_hand=2, on_order=3)): -24.77205311116058,
 NonTerminal(state=InventoryState(on_hand=3, on_order=0)): -22.934022635857026,
 NonTerminal(state=InventoryState(on_hand=3, on_order=1)): -23.918485268633972,
 NonTerminal(state=InventoryState(on_hand=3, on_order=2)): -25.772053111160584,
 NonTerminal(state=InventoryState(on_hand=4, on_order=0)): -24.91848526863397,
 NonTerminal(state=InventoryState(on_hand=4, on_order=1)): -26.772053111160577,
 NonTerminal(state=InventoryState(on_hand=5, on_order=0)): -27.772053111160577}

print("True Optimal Policy")
pprint(true_opt_pol)

True Optimal Policy
For State InventoryState(on_hand=0, on_order=0): Do Action 2
For State InventoryState(on_hand=0, on_order=1): Do Action 2
For State InventoryState(on_hand=0, on_order=2): Do Action 1
For State InventoryState(on_hand=0, on_order=3): Do Action 1
For State InventoryState(on_hand=0, on_order=4): Do Action 0
For State InventoryState(on_hand=0, on_order=5): Do Action 0
For State InventoryState(on_hand=1, on_order=0): Do Action 2
For State InventoryState(on_hand=1, on_order=1): Do Action 1
For State InventoryState(on_hand=1, on_order=2): Do Action 1
For State InventoryState(on_hand=1, on_order=3): Do Action 0
For State InventoryState(on_hand=1, on_order=4): Do Action 0
For State InventoryState(on_hand=2, on_order=0): Do Action 1
For State InventoryState(on_hand=2, on_order=1): Do Action 1
For State InventoryState(on_hand=2, on_order=2): Do Action 0
For State InventoryState(on_hand=2, on_order=3): Do Action 0
For State InventoryState(on_hand=3, on_order=0): Do Action 1
For State InventoryState(on_hand=3, on_order=1): Do Action 0
For State InventoryState(on_hand=3, on_order=2): Do Action 0
For State InventoryState(on_hand=4, on_order=0): Do Action 0
For State InventoryState(on_hand=4, on_order=1): Do Action 0
For State InventoryState(on_hand=5, on_order=0): Do Action 0

Now we compare values by state for the State Value Function

[(true_opt_svf[s], opt_svf[s]) for s in si_mdp.non_terminal_states]

[(-26.98163492786722, -26.627145648076866),
 (-19.9909558006178, -19.771390238869504),
 (-18.86849301795165, -18.514480015418165),
 (-19.934022635857023, -18.498951466322506),
 (-20.91848526863397, -21.064211166622616),
 (-22.77205311116058, -23.87449284911821),
 (-20.9909558006178, -20.08614993159479),
 (-19.86849301795165, -19.28700559050116),
 (-20.934022635857026, -20.436319583369052),
 (-21.918485268633972, -22.639086837096524),
 (-23.77205311116058, -24.284458257076704),
 (-20.86849301795165, -20.353379740767895),
 (-21.934022635857023, -21.25757526657738),
 (-22.91848526863397, -22.75024821444209),
 (-24.77205311116058, -24.809513898197483),
 (-22.934022635857026, -22.718947367168315),
 (-23.918485268633972, -23.388534356752288),
 (-25.772053111160584, -26.345027269838162),
 (-24.91848526863397, -24.387050038557934),
 (-26.772053111160577, -25.347216865676412),
 (-27.772053111160577, -29.056513846485817)]

We also compare values by state for the Policy

[(true_opt_pol.policy_map[s.state], opt_pol.policy_map[s.state]) for s in si_mdp.non_terminal_states]

[(Constant(value=2), Constant(value=2)),
 (Constant(value=2), Constant(value=2)),
 (Constant(value=1), Constant(value=1)),
 (Constant(value=1), Constant(value=1)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=2), Constant(value=2)),
 (Constant(value=1), Constant(value=1)),
 (Constant(value=1), Constant(value=1)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=1), Constant(value=1)),
 (Constant(value=1), Constant(value=1)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=1), Constant(value=1)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=0), Constant(value=0)),
 (Constant(value=0), Constant(value=0))]

3.4 Visualize

Let us visualize the convergence of the Action Value Function (Q) for each of the states:

qvfa_lst[1]

Tabular(values_map={(NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 0): -16.66003352275379, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 1): 0.0, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 2): -8.84712186006307, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 3): -3.484852528806128, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 4): -3.0417892530956645, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 5): -3.323154957160499, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 0): -5.436978480160036, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 1): 0.0, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 2): -2.5474975726878393, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 3): -2.8275062369570962, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 4): -4.466077967978892, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 0): 0.0, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 1): -9.695543163249456, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 2): -2.933739288365049, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 3): 0.0, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 0): -5.749167329955894, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 1): -2.8750300064628984, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 2): -3.166028228334391, (NonTerminal(state=InventoryState(on_hand=0, on_order=4)), 0): 0.0, (NonTerminal(state=InventoryState(on_hand=0, on_order=4)), 1): -6.3666719406671, (NonTerminal(state=InventoryState(on_hand=0, on_order=5)), 0): -2.5812832857338877, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 0): -4.707597321874659, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 1): 0.0, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 2): 0.0, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 3): -8.07172866454282, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 4): -3.0339476206022704, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 0): -10.993906420542446, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 1): 0.0, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 2): -2.844003683042871, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 3): -2.7911653293309358, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 0): -6.316763168951876, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 1): 0.0, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 2): 0.0, (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 0): -5.623645309953783, (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 1): -2.4301257768173894, (NonTerminal(state=InventoryState(on_hand=1, on_order=4)), 0): -3.259941800669189, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 0): -12.446739523987436, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 1): -7.468555067559018, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 2): -3.6864546028819642, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 3): -2.716748543151219, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 0): -2.5805663199524878, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 1): -5.029640798466062, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 2): -5.72700024482039, (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 0): -3.5178091425937676, (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 1): -8.58102363687888, (NonTerminal(state=InventoryState(on_hand=2, on_order=3)), 0): 0.0, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 0): -2.8123996539699156, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 1): -9.664140042001613, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 2): -5.957203516680925, (NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 0): -6.901471514837327, (NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 1): -16.37093741815397, (NonTerminal(state=InventoryState(on_hand=3, on_order=2)), 0): -3.76606713446086, (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 0): -8.303203454300261, (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 1): -18.762667910359255, (NonTerminal(state=InventoryState(on_hand=4, on_order=1)), 0): -22.132186839172704, (NonTerminal(state=InventoryState(on_hand=5, on_order=0)), 0): -22.579487794364617}, counts_map={(NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 1): 8, (NonTerminal(state=InventoryState(on_hand=4, on_order=1)), 0): 10, (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 0): 3, (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 1): 9, (NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 0): 3, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 2): 2, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 1): 3, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 1): 2, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 3): 1, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 1): 1, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 0): 4, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 5): 1, (NonTerminal(state=InventoryState(on_hand=0, on_order=5)), 0): 1, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 1): 4, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 3): 1, (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 0): 2, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 0): 4, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 3): 3, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 0): 2, (NonTerminal(state=InventoryState(on_hand=3, on_order=2)), 0): 1, (NonTerminal(state=InventoryState(on_hand=5, on_order=0)), 0): 10, (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 2): 1, (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 0): 1, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 2): 1, (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 0): 2, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 0): 1, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 2): 2, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 4): 1, (NonTerminal(state=InventoryState(on_hand=0, on_order=4)), 1): 2, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 1): 2, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 0): 1, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 0): 4, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 3): 1, (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 4): 1, (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 1): 1, (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 2): 1, (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 4): 1, (NonTerminal(state=InventoryState(on_hand=1, on_order=4)), 0): 1, (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 2): 1, (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 2): 1, (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 1): 3, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 2): 2, (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 0): 1, (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 0): 1, (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 3): 1}, count_to_weight_func=<function learning_rate_schedule.<locals>.lr_func at 0x7ff9e1b4bc20>)

qvfa_lst[1].values_map

{(NonTerminal(state=InventoryState(on_hand=0, on_order=0)),
  0): -16.66003352275379,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 1): 0.0,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)),
  2): -8.84712186006307,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)),
  3): -3.484852528806128,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)),
  4): -3.0417892530956645,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)),
  5): -3.323154957160499,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=1)),
  0): -5.436978480160036,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 1): 0.0,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=1)),
  2): -2.5474975726878393,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=1)),
  3): -2.8275062369570962,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=1)),
  4): -4.466077967978892,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 0): 0.0,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=2)),
  1): -9.695543163249456,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=2)),
  2): -2.933739288365049,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 3): 0.0,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=3)),
  0): -5.749167329955894,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=3)),
  1): -2.8750300064628984,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=3)),
  2): -3.166028228334391,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=4)), 0): 0.0,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=4)),
  1): -6.3666719406671,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=5)),
  0): -2.5812832857338877,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=0)),
  0): -4.707597321874659,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 1): 0.0,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 2): 0.0,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=0)),
  3): -8.07172866454282,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=0)),
  4): -3.0339476206022704,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=1)),
  0): -10.993906420542446,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 1): 0.0,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=1)),
  2): -2.844003683042871,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=1)),
  3): -2.7911653293309358,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=2)),
  0): -6.316763168951876,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 1): 0.0,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 2): 0.0,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=3)),
  0): -5.623645309953783,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=3)),
  1): -2.4301257768173894,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=4)),
  0): -3.259941800669189,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=0)),
  0): -12.446739523987436,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=0)),
  1): -7.468555067559018,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=0)),
  2): -3.6864546028819642,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=0)),
  3): -2.716748543151219,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=1)),
  0): -2.5805663199524878,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=1)),
  1): -5.029640798466062,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=1)),
  2): -5.72700024482039,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=2)),
  0): -3.5178091425937676,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=2)),
  1): -8.58102363687888,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=3)), 0): 0.0,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=0)),
  0): -2.8123996539699156,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=0)),
  1): -9.664140042001613,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=0)),
  2): -5.957203516680925,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=1)),
  0): -6.901471514837327,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=1)),
  1): -16.37093741815397,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=2)),
  0): -3.76606713446086,
 (NonTerminal(state=InventoryState(on_hand=4, on_order=0)),
  0): -8.303203454300261,
 (NonTerminal(state=InventoryState(on_hand=4, on_order=0)),
  1): -18.762667910359255,
 (NonTerminal(state=InventoryState(on_hand=4, on_order=1)),
  0): -22.132186839172704,
 (NonTerminal(state=InventoryState(on_hand=5, on_order=0)),
  0): -22.579487794364617}

qvfa_lst[1].counts_map

{(NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 1): 8,
 (NonTerminal(state=InventoryState(on_hand=4, on_order=1)), 0): 10,
 (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 0): 3,
 (NonTerminal(state=InventoryState(on_hand=4, on_order=0)), 1): 9,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=1)), 0): 3,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 2): 2,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 1): 3,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 1): 2,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 3): 1,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 1): 1,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 0): 4,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 5): 1,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=5)), 0): 1,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 1): 4,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 3): 1,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 0): 2,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 0): 4,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 3): 3,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 0): 2,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=2)), 0): 1,
 (NonTerminal(state=InventoryState(on_hand=5, on_order=0)), 0): 10,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=3)), 2): 1,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 0): 1,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 2): 1,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=2)), 0): 2,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 0): 1,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 2): 2,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 4): 1,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=4)), 1): 2,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 1): 2,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 0): 1,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 0): 4,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 3): 1,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=0)), 4): 1,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=3)), 1): 1,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=1)), 2): 1,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=0)), 4): 1,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=4)), 0): 1,
 (NonTerminal(state=InventoryState(on_hand=1, on_order=1)), 2): 1,
 (NonTerminal(state=InventoryState(on_hand=0, on_order=2)), 2): 1,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=2)), 1): 3,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 2): 2,
 (NonTerminal(state=InventoryState(on_hand=3, on_order=0)), 0): 1,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=1)), 0): 1,
 (NonTerminal(state=InventoryState(on_hand=2, on_order=0)), 3): 1}

3.5 Performance of optimal policy vs other policies

import numpy as np

print('capacity =', capacity)
print('poisson_lambda =', poisson_lambda) 
print('holding_cost =', holding_cost)
print('stockout_cost =', stockout_cost)
print('gamma =', gamma)

capacity = 5
poisson_lambda = 1.0
holding_cost = 1.0
stockout_cost = 10.0
gamma = 0.9

n_steps = 2_000 #number of simulation steps

class SimpleInventoryDeterministicPolicy(DeterministicPolicy[InventoryState, int]):
  def __init__(self, reorder_point: int):
    self.reorder_point: int = reorder_point
    def action_for(s: InventoryState) -> int:
      return max(self.reorder_point - s.inventory_position(), 0)
    super().__init__(action_for)

# 
# start state distribution
ssd = Choose(si_mdp.non_terminal_states)
# ssd

3.5.1 Deterministic Policy with Reorder Point set to Capacity (Maximum Inventory)

$θ = max (r - (α + β), 0)$

where: - $θ \in Z_{\geq 0}$ is the order quantity - $r \in Z_{\geq 0}$ is the reorder point below which reordering is allowed. - $α$ is the on-hand inventory - $β$ is the on-order inventory - $(α, β)$ is the state

We set $r = C$ where $C$ is the inventory capacity for the item.

reorder_point_pol_1 = capacity; reorder_point_pol_1

pol_1 = SimpleInventoryDeterministicPolicy(reorder_point=reorder_point_pol_1); pol_1

SimpleInventoryDeterministicPolicy(action_for=<function SimpleInventoryDeterministicPolicy.__init__.<locals>.action_for at 0x7ff9e1b8e440>)

step_gen = si_mdp.simulate_action(
    start_state_distribution=ssd, 
    policy=pol_1)

step_lst = list(itertools.islice(step_gen, n_steps))
pprint(step_lst[:5])

[TransitionStep(state=NonTerminal(state=InventoryState(on_hand=2, on_order=0)), action=3, next_state=NonTerminal(state=InventoryState(on_hand=1, on_order=3)), reward=-2.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=1, on_order=3)), action=1, next_state=NonTerminal(state=InventoryState(on_hand=4, on_order=1)), reward=-1.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=4, on_order=1)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=2, on_order=0)), reward=-4.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=2, on_order=0)), action=3, next_state=NonTerminal(state=InventoryState(on_hand=2, on_order=3)), reward=-2.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=2, on_order=3)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=3, on_order=0)), reward=-2.0)]

list_of_tuples = [((step.state.state.on_hand,step.state.state.on_order), step.action, (step.next_state.state.on_hand,step.next_state.state.on_order), step.reward) for step in step_lst]
# list_of_tuples

states, actions, next_states, rewards = [list(tup) for tup in zip(*list_of_tuples)]

cum_reward_pol_1 = np.cumsum(rewards)

3.5.2 Deterministic Policy with Reorder Point set to 1 (Minimum Inventory)

$θ = max (r - (α + β), 0)$

We set $r = 1$ .

reorder_point_pol_2 = 1; reorder_point_pol_2

pol_2 = SimpleInventoryDeterministicPolicy(reorder_point=reorder_point_pol_2); pol_2

SimpleInventoryDeterministicPolicy(action_for=<function SimpleInventoryDeterministicPolicy.__init__.<locals>.action_for at 0x7ff9e1b8e680>)

step_gen = si_mdp.simulate_action(
    start_state_distribution=ssd, 
    policy=pol_2)

step_lst = list(itertools.islice(step_gen, n_steps))
pprint(step_lst[:5])

[TransitionStep(state=NonTerminal(state=InventoryState(on_hand=1, on_order=0)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=0, on_order=0)), reward=-4.678794411714423),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=0, on_order=0)), action=1, next_state=NonTerminal(state=InventoryState(on_hand=0, on_order=1)), reward=-10.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=0, on_order=1)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=0, on_order=0)), reward=-3.6787944117144233),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=0, on_order=0)), action=1, next_state=NonTerminal(state=InventoryState(on_hand=0, on_order=1)), reward=-10.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=0, on_order=1)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=0, on_order=0)), reward=-3.6787944117144233)]

list_of_tuples = [((step.state.state.on_hand,step.state.state.on_order), step.action, (step.next_state.state.on_hand,step.next_state.state.on_order), step.reward) for step in step_lst]
# list_of_tuples

states, actions, next_states, rewards = [list(tup) for tup in zip(*list_of_tuples)]

cum_reward_pol_2 = np.cumsum(rewards)

3.5.3 Deterministic Policy with Reorder Point set to Midpoint (Midpoint Inventory)

$θ = max (r - (α + β), 0)$

We set $r = \frac{C}{2}$ .

reorder_point_pol_3 = capacity//2; reorder_point_pol_3

pol_3 = SimpleInventoryDeterministicPolicy(reorder_point=reorder_point_pol_3); pol_3

SimpleInventoryDeterministicPolicy(action_for=<function SimpleInventoryDeterministicPolicy.__init__.<locals>.action_for at 0x7ff9decef4d0>)

step_gen = si_mdp.simulate_action(
    start_state_distribution=ssd, 
    policy=pol_3)

step_lst = list(itertools.islice(step_gen, n_steps))
pprint(step_lst[:5])

[TransitionStep(state=NonTerminal(state=InventoryState(on_hand=4, on_order=1)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=5, on_order=0)), reward=-4.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=5, on_order=0)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=5, on_order=0)), reward=-5.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=5, on_order=0)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=4, on_order=0)), reward=-5.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=4, on_order=0)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=3, on_order=0)), reward=-4.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=3, on_order=0)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=0, on_order=0)), reward=-3.2333692644293284)]

list_of_tuples = [((step.state.state.on_hand,step.state.state.on_order), step.action, (step.next_state.state.on_hand,step.next_state.state.on_order), step.reward) for step in step_lst]
# list_of_tuples

states, actions, next_states, rewards = [list(tup) for tup in zip(*list_of_tuples)]

cum_reward_pol_3 = np.cumsum(rewards)

3.5.4 Optimal Policy (Monte-Carlo)

print(f"GLIE MC Optimal Policy with {n_episodes:d} episodes")
pprint(opt_pol)

GLIE MC Optimal Policy with 10000 episodes
For State InventoryState(on_hand=0, on_order=0): Do Action 2
For State InventoryState(on_hand=0, on_order=1): Do Action 2
For State InventoryState(on_hand=0, on_order=2): Do Action 1
For State InventoryState(on_hand=0, on_order=3): Do Action 1
For State InventoryState(on_hand=0, on_order=4): Do Action 0
For State InventoryState(on_hand=0, on_order=5): Do Action 0
For State InventoryState(on_hand=1, on_order=0): Do Action 2
For State InventoryState(on_hand=1, on_order=1): Do Action 1
For State InventoryState(on_hand=1, on_order=2): Do Action 1
For State InventoryState(on_hand=1, on_order=3): Do Action 0
For State InventoryState(on_hand=1, on_order=4): Do Action 0
For State InventoryState(on_hand=2, on_order=0): Do Action 1
For State InventoryState(on_hand=2, on_order=1): Do Action 1
For State InventoryState(on_hand=2, on_order=2): Do Action 0
For State InventoryState(on_hand=2, on_order=3): Do Action 0
For State InventoryState(on_hand=3, on_order=0): Do Action 1
For State InventoryState(on_hand=3, on_order=1): Do Action 0
For State InventoryState(on_hand=3, on_order=2): Do Action 0
For State InventoryState(on_hand=4, on_order=0): Do Action 0
For State InventoryState(on_hand=4, on_order=1): Do Action 0
For State InventoryState(on_hand=5, on_order=0): Do Action 0

type(opt_pol)

rl.policy_ANNO.FiniteDeterministicPolicy

step_gen = si_mdp.simulate_action(
    start_state_distribution=ssd, 
    policy=opt_pol)

step_lst = list(itertools.islice(step_gen, n_steps))
pprint(step_lst[:5])

[TransitionStep(state=NonTerminal(state=InventoryState(on_hand=1, on_order=4)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=3, on_order=0)), reward=-1.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=3, on_order=0)), action=1, next_state=NonTerminal(state=InventoryState(on_hand=3, on_order=1)), reward=-3.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=3, on_order=1)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=4, on_order=0)), reward=-3.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=4, on_order=0)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=4, on_order=0)), reward=-4.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=4, on_order=0)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=2, on_order=0)), reward=-4.0)]

list_of_tuples = [((step.state.state.on_hand,step.state.state.on_order), step.action, (step.next_state.state.on_hand,step.next_state.state.on_order), step.reward) for step in step_lst]
# list_of_tuples

states, actions, next_states, rewards = [list(tup) for tup in zip(*list_of_tuples)]

cum_reward_pol_opt = np.cumsum(rewards)

3.5.5 True Optimal Policy

print(f"GLIE MC True Optimal Policy with {n_episodes:d} episodes")
pprint(true_opt_pol)

GLIE MC True Optimal Policy with 10000 episodes
For State InventoryState(on_hand=0, on_order=0): Do Action 2
For State InventoryState(on_hand=0, on_order=1): Do Action 2
For State InventoryState(on_hand=0, on_order=2): Do Action 1
For State InventoryState(on_hand=0, on_order=3): Do Action 1
For State InventoryState(on_hand=0, on_order=4): Do Action 0
For State InventoryState(on_hand=0, on_order=5): Do Action 0
For State InventoryState(on_hand=1, on_order=0): Do Action 2
For State InventoryState(on_hand=1, on_order=1): Do Action 1
For State InventoryState(on_hand=1, on_order=2): Do Action 1
For State InventoryState(on_hand=1, on_order=3): Do Action 0
For State InventoryState(on_hand=1, on_order=4): Do Action 0
For State InventoryState(on_hand=2, on_order=0): Do Action 1
For State InventoryState(on_hand=2, on_order=1): Do Action 1
For State InventoryState(on_hand=2, on_order=2): Do Action 0
For State InventoryState(on_hand=2, on_order=3): Do Action 0
For State InventoryState(on_hand=3, on_order=0): Do Action 1
For State InventoryState(on_hand=3, on_order=1): Do Action 0
For State InventoryState(on_hand=3, on_order=2): Do Action 0
For State InventoryState(on_hand=4, on_order=0): Do Action 0
For State InventoryState(on_hand=4, on_order=1): Do Action 0
For State InventoryState(on_hand=5, on_order=0): Do Action 0

type(true_opt_pol)

rl.policy_ANNO.FiniteDeterministicPolicy

step_gen = si_mdp.simulate_action(
    start_state_distribution=ssd, 
    policy=true_opt_pol)

step_lst = list(itertools.islice(step_gen, n_steps))
pprint(step_lst[:5])

[TransitionStep(state=NonTerminal(state=InventoryState(on_hand=0, on_order=4)), action=0, next_state=NonTerminal(state=InventoryState(on_hand=2, on_order=0)), reward=-0.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=2, on_order=0)), action=1, next_state=NonTerminal(state=InventoryState(on_hand=2, on_order=1)), reward=-2.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=2, on_order=1)), action=1, next_state=NonTerminal(state=InventoryState(on_hand=0, on_order=1)), reward=-2.2333692644293284),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=0, on_order=1)), action=2, next_state=NonTerminal(state=InventoryState(on_hand=1, on_order=2)), reward=-0.0),
 TransitionStep(state=NonTerminal(state=InventoryState(on_hand=1, on_order=2)), action=1, next_state=NonTerminal(state=InventoryState(on_hand=1, on_order=1)), reward=-1.0)]

list_of_tuples = [((step.state.state.on_hand,step.state.state.on_order), step.action, (step.next_state.state.on_hand,step.next_state.state.on_order), step.reward) for step in step_lst]
# list_of_tuples

states, actions, next_states, rewards = [list(tup) for tup in zip(*list_of_tuples)]

cum_reward_pol_opt_true = np.cumsum(rewards)

3.5.6 Visualization

import matplotlib.pyplot as plt
label_list = ['Max Inventory', 'Min Inventory', 'Midpoint Inventory', 'Optimal (MC)', 'True Optimal']
plot_list = [cum_reward_pol_1, cum_reward_pol_2, cum_reward_pol_3, cum_reward_pol_opt, cum_reward_pol_opt_true]

fig,axs = plt.subplots(figsize=(16,15))
axs.set_xlabel('Steps', fontsize=20)
axs.set_title(f'Cumulative Reward', fontsize=24)
for i,cum_r in enumerate(plot_list):
  axs.plot(cum_r, label=label_list[i])
# axs.set_ylim([-5000,0])
axs.legend(fontsize=15);

fig,axs = plt.subplots(figsize=(16,15))
axs.set_xlabel('Steps', fontsize=20)
axs.set_title(f'Cumulative Cost', fontsize=24)
for i,cum_r in enumerate(plot_list):
  axs.plot(-cum_r, label=label_list[i])
# axs.set_ylim([0, 5000])
axs.legend(fontsize=15);

Now we zoom in a bit:

fig,axs = plt.subplots(figsize=(16,15))
axs.set_xlabel('Steps', fontsize=20)
axs.set_title(f'Cumulative Reward', fontsize=24)
for i,cum_r in enumerate(plot_list):
  axs.plot(cum_r, label=label_list[i])
axs.set_ylim([-3000,0])
axs.legend(fontsize=15);

fig,axs = plt.subplots(figsize=(16,15))
axs.set_xlabel('Steps', fontsize=20)
axs.set_title(f'Cumulative Cost', fontsize=24)
for i,cum_r in enumerate(plot_list):
  axs.plot(-cum_r, label=label_list[i])
axs.set_ylim([0, 3000])
axs.legend(fontsize=15);

1 Generalized Policy Iteration (GPI)

2 GPI with Evaluation as Monte-Carlo (MC)

2.1 Greedy Policy Improvement requires P and R

2.2 Biased initial random occurrences of returns

3 Monte-Carlo (MC) Control

3.1 TAB MC Control

3.2 FAP MC Control

3.3 Generalized implementation of GLIE Monte-Carlo Control

3.4 Visualize

3.5 Performance of optimal policy vs other policies

3.5.1 Deterministic Policy with Reorder Point set to Capacity (Maximum Inventory)

3.5.2 Deterministic Policy with Reorder Point set to 1 (Minimum Inventory)

3.5.3 Deterministic Policy with Reorder Point set to Midpoint (Midpoint Inventory)

3.5.4 Optimal Policy (Monte-Carlo)

3.5.5 True Optimal Policy

3.5.6 Visualization

2.1 Greedy Policy Improvement requires $P$ and $R$