A warehouse robot records every move it makes as a transition (state, action, reward, next_state, done): where it was, what it did, the reward it got, where it ended up, and whether the task was finished. Learn action values from this diary without moving the robot again.
Write q_from_log(log, actions, alpha, gamma, passes) that returns the table Q as a dictionary {state: [value of actions[0], value of actions[1], ...]} with an entry for every state that appears in the log (as state or as next_state). All values start at 0.0. Go through the log passes times, in order, and for every transition update
target = reward if done
target = reward + gamma · max(Q[next_state]) otherwise
Q[state][a] ← Q[state][a] + alpha · (target - Q[state][a]) (a = the index of the action)
using the table as it is at that moment (earlier updates in the same pass count).
Examples
Input: log = [("dock", "fwd", -1, "aisle", False), ("aisle", "fwd", -1, "shelf", False),
("shelf", "grab", 10, "done", True)],
actions = ["fwd", "back", "grab"], alpha = 0.5, gamma = 0.9, passes = 1
Output: {"dock": [-0.5, 0.0, 0.0], "aisle": [-0.5, 0.0, 0.0], "shelf": [0.0, 0.0, 5.0], "done": [0.0, 0.0, 0.0]}
Explanation: in the first pass the reward has only reached "shelf"; the moves before it only saw the -1 steps.
Input: the same log and settings, passes = 2
Output: {"dock": [-0.75, 0.0, 0.0], "aisle": [1.5, 0.0, 0.0], "shelf": [0.0, 0.0, 7.5], "done": [0.0, 0.0, 0.0]}
Explanation: "aisle" now sees 0.9 · 5 = 4.5 from "shelf": target 3.5, value -0.5 + 0.5 · 4 = 1.5.
"dock" still sees the best value of "aisle" before that update, max(-0.5, 0, 0) = 0.
Constraints
0 <= len(log) <= 5000, 1 to 8 actions,0 < alpha <= 1,0 <= gamma <= 1,0 <= passes <= 200- every action in the log is in
actions - floats are compared with a tolerance of
1e-6
Goals
- Apply the Q-learning update to recorded transitions
- Use the best value of the next state as the target, and only the reward when the episode ended
- Watch values flow backwards from the reward over repeated passes