6
$\begingroup$

One of the primary differences I've seen stated between Q-learning, as a model-free algorithm, and Value Iteration, as a model-based algorithm is that Value-Iteration requires a "model of the environment" in that it incorporates knowledge of how to transition from one state to another (which I've understood as a policy over actions), and knowledge of the rewards received at each state. I've also seen it stated that

"Value iteration works fine, but it has two weaknesses: first, it can take a long time to converge in some situations, even when the underlying policy is not changing"

Which has left me quite confused.

While I can see that it needs a given set of transition probabilities, I don't see anything in its update equation as to why it requires knowledge of rewards before hand and why it cannot be trained in an online way in the same way that Q-learning can? The next thing is that I'm not sure why the policy would ever change in value iteration? I thought the whole idea was to "predict" how this particular policy would perform using value iteration to find the optimal value function for this policy, and then "control" this behaviour using policy iteration - "one would adapt the previous policy slightly, perform value iteration, find a new value function, compare it to the previous value function and check if it had converged.

Is this an incorrect interpretation?

The equation given for value iteration is displayed here:

$ U(s) = R(s) + γmax_a\sum{T(s, a, s')U(s')} $

$ Q(s, a) = R(s, a) + γmax_a Q(s', a')$

Improve this question
$\endgroup$
5
  • $\begingroup$ Probably worth giving the equations for value iteration where you claim it does not need to know the reward beforehand, and linking the context. Value iteration equations are written with $r$ representing a known reward, or known distribution of rewards, based on the known model. The difference between a predicted/modeled reward and observed reward may be critical to understanding the difference between the two algorithms. $\endgroup$ – Neil Slater Dec 7 '17 at 13:46
  • $\begingroup$ @NeilSlater Thanks Neil, I've included them in my edit. $\endgroup$ – tryingtolearn Dec 7 '17 at 13:55
  • $\begingroup$ It's a bit odd to see $R(s)$ independent of any decisions or transitions like that in your first equation, could you link your source, so I can check the assumptions of that source? $\endgroup$ – Neil Slater Dec 7 '17 at 14:13
  • $\begingroup$ @NeilSlater Sure, I was following this: uhaweb.hartford.edu/compsci/ccli/projects/QLearning.pdf $\endgroup$ – tryingtolearn Dec 7 '17 at 14:25
  • $\begingroup$ Thanks. Yes I think it as I guessed in my answer, this is "the reward for entering a state", which is I think valid, but not what I am used to seeing. I'll update my answer to cover it. $\endgroup$ – Neil Slater Dec 7 '17 at 14:30
5
$\begingroup$

I don't see anything in its update equation as to why it requires knowledge of rewards before hand and why it cannot be trained in an online way in the same way that Q-learning can?

The usual Value Iteration update rule is:

$$v(s) \leftarrow \text{max}_a[\sum_{r,s'} p(r, s'|s,a)(r + \gamma v(s')]$$

or it might be written as some variation of

$$v(s) \leftarrow \text{max}_a[R_s^a + \gamma \sum_{s'} (p(s'|s,a)v(s')]$$

In the first equation, $r$ is a known reward value, where you must already know its distribution. In the second equation $R_s^a$ is the expected reward from a particular state, action pair. It is also possible to use $R_{ss'}^a$ - the expected reward from a particular transition. None of these are about observed reward instances.

You cannot use observed reward instances directly in Value Iteration and trust that this will work in expectation in the long term, as you need to take the max over possible actions, and it is not usually possible to observe the output of taking all possible actions.

You could in theory maintain a separate table of estimated expected rewards, and that would then be a complete RL algorithm, not much different from other single-step TD algorithms. It would be a kind of half-way house to Q-learning as you would still need to know transition probabilities in order to use it.

The equation you give for policy iteration uses a slightly different view of reward:

$$U(s) = R(s) + \gamma \text{max}_a\sum_{s'}{T(s, a, s')U(s')}$$

Here $R(s)$ appears to stand for "fixed reward from arriving in this state". If you have a full model to go with the state transitions, then it is provided. But could you learn it from observations? Yes, with one important caveat: The formula assumes that each state has one and only one associated reward value.

If you can safely assume that your MDP has fixed rewards associated with landing in specific states (and often you can if you have constructed the MDP as part of a game or virtual environment), then yes you should be able to run value iteration much like Q-learning in an online fashion using that update rule. The equation will work just fine without you needing to store or estimate anything about immediate rewards - the expected and immediate values would be the same. You should note this is not a completely generic solution that applies to all MDPs.

The next thing is that I'm not sure why the policy would ever change in value iteration?

The policy changes implicitly. The deterministic policy from value iteration is the one that takes the action with best expected return:

$$\pi(s) \leftarrow \text{argmax}_a[\sum_{r,s'} p(r, s'|s,a)(r + \gamma v(s')]$$

This clearly will change as your values converge. All optimal control algorithms need to deal with this, which is why many use a rolling average (a learning rate parameter) to estimate values, and not a true mean.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I see. That last part seems to be very similar to what I thought the point of policy iteration was - changing the policy directly according to the resulting value function. It seems that I've definitely misunderstood something here. In the summation over s', are we summing up over all the states that the agent could go into if it takes action a? Or are we weighting the value of states s' by the probability that the action that takes them to that state s' is chosen? It looks like this is saying that s -> a -> s1 or s2, but all the examples I've come across have been deterministic. $\endgroup$ – tryingtolearn Dec 7 '17 at 14:31
  • $\begingroup$ "Or are we weighting the value of states s' by the probability that the action that takes them to that state s' is chosen?" Yes, that is what the transition matrix or function is doing. A deterministic transition is just a probability of 1 for a specific s, a -> s' rule, and means you can skip the sum if you can just look up what the result should be $\endgroup$ – Neil Slater Dec 7 '17 at 14:39
  • $\begingroup$ Right, that's what I thought but then why do we have the max function? In my head, the transition matrix is the policy and tells the agent how to behave at each state. I feel like this is incorrect and is leading to my confusion. $\endgroup$ – tryingtolearn Dec 7 '17 at 14:42
  • $\begingroup$ The transition matrix is a property of the MDP, and not directly related to the policy. It takes input (s,a,s') and returns probability of transitioning to s' given starting in s and taking action a. That is usually assumed not to change. The policy is what you are learning - how to act - it takes input s and returns suggested a. You take the max over all actions in value iteration because when optimising a policy you want to calculate the result of taking the (current) best action. In policy iteration, you fully calculate this value before explicitly constructing an interim policy . . . $\endgroup$ – Neil Slater Dec 7 '17 at 14:48
  • $\begingroup$ . . . in value iteration, the current best guess at the policy is just assumed already in the calculations. Otherwise they are practically the same algorithm. You can kind of mix-n-match them, sometimes taking the max, sometimes not, if you want. $\endgroup$ – Neil Slater Dec 7 '17 at 14:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.