Value iteration needs a known model — what exactly must that model give you?
answer
- dynamics, not a dataset
- probability of every successor state
- expected reward per transition
- the update is an expectation
- planning inside a model
basics
~20 sFor every state and action, the model must give the probability of each possible next state and the expected reward. Value iteration averages over all successors in every update, so it plans inside the model rather than learning from experience.
solid answer
~40 sValue iteration is a planning method: it needs the MDP's dynamics written down. Concretely, for each state `s` and action `a` you need `P(s'|s,a)` for every successor `s'`, plus the expected reward of that transition. Every update is a full-width backup, `v(s) <- max_a sum_s' P(s'|s,a) * [r(s,a,s') + gamma * v(s')]`, which sums over the whole successor distribution rather than over anything that happened. That is why a restocking problem is a natural fit: if demand follows a known distribution and your ordering rules are fixed, you can enumerate every next inventory level and its probability, so you can solve for the optimal ordering policy before ever touching the warehouse. Without those numbers there is nothing to sum over, and a different family of methods is needed.
go deeper
Be ready to say that value iteration needs the transition probabilities and expected rewards for every state and action, and that this is why it is called planning rather than learning.
Explain the full-width backup out loud: for each action you sum over every successor weighted by its probability, then take the best action. Say why no distribution means no expectation to compute.
Show where a usable model comes from in a real problem, such as a fitted demand or failure distribution, and note that a sweep costs roughly the number of states times actions times successors, which bounds what you can solve exactly.
Own the framing decision: whether a problem should be posed as a planning problem with a written-down model at all, what it costs the organisation to build and maintain that model, and what is gained over simpler decision rules.
## What "a model" means here A Markov decision process is the tuple: a set of states `S`, a set of actions `A`, transition dynamics `P(s'|s,a)`, a reward function, and a discount factor `gamma`. The **model** is the pair that describes the environment's behaviour: the transition probabilities and the rewards. Knowing the model means that, sitting at your desk with no environment running, you can answer the question *"if I am in state `s` and take action `a`, what is the full probability distribution over where I end up, and what reward do I expect?"* That is a stronger requirement than it first sounds. It is not enough to know one likely outcome; you need the whole distribution, because the algorithm's arithmetic is an expectation over it. ## Why value iteration cannot run without it One value-iteration update of a single state is ``` v_new(s) = max over a of sum over s' of P(s'|s,a) * [ r(s,a,s') + gamma * v_old(s') ] ``` Read that literally. To compute the value of one action you must enumerate every successor state, weight it by its probability, add the reward you expect on the way, and add the discounted value you already hold for that successor. This is called a **full-width backup**: it touches all branches of the one-step tree, not a sampled branch. Then you take the maximum over actions, because you get to choose. If you do not have `P`, there is no distribution to sum over and no expectation to take. This is the precise sense in which value iteration is *planning*: all of the computation happens inside a model you already possess, and the environment is never touched. Nothing is estimated from interaction; the only thing being computed is the consequence of arithmetic you could in principle do by hand. ## Where a known model actually comes from Candidates sometimes treat "known model" as a fantasy. In practice it is common: - **Operations problems built on a fitted demand or arrival distribution.** An inventory-restocking MDP whose state is stock on hand and whose demand each period follows a known distribution has fully enumerable dynamics: for each order quantity you can compute the probability of each next stock level. - **Engineered systems with reliability data.** A machine that fails with a tabulated probability per period gives you `P` directly. - **Rule-governed systems.** Board games, scheduling problems, and routing on a known network have dynamics that are simply the rules. In each case the model may itself be estimated from data, but once it is written down it is *treated as known* and the planning step is exact arithmetic against it. ## Consequences worth knowing **The state space must be enumerable.** A sweep touches every state, and each state's update touches every action and every successor. For a dense model that is on the order of `|S| * |A| * |S|` operations per sweep. If states are counted in the billions, exact sweeps are out even with a perfect model. **Initial values do not matter much.** You typically start `v(s) = 0` everywhere. The updates contract towards the optimal values regardless of the starting guess (terminal states are pinned at zero). **Optimality is relative to the model.** Value iteration returns the exactly optimal policy for the numbers you fed it. If `P` is wrong, the policy is optimal for a world that does not exist — an important caveat whenever the model came from estimates. **Asynchronous updates are allowed.** The classic sweep updates every state from the previous iteration's values, but you may update states in any order, in place, as long as every state keeps being revisited. This is often much faster in practice and does not change what the method needs to know. ## The short version to say out loud "I need `P(s'|s,a)` and the expected reward for every state–action pair, because each update is an expectation over the entire successor distribution. That is what makes it planning rather than learning — the environment is never queried; I am doing arithmetic inside a model I already have."
- Where do the transition probabilities in a planning problem usually come from?From the structure of the problem rather than from trial and error: a fitted demand distribution in an inventory problem, failure rates from reliability tables for a maintenance problem, the published rules of a game, or a physical or queueing model. They are often estimated from historical records once and then treated as fixed inputs to the planner.
- Does value iteration have to update states in a fixed order?No. The textbook sweep is synchronous — every state is updated from the previous iteration's values — but asynchronous variants update states one at a time, in place, in any order. They still converge to the same optimal values provided every state continues to be updated, and choosing a good order often converges much faster.
- What limits how large a problem you can plan over exactly?The state space, because each sweep touches every state and every state's update touches every action and successor. Roughly `|S| * |A| * |S|` operations per sweep for dense dynamics. Beyond a few million states you need aggregation, structure in the model, or restricting attention to states reachable from the start.
It is the difference between reading the full rulebook of a board game and working out the best move at the table, versus having only a pile of scoresheets from games other people played.
saying these in an interview costs you the question
- Says value iteration learns the policy from collected episodes
- Thinks knowing only the reward function is enough
- Treats the model as one next state instead of a distribution
- Assumes the model must be exactly true rather than assumed known