Markov Decision Processes: States, Actions and Return · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Writing a choice problem down

Computing · Machine Learning · ages 22-24
Name ______________________   Date ____________

  1. A robot chooses Move or Wait. After Move, it receives a score of -2. Which MDP part is that score?

    • The action selected before the robot moves
    • The reward received after the robot acts
    • The state describing where the robot waits

  2. Under the Markov assumption, the same current state and action may have different next-state distributions solely because earlier histories differ.

    Circle one:   True   False

  3. What is the return along one trajectory in a discounted MDP?

    • A discounted sum of rewards on that trajectory
    • A probability distribution over the next states
    • A list of actions chosen on a single trajectory

  4. A Markov model can produce different next states on repeated visits to the same state with the same action.

    Circle one:   True   False

  5. An episode gives rewards 5, 4 and 8 in that order, then ends. With discount gamma = 0.5, what is the return starting before the first reward?

    Answer: ______________

  6. For a fixed reward sequence and 0 <= gamma < 1, what changes when the discount gamma is made smaller?

    • The process stops after a fixed number of actions
    • The weights on later rewards decay more quickly
    • The probabilities of later transitions become zero

  7. For one fixed state and action, Base and Field are the only possible next states. Which proposed transition row is valid?

    • 0.4 to Base; 0.6 to Field
    • 0.4 to Base; 0.4 to Field
    • 0.6 to Base; 0.6 to Field
    • 0.7 to Base; 0.6 to Field

  8. A drone is at Base. With Fly, its next state is Field with probability 0.65 and Base with probability 0.35. With Hold, Field has probability 0.15. The drone chooses Fly. What is the probability its next state is Field?

    • 0.15
    • 0.35
    • 0.65

  9. Weather depends only on the last two days. Tomorrow's rain probability is 0.7 after Rainy then Rainy, but 0.2 after Sunny then Rainy. A state records today only. Which repair captures the rule?

    • Record yesterday and today as the current state
    • Replace both rain probabilities with their average
    • Change the discount until both histories have equal value

  10. A robot's state records only its location. At a door, Open succeeds if the robot holds a badge and fails otherwise. The robot may have collected a badge earlier. What is the defect in this state representation?

    • Open's success probability must be identical at every location
    • The robot must discard its collected badge before choosing Open
    • Badge history changes Open's conditional success probability
LightMySky · lightmysky.comW1-mt_bTCO27sgc6-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Writing a choice problem down W1-mt_bTCO27sgc6-s1

  1. The reward received after the robot acts · The score received after an action is its reward, even when negative. Move is the action; the robot's situation is its state.
  2. False · The current state and action must determine the same outcome distribution regardless of earlier history. Sampled outcomes can still differ.
  3. A discounted sum of rewards on that trajectory · Return adds a trajectory's rewards after applying their discount weights. Expected return averages returns over possible trajectories.
  4. True · The Markov assumption fixes conditional probabilities, not the sampled outcome. Random transitions can produce different next states.
  5. 9 · The weights are 1, 0.5 and 0.25. The return is 5 + 0.5 * 4 + 0.25 * 8 = 9.
  6. The weights on later rewards decay more quickly · Later rewards have weights gamma, gamma squared and so on. Smaller gamma reduces those weights faster without changing transition probabilities or imposing a stopping time.
  7. 0.4 to Base; 0.6 to Field · A transition row must contain nonnegative probabilities summing to 1. Only 0.4 + 0.6 meets that requirement.
  8. 0.65 · Use the transition rule for the current state Base and chosen action Fly. Its probability of Field is 0.65.
  9. Record yesterday and today as the current state · The pair of days distinguishes the two histories and contains all the memory this rule needs. Changing probabilities or discount does not repair the state.
  10. Badge history changes Open's conditional success probability · At the same door under Open, success has probability 1 with a badge and 0 without one. Earlier badge collection changes this conditional distribution because the recorded state omits badge status. Different samples from one fixed distribution would not establish this defect.
Worksheet · LightMySky