6
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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$.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$
    – nbro
    Feb 10, 2019 at 18:03
  • 2
    $\begingroup$ @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) $\endgroup$
    – Dennis Soemers ♦
    Feb 10, 2019 at 18:04
  • 1
    $\begingroup$ 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? $\endgroup$
    – nbro
    Feb 10, 2019 at 18:16
  • 1
    $\begingroup$ @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). If you start to include adversarial elements in your environment, there may be cases where optimal policies are non-deterministic (think Rock-Paper-Scissors). $\endgroup$
    – Dennis Soemers ♦
    Feb 10, 2019 at 18:46
  • 2
    $\begingroup$ 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). $\endgroup$
    – Dennis Soemers ♦
    Feb 10, 2019 at 18:47

You must log in to answer this question.

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