disc08-regular-sols

2 Q-learning Consider the following gridworld (rewards shown on left, state names shown on right). Rewards State names From state A, the possible actions are right( → ) and down( ↓ ). From state B, the possible actions are left( ← ) and down( ↓ ). For a numbered state (G1, G2), the only action is to exit. Upon exiting from a numbered square we collect the reward specified by the number on the square and enter the end-of-game absorbing state X . We also know that the discount factor γ = 1, and in this MDP all actions are deterministic and always succeed. Consider the following episodes: Episode 1 ( E 1 ) s a s ′ r A ↓ G 1 0 G 1 exit X 10 Episode 2 ( E 2 ) s a s ′ r B ↓ G 2 0 G 2 exit X 1 Episode 3 ( E 3 ) s a s ′ r A → B 0 B ↓ G 2 0 G 2 exit X 1 Episode 4 ( E 4 ) s a s ′ r B ← A 0 A ↓ G 1 0 G 1 exit X 10 (a) Consider using temporal-difference learning to learn V ( s ). When running TD-learning, all values are ini- tialized to zero. For which sequences of episodes, if repeated infinitely often, does V ( s ) converge to V ∗ ( s ) for all states s ? (Assume appropriate learning rates such that all values converge.) Write the correct sequence under “Other” if no correct sequences of episodes are listed. □ E 1 , E 2 , E 3 , E 4 □ E 1 , E 2 , E 1 , E 2 □ E 1 , E 2 , E 3 , E 1 ■ E 4 , E 4 , E 4 , E 4 □ E 4 , E 3 , E 2 , E 1 □ E 3 , E 4 , E 3 , E 4 □ E 1 , E 2 , E 4 , E 1 ■ Other See explanation below TD learning learns the value of the executed policy, which is V π ( s ). Therefore for V π ( s ) to converge to V ∗ ( s ), it is necessary that the executing policy π ( s ) = π ∗ ( s ). Because there is no discounting since γ = 1, the optimal deterministic policy is π ∗ ( A ) = ↓ and π ∗ ( B ) = ← ( π ∗ ( G 1) and π ∗ ( G 2) are trivially exit because that is the only available action). Therefore episodes E 1 and E 4 act according to π ∗ ( s ) while episodes E 2 and E 3 are sampled from a suboptimal policy. From the above, TD learning using episode E 4 (and optionally E 1) will converge to V π ( s ) = V ∗ ( s ) for states A , B , G 1. However, then we never visit G 2, so V ( G 2) will never converge. If we add either episode E 2 or E 3 to ensure that V ( G 2) converges, then we are executing a suboptimal policy, which will then cause V ( B ) to not converge. Therefore none of the listed sequences will learn a value function V π ( s ) that converges to V ∗ ( s ) for all states s . An example of a correct sequence would be E 2 , E 4 , E 4 , E 4 , ... ; sampling 3