Markov Decision Processes

# A Markov decision process written out in full: the five parts, the transition
# model checked, and three fixed policies EVALUATED so that the difference
# between judging a policy and finding one is visible.
COLS, ROWS = 4, 3
WALL = (1, 1)
TERMINAL = {(3, 2): 1.0, (3, 1): -1.0}
START = (0, 0)
LIVING = -0.04          # the reward for being in any non-terminal square
GAMMA = 1.0
ACTIONS = ["N", "S", "E", "W"]
MOVE = {"N": (0, 1), "S": (0, -1), "E": (1, 0), "W": (-1, 0)}
# A slip sends the agent at right angles to the way it meant to go.
SIDEWAYS = {"N": ("W", "E"), "S": ("E", "W"), "E": ("N", "S"), "W": ("S", "N")}
P_INTENDED, P_SLIP = 0.8, 0.1

STATES = [(c, r) for r in range(ROWS) for c in range(COLS) if (c, r) != WALL]

def legal(s):
    c, r = s
    return 0 <= c < COLS and 0 <= r < ROWS and (c, r) != WALL

def move(s, a):
    """Walking into a wall or off the edge leaves the agent where it was."""
    d = MOVE[a]
    t = (s[0] + d[0], s[1] + d[1])
    return t if legal(t) else s

def transitions(s, a):
    """P(s' | s, a) as a list of (probability, next state)."""
    left, right = SIDEWAYS[a]
    out = {}
    for p, act in ((P_INTENDED, a), (P_SLIP, left), (P_SLIP, right)):
        t = move(s, act)
        out[t] = out.get(t, 0.0) + p
    return [(p, t) for t, p in sorted(out.items())]

def reward(s):
    return TERMINAL[s] if s in TERMINAL else LIVING

def draw(grid, fmt="%6s"):
    for r in range(ROWS - 1, -1, -1):
        line = "   "
        for c in range(COLS):
            line += fmt % ("#" if (c, r) == WALL else grid.get((c, r), "."))
        print(line.rstrip())

print("A MARKOV DECISION PROCESS HAS FIVE PARTS.")
print("   S      the set of states")
print("   A      the set of actions")
print("   P      the transition model, P(s' | s, a)")
print("   R      the reward")
print("   gamma  the discount factor")
print()
print("THE GRID. the robot starts at the bottom left and is trying to reach the")
print("+1 square. # is a pillar it cannot enter.")
labels = {t: "%+.0f" % v for t, v in TERMINAL.items()}
labels[START] = "start"
draw(labels)
print()
print("   S: %d squares, two of them terminal." % len(STATES))
print("   A: %s. gamma = %.2f. reward %.2f in every non-terminal square,"
      % (", ".join(ACTIONS), GAMMA, LIVING))
print("      %+.0f and %+.0f in the two terminal ones."
      % (TERMINAL[(3, 2)], TERMINAL[(3, 1)]))
print()
print("   P: THE FLOOR IS SLIPPERY. an action goes the intended way with")
print("      probability %.1f and at right angles with probability %.1f each."
      % (P_INTENDED, P_SLIP))
print("      walking into the pillar or off the edge leaves the robot where it was.")
print()
print("   one state and action written out in full, from %s going N:" % str((0, 0)))
for p, t in transitions((0, 0), "N"):
    why = "intended" if t == (0, 1) else ("blocked, stays put" if t == (0, 0) else "slipped")
    print("      P(%s | %s, N) = %.1f   (%s)" % (str(t), str((0, 0)), p, why))
print("   and from %s going N, where the pillar is above:" % str((1, 0)))
for p, t in transitions((1, 0), "N"):
    why = "blocked by the pillar, stays put" if t == (1, 0) else "slipped"
    print("      P(%s | %s, N) = %.1f   (%s)" % (str(t), str((1, 0)), p, why))
print()
bad = 0
for s in STATES:
    if s in TERMINAL:
        continue
    for a in ACTIONS:
        tot = sum(p for p, _ in transitions(s, a))
        if abs(tot - 1.0) > 1e-12:
            bad += 1
print("   CHECKED: for all %d non-terminal states and %d actions the transition"
      % (len(STATES) - len(TERMINAL), len(ACTIONS)))
print("   probabilities sum to 1. violations: %d." % bad)
print()

print("THE MARKOV PROPERTY, which is what the M stands for.")
print("   P(s' | s, a) depends on the CURRENT state and action only. how the")
print("   robot reached (2,1) does not change what happens next from (2,1).")
print("   THAT IS AN ASSUMPTION ABOUT THE PROBLEM, and it is what lets a policy")
print("   be a function of the state alone rather than of the whole history.")
print()
print("A POLICY maps each state to an action. for an MDP with a fixed discount")
print("an optimal policy can always be taken to be")
print("   DETERMINISTIC: no need to randomise, since one action is at least as")
print("      good as any mixture of actions.")
print("   STATIONARY: the same in a state whenever it is visited, since the")
print("      future from a state does not depend on the time of arrival.")
print("   so the search is over %d**%d = %d policies, which is finite and far"
      % (len(ACTIONS), len(STATES) - len(TERMINAL),
         len(ACTIONS) ** (len(STATES) - len(TERMINAL))))
print("   too many to try one at a time.")
print()

def evaluate(policy, tol=1e-10):
    """POLICY EVALUATION: the value of every state UNDER A GIVEN POLICY.
    V(s) = R(s) + gamma * sum over s' of P(s' | s, policy(s)) * V(s')"""
    V = {s: 0.0 for s in STATES}
    for s in TERMINAL:
        V[s] = TERMINAL[s]
    sweeps = 0
    while True:
        sweeps += 1
        delta = 0.0
        for s in STATES:
            if s in TERMINAL:
                continue
            total = sum(p * V[t] for p, t in transitions(s, policy[s]))
            new = reward(s) + GAMMA * total
            delta = max(delta, abs(new - V[s]))
            V[s] = new
        if delta < tol:
            return V, sweeps

def show_policy(policy):
    g = dict(policy)
    for t, v in TERMINAL.items():
        g[t] = "%+.0f" % v
    draw(g)

print("EVALUATING A FIXED POLICY. this is the PREDICTION problem: not 'what")
print("should the robot do' but 'how good is this particular rule'.")
print()
POLICIES = {
    "always north": {s: "N" for s in STATES if s not in TERMINAL},
    "always east": {s: "E" for s in STATES if s not in TERMINAL},
    "along the bottom and up the right hand side": {
        (0, 0): "E", (1, 0): "E", (2, 0): "E", (3, 0): "N",
        (0, 1): "N", (2, 1): "N",
        (0, 2): "E", (1, 2): "E", (2, 2): "E"},
    "up the left hand side and along the top": {
        (0, 0): "N", (1, 0): "E", (2, 0): "N", (3, 0): "W",
        (0, 1): "N", (2, 1): "N",
        (0, 2): "E", (1, 2): "E", (2, 2): "E"},
}
for name, pol in POLICIES.items():
    V, sweeps = evaluate(pol)
    print("   %s" % name.upper())
    show_policy(pol)
    print("   its values:")
    draw({s: "%+.3f" % V[s] for s in STATES}, fmt="%9s")
    print("   value of the start square: %+.4f, after %d sweeps."
          % (V[START], sweeps))
    print()

print("READ THE FOUR START VALUES TOGETHER:")
for name, pol in POLICIES.items():
    V, _ = evaluate(pol)
    print("   %+.4f   %s" % (V[START], name))
print()
v_north = evaluate(POLICIES["always north"])[0][START]
v_right = evaluate(POLICIES["along the bottom and up the right hand side"])[0][START]
v_top = evaluate(POLICIES["up the left hand side and along the top"])[0][START]
print("   'always north' is worth %+.4f: the robot presses into the top wall and"
      % v_north)
print("   reaches the goal only by slipping sideways along the top row.")
print("   'always east' is worth %+.4f, because from the bottom right corner it"
      % evaluate(POLICIES["always east"])[0][START])
print("   presses east into the edge and slips into the -1 square.")
print()
print("   AND THE TWO ROUTES THAT LOOK SENSIBLE ON THE MAP ARE %+.4f APART."
      % (v_top - v_right))
print("   going right along the bottom and up the right hand side is the SHORTER")
print("   route, and it is worth %+.4f, because the only way up the right hand" % v_right)
print("   column passes through the -1 square. going up the left and along the")
print("   top is longer, costs more steps at %.2f each, and is worth %+.4f."
      % (LIVING, v_top))
print("   THE SHORT ROUTE ON THE MAP IS THE BAD POLICY, and no amount of looking")
print("   at the grid says so. only the evaluation does.")
print()
print("NOTICE WHAT EVALUATION DOES NOT DO. it scores a policy that was handed to")
print("it; it never proposes one. finding the best policy is the CONTROL problem")
print("and it needs the next chapter's equations.")