Finding the optimal policy from a set of fixed policies in reinforcement learning

This is an open-ended question.Suppose I have a reinforcement learning task that is being solved using many different fixed policies, one of which is optimal. The goal of the agent is not to figure out what the optimal policy is but rather which policy (from a set of predefined fixed policies) is the optimal one.

Are there any algorithms/methods that handle this?

I was wondering if meta learning is the right area to look into?

• you could check out a paper I just read called deep exploration with bootstrapped DQN. They kind of do what you say -- they have $k$ Q-functions and one is chosen uniformly at random to choose actions for the policy and they store the tuple in the replay buffer with a mask to determine whether the $k$th network should be updated with said tuple. – David Ireland Aug 13 '20 at 14:19
• Thanks. I'll look into this. It seems like an analogy for this would be like solving a multi-armed bandit but rather than single lotteries you're finding the best policy. Would it be fair to classify this approach as meta-learning? – Max Power Aug 13 '20 at 14:28
• Sorry, I don't know anything about meta-learning so I can't comment! – David Ireland Aug 13 '20 at 14:31

The quickest way to do this would be to use policy evaluation methods. Most of the standard optimal control algorithms consist of policy evaluation plus a rule for updating the policy.

It may not be possible to rank arbitrary policies by performance when considering all states. So you will want to rank them according to some fixed distribution of state values. The usual distribution of start states would be a natural choice (this is also the objective when learning via policy gradients in e.g. Actor-Critic).

One simple method would be to run multiple times for each policy, starting each time according to the distribution of start states, and calculate the return (discounted sum of rewards) from each one. A simple Monte Carlo run from each start state would be fine, and is very simple to code. Take the mean value as your estimate, and measure the variance too so you can establish a confidence for your selection.

Then simply select the policy with the best average value in start states. You can use the variance to calculate a standard error for this, so you will have a feel for how robust your selection is.

If have a large number of policies to select between, you could do a first pass through with a relatively low number of samples, and try to rule out policies that perform badly enough that even adding say 3 standard errors to the estimated value would not cause them to be preferred. Other than that, the more samples you can take, the more accurate your estimates of mean starting value for each policy will be, and the more likely you will be to select the right policy.

I was wondering if meta learning is the right area to look into?

In general no, but you might want to consider meta learning if:

• You have too many policies to select between by testing them all thoroughly.

• The policies have some meaningful low dimension representation that is driving their behaviour. The policy function itself would normally be too high dimensional.

You could then use some form of meta-learning to predict policy performance directly from the representation, and start to skip evaluations from non-promising policies. You may need your fixed policies to number in the thousands or millions before this works though (depending on the number of parameters in the representation and complexity of mapping between parameters and policy function), plus you will still want to thoroughly estimate performance of candidates selected as worth evaluating by the meta-learning.

In comments you suggest treating the list of policies as context-free bandits, using a bandit solver to pick the policy that scores the best on average. This might offer some efficiency over evaluating each policy multiple times in sequence. A good solver will try to find best item in the list using a minimal number of samples, and you could use something like UCB or Gibbs distribution to focus more on the most promising policies. I think the main problem with this will be finding the right hyperparameters for the bandit algorithm. I would suggest if you do that to seed the initial estimates with an exhaustive test of each policy multiple times, so you can get a handle on variance and scale of the mean values.