Which policy do I need to use in updating Q function?

Question

Policy function can be of two types: deterministic policy and stochastic policy.

Deterministic policy is of the form $\pi : S \rightarrow A$

Stochastic policy is defined using conditional probability distributions and I generally remember as $\pi: S \times A \rightarrow [0,1]$. (I personally don't know whether the function prototype is correct or not)

I am guessing that both type of policies can be used for Q learning. As one can read from this answer that both reward and policy function are needed to implement $Q$ learning algorithm

In addition to the RF, you also need to define an exploratory policy (an example is the $\epsilon$-greedy), which allows you to explore the environment and learn the state-action value function $\hat{q}$.

I have no doubt about the necessity of reward function as it is obvious from the updating equation of $Q$.

And coming to the (usage of policy), you can find it from the line 5 of the pseudocode provided in the answer

Choose $a$ from $s$ using policy derived from $Q$

One can notice that policy is used for computing $Q$ and $Q$ updation also needs a policy.

Henceforth I conclused myself that the correct statement for the line 5 of pseudocode has to be

Choose $a$ from $s$ using policy derived from $Q$ updated so far

Is my conclusion true? Else, how is it possible to break that cyclic dependency between policy and $Q$ function?

Answer 1

I am going to stick with Q learning here to keep things simple. Most value-based reinforcement learning used for optimal control will have some statement similar to:

Choose $a$ from $s$ using policy derived from $Q$

First, yes this is always the current Q function or Q table, evaluated for the state of interest.

When you are choosing the agent's best guess at optimal actions, then this derivation of policy is fixed:

$$\pi(s) = \text{argmax}_a Q(s,a)$$

This matches your form for a deterministic policy (although it is always possible to express a deterministic policy as a stochastic one with probabitly of 1 choosing its selected action). In Q-learning this policy is the target policy that you are currently learning the value of.

When it comes to taking actions in the environment to gain new observations, you do not use the target policy, because it does not explore. Instead you use a different behaviour (or exploring) policy. It is important for Q learning to work in theory that this policy is "soft" - that it has some non-zero chance of selecting any action.

A popular choice for the behaviour policy is to use $\epsilon$-greedy, which is a stochastic policy that selects a random actiom with probability $\epsilon$, otherwise it selects the greedy policy. The greedy policy is definitely "derived from Q", so the $\epsilon$-greedy is too.

In fact it is not 100% necessary to use a "policy derived from Q" for the behaviour policy for Q learning to work. A completely random policy can work, for instance. The learning rate is better though - often much better - if current highest action value estimates are selected more often. This allows the agent to explore state action pairs close to its best guess at optimal.

There are a few other ways to derive behaviour policies from Q table. There is an unwritten assumption in the pseudocode that this will be done in a way that favours the higher-valued actions.

You can come up with any method that creates a stochastic policy function from Q values and has the following traits:

• There is a chance of selecting any action

• There is a higher chance of selecting the current highest valued actions

• Optionally, the preference for highest valued actions becomes stronger as the agent becomes better at the task

If you can do this, then Q learning should work well. It is still sometimes a challenge to find the balance point between exploring enough to learn new things about the environment, yet doing so close to what is currently known to be best.

Regarding this:

Choose $a$ from $s$ using policy derived from $Q$ updated so far

Yes although most sources do not spell that out in full, relying on the use of $Q$ as a variable/data structure to imply it.

The target policy in Q learning is not directly the optimal policy (that is not possible unless you already know it), but the best guess at what would maximise expected return given the updates to Q so far. This keeps shifting as more knowledge is obtained.