3
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – Phizaz
    Commented Sep 12, 2019 at 3:22
  • $\begingroup$ @Phizaz You can ask another question on the website. $\endgroup$
    – nbro
    Commented Sep 12, 2019 at 10:40
  • $\begingroup$ You didn't answer my question on the "why is it required" part. $\endgroup$
    – Phizaz
    Commented Sep 12, 2019 at 17:21
  • $\begingroup$ @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.". $\endgroup$
    – nbro
    Commented Sep 12, 2019 at 19:18
  • $\begingroup$ 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. $\endgroup$
    – Phizaz
    Commented Sep 14, 2019 at 3:58

You must log in to answer this question.

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