Solve an MDP with uncertain moves to convergence.
What to build
A program that finds the optimal values and policy of a grid world where moves can slip.
Requirements
- Cells:
.open,#wall,Gterminal with value +1,Pterminal with value −1. From an open cell, an action goes the intended way with probability 0.8 and to each perpendicular side with probability 0.1; into a wall or off the grid, the agent stays. V(s) = r + γ × maxₐ Σ P(s′ | s, a) V(s′), with living reward r. - Run value iteration from 0 until the largest change is below 1e-9. Print the values grid (two decimal places;
#,G,Pas themselves), then the policy grid with^ > v <(ties: N, E, S, W order).
Input
Line 1: rows, columns, r and γ. Then the grid.
Output
The values rows, then the policy rows.
Constraints
At most 8 × 8 cells; γ ≤ 1 and every cell can reach a terminal.
Example
Input:
3 3 -0.04 1
..G
.#P
...
Output:
0.89 0.95 G
0.84 # P
0.79 0.74 0.50
> > G
^ # P
^ < <
Why it works
The values are the unique solution of the Bellman equations, and value iteration approaches it; acting greedily on the final values chooses moves whose likely slips are also safe.
Examples
3 3 -0.04 1 ..G .#P ...
0.89 0.95 G 0.84 # P 0.79 0.74 0.50 > > G ^ # P ^ < <
1 3 -0.1 0.9 ..G
0.54 0.76 G > > G
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A move goes the intended way with probability 0.8 and to each side with 0.1; compute the expected next value for each of the four actions.
Hint 2
Keep iterating until the largest change in a whole pass is below 1e-9, then take the best action in each cell.
Solution
Show one correct solution (try it yourself first)
rows, cols, living, gamma = input().split()
rows, cols, living, gamma = int(rows), int(cols), float(living), float(gamma)
grid = [input() for _ in range(rows)]
MOVES = {"^": (-1, 0), ">": (0, 1), "v": (1, 0), "<": (0, -1)}
SIDES = {"^": "><", "v": "><", ">": "^v", "<": "^v"}
V = {}
for r in range(rows):
for c in range(cols):
if grid[r][c] != "#":
V[(r, c)] = {"G": 1.0, "P": -1.0}.get(grid[r][c], 0.0)
def step(cell, d):
r, c = cell[0] + MOVES[d][0], cell[1] + MOVES[d][1]
return (r, c) if 0 <= r < rows and 0 <= c < cols and grid[r][c] != "#" else cell
def q(values, cell, d):
a, b = SIDES[d]
return living + gamma * (0.8 * values[step(cell, d)] + 0.1 * values[step(cell, a)] + 0.1 * values[step(cell, b)])
open_cells = [cell for cell in V if grid[cell[0]][cell[1]] == "."]
while True:
new = dict(V)
for cell in open_cells:
new[cell] = max(q(V, cell, d) for d in MOVES)
change = max((abs(new[cell] - V[cell]) for cell in open_cells), default=0)
V = new
if change < 1e-9:
break
for r in range(rows):
print(" ".join(f"{V[(r, c)]:.2f}" if grid[r][c] == "." else grid[r][c] for c in range(cols)))
for r in range(rows):
line = []
for c in range(cols):
if grid[r][c] != ".":
line.append(grid[r][c])
continue
best = None
for d in MOVES:
if best is None or q(V, (r, c), d) > q(V, (r, c), best):
best = d
line.append(best)
print(" ".join(line))