I have seen this sentence while reading an RL source (slide 29): "As discussed with MC-based off-policy control: avoidance of the exploration-optimality trade-off for on-policy methods."
Question: Why doesn't the exploration-optimality trade-off persist for off-policy methods such as Q-learning?
I feel that this question is more easily understood by contrasting on-policy methods with off-policy methods.
An off-policy method generates data in the environment with a behavior policy during training to update a target policy for evaluation. Off-policy methods usually navigate the exploration-exploitation trade-off by using a behavior policy that is suboptimal to better explore the environment and generate a rich set of experience during training. Since the target policy does not generate experience in the environment, it is often designed to neglect exploration and is therefore generally superior to the behavior policy during evaluation, sometimes up to complete optimality.
In contrast, on-policy methods use the experience generated in the environment with the behavior policy to update that same policy: the behavior and target policies for on-policy algorithms are identical. Since the exploration-exploitation trade-off still persists while generating the experience during training, the policy must be designed to take presumably suboptimal actions to explore. However, increasing exploration generally degrades the policy's performance during evaluation. The trade-off of needing to increase exploration during training that generally decreases the optimality of the policy during evaluation can be dubbed the exploration-optimality trade-off for on-policy algorithms.
To answer your question as posed, off-policy methods bypass the exploration-optimality trade-off by using separate behavior and target policies. Increasing exploration in the behavior policy during training does not generally decrease optimality of the target policy during evaluation. Note that I personally have not seen the exploration-optimality trade-off explicitly mentioned in any source; I have seen a discussion of the ideas of this trade-off in Example 6.6 of Sutton & Barto.
Whilst it's not perfect separation, because you may still pay real costs for exploration during learning (in fact possibly worse than on-policy methods), then off-policy methods do offer a clean way to learn optimal control whilst worrying a lot less about how to converge towards the optimal policy.
With on-policy methods, the exploration Vs exploitation tradeoff directly affects learning - if you set a low exploration level (e.g. low $\epsilon$) then learning about alternatives is slow. If you set a high exploration level, then the algorithm learns about a high exploration policy which is likely to be far from optimal. Typical solutions require careful management of exploration, reducing it over time, approaching zero.
Off-policy methods free you from that specific part of the dilemma. They can learn about a policy which is the current best guess at a deterministic optimal policy, whilst still exploring.
In theory, off-policy methods can learn optimal control given a behaviour policy of random action selection without reference to any value function. This is an extreme separation between behaviour and target policies, and follows the statement in S&B - theoretically off-policy learning gives you freedom to choose any exploration rate, whilst still guaranteeing converging on optimal control (for the tabular version at least).
In practice you still need to care about the degree of exploration with off-policy methods, because too much exploration will provide values for states that the agent wouldn't visit for optimal behaviour which don't matter. In a lot of problem domains, this can be the vast majority of states that are not worth exploring, because they are not even close to an optimal trajectory and there's nothing useful to learn about them. Too much exploration with off-policy doesn't prevent learning (like it would with on-policy), but it may reduce the convergence rate so much that solutions are not practical.
So typical off-policy methods do also manage exploration rate, on the surface quite similarly to on-policy. However the difference is that the ranges of values that work for off-policy are much broader, and it is common to keep a moderate or small amount of exploration always (where an on-policy method would have trouble converging to optimal with the same exploration rate).
