What is the relation between a policy which is the solution to a MDP and a policy like $\epsilon$-greedy?
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, &amp; \text{if } a = \arg\max_{a'} Q(s, a') \\
0, &amp; \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}, &amp; \text{if } a = \arg\max_{a'} Q(s, a') \\
\frac{\epsilon}{\vert \mathcal{A}(s) \vert}, &amp; \text{otherwise}
\end{cases}
$$
where $\vert \mathcal{A}(s) \vert$ denotes the size of the set of legal actions in state $s$.