A Modified Value Iteration Algorithm for Discounted Markov Decision Processes

2.1. Definition

We consider a stochastic dynamic system which is observed at discrete time points t = 1, 2,... . An MDP (Puterman, 2009) is defined by , where:

• •

  S={1, 2, ..., M} is the set of states of the environment (the state space), let is a random variable which represent the state of the system at time t whose values are in the state space S;

• •

  A is the set of actions (the action space);

• •

  T is the transition function (the probability of transitioning to state s’ when action a is executed in state s), where:

• •

  is the reward function (the immediate utility of executing the action a in state s), where: R: S × A → ℜ

A strategy is defined by a sequence where is a decision rule, that is a function where the set of all histories up to time t, and the set of probability distributions over . A Markov strategy is a strategy in which depends only on the current state at time t, a stationary strategy is a Markov strategy with identical decision rules, and a deterministic or pure strategy is a stationary strategy whose single decision rule is nonrandomized. In the following, we will assume the process stationary. For there to exist an optimal policy, there must exist an optimality criterion that places some kind of ordering on different policies.