Value Function

The Value function is used to estimate how good it is for the agent to be in a given state.

Used for Policy Evaluation.

Whereas the Reward indicates what is good in the immediate sense, the value function specifies what is good in the long run.

For an MRP, The value function $v(s)$ gives the long-term value of state $s$. They are defined in terms of a Policy.

Definition

The state-value function $v_{\pi }(s)$ of an MDP is the expected Return starting from state $s$, and then following policy $\pi$ $v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t\mid S_t=s]$

Definition

The action-value function $q_{\pi }(s,a)$ of an MDP is the expected Return starting from state $s$, taking action $a$, and then following policy $\pi$ $q_{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t\mid S_t=s,A_t=a]$

But we can do better, because we are making assumptions that the problem we are solving is a MDP, so the current state has captured all information (not dependent on past rewards). We can break the equation into two parts (the idea of breaking our value function down into these 2 parts is called a Bellman Equation):

$\text{Value}=\text{immediate reward}+\text{discounted sum of future rewards (future value)}$

With the value function, the probability (weight of each edge) is given by the policy, we decide that. Below are called Backup Diagram: $v_{\pi }(s)={\sum }_a\pi (a|s)q_{\pi }(s,a)$ On the other hand, for the q-value (i.e. after we have done an action), this is what we do with the environment. After choosing an action, we get a reward, and the probability of landing into new states are given by our environment. We also apply the Discount Factor here. $q_{\pi }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)(r+\gamma v_{\pi }(s^{\prime }))$ So now, we can have a recursive relationship. $v_{\pi }(s)={\sum }_a\pi (a|s){\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)(r+\gamma v_{\pi }(s^{\prime }))$ $q_{\pi }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)(r+\gamma {\sum }_{a^{\prime }}\pi (a^{\prime }|s^{\prime })q_{\pi }(s^{\prime },a^{\prime }))$

We use Bellman Equation to calculate the value function.

Important

The value function of the terminal state is always $v(s_{terminal})=0$

Computing the Value Function

We can run a bunch of simulations and average the returns to compute the value function of a particular state, where you use the janky equation that you don’t usually use.

State-Value vs. Action-Value Function

Maybe I talked about this somewhere else, but in Model-Free Control, you ABSOLUTELY need to use action-value function $Q(s,a)$, it will not work with $V(s)$, because that depends on the next value function? See Generalized Policy Iteration

Next

• Optimal Value Function