3
$\begingroup$

In page 125 of Sutton and Barto (second last paragraph) the proof for equality of $v_{\pi}$ and $v_*$ for $\epsilon$ soft policies is given. But I could not understand the statement explaining the proof:

Consider a new environment that is just like the original environment, except with the requirement that policies be $\epsilon$-soft “moved inside” the environment. The new environment has the same action and state set as the original and behaves as follows. If in state $s$ and taking action $a$, then with probability $1 - \epsilon$ the new environment behaves exactly like the old environment. With probability $\epsilon$ it repicks the action at random, with equal probabilities, and then behaves like the old environment with the new, random action. The best one can do in this new environment with general policies is the same as the best one could do in the original environment with $\epsilon$-soft policies.

What is the meaning of environment here? And what is this new thing/argument (provided above) the authors are describing to arrive at the proof?

$\endgroup$

1 Answer 1

2
$\begingroup$

Let's first clarify a couple of details:

  1. The policy $\pi$ we're talking about is an $\epsilon$-soft policy (defined to mean that $\pi(a \vert s) \geq \frac{\epsilon}{\vert \mathcal{A}(s) \vert}$ for all states and all actions).
  2. We're not trying to prove equality of $v_{\pi}$ and $v_*$, but of $v_{\pi}$ and $\tilde{v}_*$, where $\tilde{v}_*$ denotes the optimal value function in this "new environment" that we're constructing.

So, "environment" is basically the "world" that our agent "lives" and acts in. You can think of it as the "rules" that we "play" by. So, you could think of the definitions of our complete state and action spaces as part of the environment, and the function that tells us which successor state $s'$ we end up in whenever we pick an action $a$ in a state $s$ (i.e. the state transition dynamics) are a part of the environment. And the function that tells us what Rewards we'll obtain in what situations is also a part of the environment. The policy $\pi$ is not a part of the environment; this is the "brain" of the agent itself.

Now, recall that here we're not interested in proving that $v_{\pi}$ moves towards the true optimal value function $v_*$ of the "real" environment. We know for a fact that we won't ever become completely equal to that, because we're forcing our policies to have exploratory behaviour by requiring them to be $\epsilon$-soft, so it would be hopeless to prove such a thing. Instead, we're interested in proving that $v_{\pi}$ will move towards whatever value function is the best one that we could possibly achieve under the restriction that we must have an $\epsilon$-soft policy.

What we do in the book here is that we slightly "transform" our environment into a new environment (i.e. we change the rules that we play by just a little bit). This is done in a clever way, such that the thing I just described that we want to prove becomes mathematically equivalent to just proving that $v_{\pi}$ moves towards (or becomes equal to) $\tilde{v}_*$. Now, if we can prove this for the new environment, we'll automatically have proven the thing that we actually wanted to prove for the "real" environment.

$\endgroup$
4
  • $\begingroup$ @ Dennis Soemers 1- Consider a new environment that is just like the original environment, except with the requirement that policies be ε-soft “moved inside” the environment. 2-The best one can do in this new environment with general policies is the same as the best one could do in the original environment with ε-soft policies. Are 1 and 2 not conflicting each other because in (1) only epsilon soft policies are in the new environment and in (2) the author is talking about general policies? $\endgroup$ Feb 13, 2022 at 22:00
  • $\begingroup$ @DSPinfinity (1) does not say that only epsilon soft policies are in the new environment. We had that requirement for the old environment. (1) states that we no longer explicitly have that same constraint on the policy, but we modify the environment in such a way that the environment actually enforces something like "epsilon-softness" on general / deterministic policies whenever they are used to play the new environment. The new environment simply has a bunch of randomness baked into it. $\endgroup$
    – Dennis Soemers
    Feb 14, 2022 at 9:35
  • $\begingroup$ What does this mean exactly: "Consider a new environment that is just like the original environment, except with the requirement that policies be $\varepsilon$-soft "moved inside" the environment? Does it mean that in new environment we can have all general policies in contrast to the old environment where we have only $\varepsilon$-soft policies? The English language use of the authors is very weird sometimes for me. $\endgroup$ Feb 14, 2022 at 13:03
  • $\begingroup$ @DSPinfinity with "moved inside the environment" they mean exactly what they write afterwards in more explicit detail: "The new environment has the same action and state set as the original and behaves as follows. If in state $s$ and taking action $a$, then with probability $1 - \epsilon$ the new environment behaves exactly like the old environment. With probability $\epsilon$ it repicks the action at random, with equal probabilities, and then behaves like the old environment with the new, random action." So the "$\epsilon$-randomness" is made an inherent part of the environment. $\endgroup$
    – Dennis Soemers
    Feb 14, 2022 at 14:07

You must log in to answer this question.