0
$\begingroup$

I am new to RL and I am trying to understand how to find solutions of an MDP.
This is what I understand so far -> since the nature of our environment is stochastic, at a state 's' if we take an action 'a' we do not know which state we would end up in. So we define the following terms :

  1. T(s, a, s') or P(s'/s, a) - transition probability. This is the probability that starting at state 's' and taking action 'a' we end up in state s'
  2. V(s) - value of a state, which tells us how good or bad this state 's' is.
  3. R(s) - reward of being in a state 's', this is also known as the immediate reward of being in state 's'
  4. Q(s) - state action value function. This tells us that given we are at a state 's' and we take a particular action 'a' what is the expected utility of the state s' we might end up in

Now coming to the part that confuses me. From what I understand so far, the difference between v(s) and q(s) is that v(s) gives us the utility of a state assuming we do not know which action to take while q(s) is the value of that state given we take a particular action 'a'.
Coming to $v^\pi(s)$ = same as what I defined v(s) to be, so the value of a state
$v^*(s)$ = value of a state given we take the optimal action 'a' so this is like following max (q(s)) over all actions
I read online how to mathematically define these terms and I am not sure if I correctly understand them. Also, I don't really understand the difference between $v^*(s) $ and $v^\pi(s)$
I found some conflicting ideas online but since I am just starting out I am not sure what is lacking in my understanding:



$ V^\pi(s) = R(s) + \gamma*max\sum P(s'/s,a)*V^\pi(s') $

$V^*(s) = max\ Q*(s,a)$ and here we can substitute for Q*(s,a) as $Q^*(s,a) = \sum T(s,a,s')*[R(s) + \gamma V^*(s')]$ so we get $V^*(s) = max \sum T(s,a,s')*[R(s) + \gamma V^*(s')]$

$V(s) = \gamma*max\sum P(s'/s,a)*V(s')$



As you can see there are different equations which are defining the same V(s) quantity? So what exactly is the clear definition of V(s)? Are these equations just dependent on the case of RL we are dealing with? I don't understand how to distinguish between these, any suggestions/links/readings are much appreciated! Thanks!
$\endgroup$

1 Answer 1

2
$\begingroup$

Your confusion seems to come from mixing up between some policy $\pi$ and an optimal policy $\pi^*$. Your summary is generally correct, but missing these extra details.

Let me try go through it again. Starting with the MDP definitions:

  • First of all, we have the transition probabilities $T(s,a,s') = P(s'|s,a)$ which are conditional probabilities of arriving at state $s'$, given that we've taken action $a$ in state $s$
  • The (expected) reward is generally associated with the state-action pair $R(s,a)$ - there is some slight variations about it in literature, but that's a subject for a different discussion.
  • Then we have the policy $\pi(a,s) = P(a|s)$ - the probability of taking an action $a$ in state $s$ for an agent following the policy.

Given all three things above: $T$, $R$ and $\pi$ (plus a discount factor $\gamma$) you can define your value functions as average discounted rewards collected by the agent that follows $\pi$.

  • $V^\pi(s)$ is the average reward that the agent following $\pi$ will collect, when starting from the state $s$.
  • $Q^\pi(s,a)$ is the average reward that the agent following $\pi$ will collect, when starting from the state $s$ and taking an action $a$.

Quite often authors drop the index $\pi$ and assume implicitly that we are dealing with some policy $\pi$, but one should keep in mind that some (maybe unspecified) policy is always in the context when we are talking about value functions $V$ or $Q$.

These value functions satisfy the following recursive relationships for any policy $\pi$ (note that there's no $\max_a$ in these):

$$V^\pi(s) = \sum_a\pi(a,s)\left[R(s,a) + \gamma \sum_{s'}T(s',s,a)V^\pi(s')\right]$$ $$Q^\pi(s,a) = R(s,a) + \gamma \sum_{s',a'}T(s',s,a)\pi(a'|s')Q^\pi(s',a')$$

Now, some policies maximize the expected reward - these policies are called "optimal" and standardly denoted with a star: $\pi^*(a,s)$ - optimal policy. The index $\pi$ for the value functions is usually replaced with a star as well: $V^*$ and $Q^*$. The optimal value functions satisfy Bellman equations (the ones that have $\max_a$ in them):

$$V^*(s) = \max_a\left[R(s,a) + \gamma \sum_{s'}T(s',s,a)V^*(s')\right]$$ $$Q^*(s,a) = R(s,a) + \gamma \max_{a'}\sum_{s'}T(s',s,a)Q^*(s',a')$$

Hope this clarifies it.

$\endgroup$
2
  • $\begingroup$ Thank you for your reply! So just to be clear, when we say we have a policy $\pi$ then that means we have some given probabilities of taking the available actions from a given state s? I thought that a policy was more like a definite set of actions we take from each state, like for example consider that you can go up, left & right at any given state, then according to my understanding I thought that a policy is like telling us which action to take in a particular state, like GO LEFT, then at the next state we could have GO UP or something like this. $\endgroup$ Apr 11, 2021 at 3:49
  • $\begingroup$ @JANVISHARMA You are correct that the policy is the probability for an agent to take action $a$ in state $s$. Our goal, usually, is to find some (usually optimal) policy. The "definite" policies you are talking about are called "deterministic policies" - these make a subclass of all possible policies. $\endgroup$
    – Kostya
    Apr 11, 2021 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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