# What is a non-starving policy in reinforcement learning?

In the paper, Eligibility Traces for off-Policy Policy Evaluation (2010), by Doina Precup et al., mentioned the term "non-starving" many times. The specific use of the term was like "non-starving policy" in the context of off-policy learning.

A specific mention of the term

we consider a method that requires nothing of the behavior policy other than that it be non-starving, i.e., that it never reaches a time when some state-action pair is never visited again.

What does the thing look like intuitively? Why is it required?

## 1 Answer

A non-starving policy is a (behavior) policy that is theoretically guaranteed to visit each state and take all possible actions from each state an infinite number of times, so that to always update $$Q(s, a)$$, $$\forall s, \forall a$$, an infinite number of times. In the context of off-policy prediction, this criterion implies that any trajectory will have no zero probability under a behavior policy. As a consequence, the experience from the behavior policy sufficiently covers the possibilities of any target policy.

An example of a non-starving policy is the $$\epsilon$$-greedy policy, which, with $$0 < \epsilon \leq 1$$ (which is usually a small number between $$0$$ and $$1$$) probability, takes a random action from a given state, and, with $$1-\epsilon$$ probability, takes the current best action, that is, the action with the highest value from a given state, according to the current value function.

• Could I say that the presence of a non-starving behavior policy is to guarantee that an importance sampling ratio does not go to "infinity"? A second thought tells me that this is not the case. Non-starving seems to be a "requirement" for all policies considered in RL? – Phizaz Sep 12 '19 at 3:22
• @Phizaz You can ask another question on the website. – nbro Sep 12 '19 at 10:40
• You didn't answer my question on the "why is it required" part. – Phizaz Sep 12 '19 at 17:21
• @Phizaz I answered: "Of course, while the agent is learning, it needs to sufficiently explore the state and action spaces, so that to learn the most rewarding (or profitable) actions from each state.". – nbro Sep 12 '19 at 19:18
• Does it have anything to do with off-policy learning? Or it's just a common assumption needed for any learning algorithm to work? I suspect if that the case, it is not worth mentioning in the paper at all. – Phizaz Sep 14 '19 at 3:58