1
$\begingroup$

From what I understand, the value function estimates how 'good' it is for an agent to be in a state, and a policy is a mapping of actions to state.

If I have understood these concepts correctly, why does the value of a state change with the policy with which an agent gets there?

I guess I'm having difficulty grasping the concept that the goodness of a state changes depending on how an agent got there (different policies may have different ways, and hence different values, for getting to a particular state).

If there can be a concrete example (perhaps on a grid world or on a chessboard), that might make it clear why that might be the case.

$\endgroup$

1 Answer 1

2
$\begingroup$

I guess I'm having difficulty grasping the concept that the goodness of a state changes depending on how an agent got there

It doesn't.

The value of a state changes depending on what the agent will do next. That is where the dependency on the policy comes in, not in past behaviour, but expectations of future behaviour. The future behaviour depends on the state transitions and rewards presented by the environment, plus it depends on the distribution of actions chosen by the policy.

More formally, the value function of a state is not just a relative and arbitrary scoring system, but equals the expected (discounted) sum of rewards, assuming the MDP follows the given dynamics, including action selection:

$$v_{\pi}(s) = \mathbb{E}_{A \sim \pi}[\sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t = s]$$

Without identifying a policy, it is not possible to assess a value function. In value-based control methods, the policy to evaluate can be implied, somewhat self-referentially, as the policy that acts greedily (or maybe $\epsilon$-greedily) according to the current estimates of the value function.

If there can be a concrete example (perhaps on a GridWorld or on a chess board), that might make it clear why that might be the case

A very simple deterministic MDP with a start state and two terminal states illustrates this:

Very basic MDP

Start in state B. Taking the left action is followed by a transition (with $p=1$) to terminal state A, and a reward of $0$. Taking the right action is followed by a transition (with $p=1$) to terminal state C, and a reward of $3$.

What is the value of state B? It depends on what the policy chooses. A deterministic left policy $\pi_1$ has $v_{\pi_1}(B) = 0$, a random policy $\pi_2$ choosing left and right with $p=0.5$ has $v_{\pi_2}(B) = 1.5$. The optimal policy chooses action right always and has $v_{\pi_3}(B) = v^*(B) = 3.0$

$\endgroup$
5
  • $\begingroup$ I guess this does answer my question of why does a value function explicitly depend on a policy. There's no way of knowing how an agent will behave once it leaves the current state unless it has a policy defining its behaviour. $\endgroup$ Sep 24, 2018 at 1:35
  • $\begingroup$ Just out of curiosity though, why do states having an absolute value (independent of policy) does not make sense? Why is the measure of how good a state is dependent upon how an agent will act once it is in the state? $\endgroup$ Sep 24, 2018 at 1:38
  • $\begingroup$ Is it because we define how good a state is in terms of expected future rewards which implies that by definition a value function needs a policy with it? $\endgroup$ Sep 24, 2018 at 1:56
  • 1
    $\begingroup$ @user3079474: Yes, the value function in RL is defined that way, so that's precisely what it means. You could invent some function that allocated an absolute "value" to each state, but that would be a different function. Possibly the closest in RL, would be if immediate reward is allocated according only to state (which is quite common situation - e.g. think of winning any board game, this is often purely a function of state) - that would not be the value function though, but how the reward function was set up. $\endgroup$ Sep 24, 2018 at 7:09
  • 1
    $\begingroup$ Some heuristic systems may also allocate values to states, and use them to guide search for game and problem-solving tree searches (like A*). There is a little bit of overlap here, as you can use a learned RL value function in place of a heuristic - that is essentially what AlphaGo and its variants do. $\endgroup$ Sep 24, 2018 at 7:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .