Finding the true Q-values in gymnaiusm

Question

I'm very interested in the true Q-values of state-action pairs in the classic control environments in gymnasium. Contrary to the usual goal, the ordering of the Q-values itself is irrelevant; a very close to accurate estimation of the Q-values is important.

Ideally, I could use an already trained model like a DQN to do this, but the key concern here is the overestimation that is common in Q-learning. Is there a model openly available that predicts this accurately; for instance, can we rely on a trained double-DQN for very close to accurate Q-values? Or is the only option to run a DQN until it solves the environment, then evaluate the policy found using many Monte Carlo rollouts? Or is it something else entirely?

Answer 1

In simple environments, the gold standard for true values to arbitrary accuracy would be to use dynamic programming, either policy iteration or value iteration (to evaluate a fixed policy, then use a single evaluation run from policy iteration). This should be feasible for discrete state/action spaces up to a million or more for classic problems that can be evaluated quickly.

You are right to be concerned about DQN accuracy. I don't think there is any easy way to check accuracy of results using just the DQN networks. Double DQN removes a source of bias, but not approximation errors, or statistical ones. Due to Q-learning's focus on learning close-to-optimal trajectories, you should expect action values that a DQN neural network predicts for states and actions more than a couple of steps away from the optimal path to be quite inaccurate due to low sample rates.

If you are only concerned about a limited number of state/action pairs, and are happy to treat the DQN greedy policy as your target, then you could check values by Monte Carlo sampling starting from a chosen set of pairs. If the environment is deterministic you would only need one sample per pair. If not, you may need 1000s to get accurate measurements (you will be able to calculate your error bounds by taking the variance of the measured returns). Also, this doesn't guarantee you will have the Q values of the optimal policy - in a complex enough environment there is no guarantee you can get that by any means.