1
$\begingroup$

In order to learn an environment, we can use Q-learning as a model free algorithm. In Q-learning, there is a Q function and we update this function using Q-learning algorithm until convergence. When converged, we can find optimal value function for each particular state by maximizing the Q function at that state over all possible actions.

Now, my question is that, assume we don't care about what the optimal action is at each state and we just want to find the optimal value function at each state without calculating the Q function first. Is there anyway for doing this?

By optimal value function, I mean value function corresponding to the optimal policy. Further, we don't have the full model of the environment (rewards and transition probability). So, it is a learning problem.

The reason I am looking for the optimal value function and not optimal Q-function is that, assume the action space is very large but the state space is not. And I only care about the optimal value function. Since the action space is very large, finding optimal Q functions is not efficient or probably impossible for this case.

$\endgroup$
  • $\begingroup$ There are lots of possible answers here, depending on details. First, the value function is critically dependent upon the policy. So, do you want to find the value function for the optimal policy? If not, what policy do you want to assess? Second, you don't have to calculate or estimate Q, but you may have to put in very similar effort to calculate V - that depends what you already know about the environment. Do you have a full model of the environment's MDP (i.e. you already know the transition probabilities and immediate reward values)? $\endgroup$ – Neil Slater Jul 7 '18 at 6:19
  • $\begingroup$ @NeilSlater Thanks for your comment. I edited the question. Is there any solution for this case? $\endgroup$ – user491626 Jul 7 '18 at 6:35
1
$\begingroup$

There is good news and bad news for you here.

The good news is that yes, you can avoid calculating the action value function $Q(s,a)$. In fact you don't need to calculate any value function, although it may be helpful to calculate the state value function $V(s)$ - and clearly if that is your goal you should use a method that helps with this.

The class of algorithms that you should look into are called policy gradient methods. The simplest algorithm in this class is REINFORCE, and it works directly with a stochastic policy function $\pi(a|s)$ that can be optimised based on sampled episodes. There is no value function estimate in REINFORCE.

If you want to have an estimate for $V(s)$ using policy gradient, you can assess it whilst learning separately. However, it can also be used to augment the gradient estimates in policy gradient. This is how Actor-Critic algorithms work. Recent popular Actor-Critic implementations are A3C and A2C.

Using a policy gradient method like Actor-Critic, you avoid the need to maximise over $a$ for $Q(s,a)$ in order to select a greedy action.

The bad news is that using a policy gradient method with a state value estimate does not remove the need to explore the state/action space in order to learn it. If the action space is large and the environment response to different action values is complex, then finding near-optimal solutions can still be a hard problem.

Whether it is better to use value-based methods like Q-learning, or policy-gradient methods like Actor-Critic depends on features of the problem. In your case, the continuous action space more or less forces you to abandon action value methods that learn $Q(s,a)$, so you don't really have the choice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.