Answers.Body: <blockquote>
    <p>for example, the "greedy policy" always chooses the action with the highest expected return, no matter which state we are in</p>
  </blockquote>
  
  <p>The "no matter which state we are in" there is generally not true; in general, the expected return depends on the state we are in <strong>and</strong> the action we choose, not just the action.</p>
  
  <p>In general, I wouldn't say that a policy is a mapping from states to actions, but a mapping from states to <strong>probability distributions over actions</strong>. That would only be equivalent to a mapping from states to actions for deterministic policies, not for stochastic policies.</p>
  
  <p>Assuming that our agent has access to (estimates of) value functions <span class="math-container">$Q(s, a)$</span> for state-action pairs, the greedy and <span class="math-container">$\epsilon$</span>-greedy policies can be described in precisely the same way.</p>
  
  <p>Let <span class="math-container">$\pi_g (s, a)$</span> denote the probability assigned to an action <span class="math-container">$a$</span> in a state <span class="math-container">$s$</span> by the greedy policy. For simplicity, I'll assume there are no ties (otherwise it would in practice be best to randomize uniformly across the actions leading to the highest values). This probability is given by:</p>
  
  <p><span class="math-container">$$
  \pi_g (s, a) = 
  \begin{cases}
  1, &amp; \text{if } a = \arg\max_{a'} Q(s, a') \\
  0, &amp; \text{otherwise}
  \end{cases}
  $$</span></p>
  
  <p>Similarly, <span class="math-container">$\pi_{\epsilon} (s, a)$</span> could denote the probability assigned by an <span class="math-container">$\epsilon$</span>-greedy strategy, with probabilities given by:</p>
  
  <p><span class="math-container">$$
  \pi_{\epsilon} (s, a) = 
  \begin{cases}
  (1 - \epsilon) + \frac{\epsilon}{\vert \mathcal{A}(s) \vert}, &amp; \text{if } a = \arg\max_{a'} Q(s, a') \\
  \frac{\epsilon}{\vert \mathcal{A}(s) \vert}, &amp; \text{otherwise}
  \end{cases}
  $$</span>
  where <span class="math-container">$\vert \mathcal{A}(s) \vert$</span> denotes the size of the set of legal actions in state <span class="math-container">$s$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T18:03:08.393Z
Answers.Text: By "the 'greedy policy' always chooses the action with the highest expected return, no matter which state we are in", I meant that, given a state where the agent is currently in, then the action that is chosen is always the one with the highest expected return from that state. No? I am more confused now, because the expected return is something associated with a state.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T18:04:55.890Z
Answers.Text: @nbro Sure. Which can still be interpreted as a mapping from states to probability distributions (where every probability distribution happens to have all the probability mass assigned to a single action)
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T18:16:30.793Z
Answers.Text: So, you're defining policies like the _greedy_ or _$\epsilon$-greedy_ with respect to value functions. Is this always the case? Also, you say that a policy which solves a MDP is a mapping between states and probability distribution over actions. However, AFAIK, the optimal policies are (often) deterministic. No? Can they be considered greedy? For example, the policy learned by Q-learning, which, at the end, will be a mapping from states to actions (or probability over actions?). Is the policy learned using Q-learning greedy?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T18:16:44.270Z
Answers.Text: AFAIK, Q-learning uses the $\max$ operator, which makes it learn the greedy policy (as the target).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T18:46:13.717Z
Answers.Text: @nbro Greedy and $\epsilon$-greedy policies will always have to be with respect to some sort of value function yes... but there are different ways to learn policies directly without first learning a value function as an "intermediate" step (see [policy gradients](https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html)). If you start to include adversarial elements in your environment, there may be cases where optimal policies are non-deterministic (think Rock-Paper-Scissors).
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T18:47:39.723Z
Answers.Text: Technically... I'd say $Q$-learning doesn't learn a policy at all. It learns the value function $Q^{\pi_g}$ corresponding to the greedy policy $\pi_g$ (the value function is the output of the learning algorithm, and given that value function it is trivial to derive the greedy policy with respect to those value).
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-10T17:58:44.270Z
Answers.LastActivityDate: 2019-02-11T08:05:10.490Z
Answers.LastEditDate: 2019-02-11T08:05:10.490Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>In the context of reinforcement learning, a policy, <span class="math-container">$\pi$</span>, is often defined as a function from the space of states, <span class="math-container">$\mathcal{S}$</span>, to the space of actions, <span class="math-container">$\mathcal{A}$</span>, that is, <span class="math-container">$\pi : \mathcal{S} \rightarrow \mathcal{A}$</span>. This function is the &quot;solution&quot; to a problem, which is represented as a Markov decision process (MDP), so we often say that <span class="math-container">$\pi$</span> is a solution to the MDP. In general, we want to find the optimal policy <span class="math-container">$\pi^*$</span> for each MDP <span class="math-container">$\mathcal{M}$</span>, that is, for each MDP <span class="math-container">$\mathcal{M}$</span>, we want to find the policy which would make the agent behave optimality (that is, obtain the highest &quot;cumulative future discounted reward&quot;, or, in short, the highest &quot;return&quot;).</p>
  <p>It is often the case that, in RL algorithms, e.g. Q-learning, people often mention &quot;policies&quot; like <span class="math-container">$\epsilon$</span>-greedy, greedy, soft-max, etc., without ever mentioning that these policies are or not solutions to some MDP. It seems to me that these are two different types of policies: for example, the &quot;greedy policy&quot; always chooses the action with the highest expected return, no matter which state we are in; similarly, for the &quot;<span class="math-container">$\epsilon$</span>-greedy policy&quot;; on the other hand, a policy which is a solution to an MDP is a map between states and actions.</p>
  <p>What is then the relation between a policy which is the solution to an MDP and a policy like <span class="math-container">$\epsilon$</span>-greedy? Is a policy like <span class="math-container">$\epsilon$</span>-greedy a solution to any MDP? How can we formalise a policy like <span class="math-container">$\epsilon$</span>-greedy in a similar way that I formalised a policy which is the solution to an MDP?</p>
  <p>I understand that &quot;<span class="math-container">$\epsilon$</span>-greedy&quot; can be called a policy, because, in fact, in algorithms like Q-learning, they are used to select actions (i.e. they allow the agent to behave), and this is the fundamental definition of a policy.</p>
  
Tags: <reinforcement-learning><definitions><markov-decision-process><policies><exploration-strategies>
Title: What is the relation between a policy which is the solution to a MDP and a policy like $\epsilon$-greedy?
UserDisplayName: nbro
ThreadText: # What is the relation between a policy which is the solution to a MDP and a policy like $\epsilon$-greedy?
  
  (Asked by: username_0 on 2019-02-10)
  
  In the context of reinforcement learning, a policy, $\pi$, is often defined as a function from the space of states, $\mathcal{S}$, to the space of actions, $\mathcal{A}$, that is, $\pi : \mathcal{S} \rightarrow \mathcal{A}$. This function is the "solution" to a problem, which is represented as a Markov decision process (MDP), so we often say that $\pi$ is a solution to the MDP. In general, we want to find the optimal policy $\pi^\*$ for each MDP $\mathcal{M}$, that is, for each MDP $\mathcal{M}$, we want to find the policy which would make the agent behave optimality (that is, obtain the highest "cumulative future discounted reward", or, in short, the highest "return").
  
  It is often the case that, in RL algorithms, e.g. Q-learning, people often mention "policies" like $\epsilon$-greedy, greedy, soft-max, etc., without ever mentioning that these policies are or not solutions to some MDP. It seems to me that these are two different types of policies: for example, the "greedy policy" always chooses the action with the highest expected return, no matter which state we are in; similarly, for the "$\epsilon$-greedy policy"; on the other hand, a policy which is a solution to an MDP is a map between states and actions.
  
  What is then the relation between a policy which is the solution to an MDP and a policy like $\epsilon$-greedy? Is a policy like $\epsilon$-greedy a solution to any MDP? How can we formalise a policy like $\epsilon$-greedy in a similar way that I formalised a policy which is the solution to an MDP?
  
  I understand that "$\epsilon$-greedy" can be called a policy, because, in fact, in algorithms like Q-learning, they are used to select actions (i.e. they allow the agent to behave), and this is the fundamental definition of a policy.
  
  **Tags:** reinforcement-learning, definitions, markov-decision-process, policies, exploration-strategies
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-02-10. Score: 5 | Accepted answer
  
  > for example, the "greedy policy" always chooses the action with the highest expected return, no matter which state we are in
  
  The "no matter which state we are in" there is generally not true; in general, the expected return depends on the state we are in **and** the action we choose, not just the action.
  
  In general, I wouldn't say that a policy is a mapping from states to actions, but a mapping from states to **probability distributions over actions**. That would only be equivalent to a mapping from states to actions for deterministic policies, not for stochastic policies.
  
  Assuming that our agent has access to (estimates of) value functions $Q(s, a)$ for state-action pairs, the greedy and $\epsilon$-greedy policies can be described in precisely the same way.
  
  Let $\pi\_g (s, a)$ denote the probability assigned to an action $a$ in a state $s$ by the greedy policy. For simplicity, I'll assume there are no ties (otherwise it would in practice be best to randomize uniformly across the actions leading to the highest values). This probability is given by:
  
  $$
  \pi\_g (s, a) =
  \begin{cases}
  1, & \text{if } a = \arg\max\_{a'} Q(s, a') \\
  0, & \text{otherwise}
  \end{cases}
  $$
  
  Similarly, $\pi\_{\epsilon} (s, a)$ could denote the probability assigned by an $\epsilon$-greedy strategy, with probabilities given by:
  
  $$
  \pi\_{\epsilon} (s, a) =
  \begin{cases}
  (1 - \epsilon) + \frac{\epsilon}{\vert \mathcal{A}(s) \vert}, & \text{if } a = \arg\max\_{a'} Q(s, a') \\
  \frac{\epsilon}{\vert \mathcal{A}(s) \vert}, & \text{otherwise}
  \end{cases}
  $$
  where $\vert \mathcal{A}(s) \vert$ denotes the size of the set of legal actions in state $s$.
  
  > **Comments:**
  > **username_0**: By "the 'greedy policy' always chooses the action with the highest expected return, no matter which state we are in", I meant that, given a state where the agent is currently in, then the action that is chosen is always the one with the highest expected return from that state. No? I am more confused now, because the expected return is something associated with a state.  
  > **username_1**: @nbro Sure. Which can still be interpreted as a mapping from states to probability distributions (where every probability distribution happens to have all the probability mass assigned to a single action)  
  > **username_0**: So, you're defining policies like the _greedy_ or _$\epsilon$-greedy_ with respect to value functions. Is this always the case? Also, you say that a policy which solves a MDP is a mapping between states and probability distribution over actions. However, AFAIK, the optimal policies are (often) deterministic. No? Can they be considered greedy? For example, the policy learned by Q-learning, which, at the end, will be a mapping from states to actions (or probability over actions?). Is the policy learned using Q-learning greedy?  
  > **username_0**: AFAIK, Q-learning uses the $\max$ operator, which makes it learn the greedy policy (as the target).  
  > **username_1**: @nbro Greedy and $\epsilon$-greedy policies will always have to be with respect to some sort of value function yes... but there are different ways to learn policies directly without first learning a value function as an "intermediate" step (see [policy gradients](https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html)). If you start to include adversarial elements in your environment, there may be cases where optimal policies are non-deterministic (think Rock-Paper-Scissors).  
  > **username_1**: Technically... I'd say $Q$-learning doesn't learn a policy at all. It learns the value function $Q^{\pi_g}$ corresponding to the greedy policy $\pi_g$ (the value function is the output of the learning algorithm, and given that value function it is trivial to derive the greedy policy with respect to those value).  
  
  ---
  
  