1
$\begingroup$

When the number of states in the Q-learning is large, we can refer to approximate Q-learning, but what should we do when we have a large number of actions?

$\endgroup$

2 Answers 2

1
$\begingroup$

one of the downsides associated with the $Q$-Learning algorithm is that it must initialize a value $Q(s,a)$ for every $s\in S$ and every $a\in A$. If either one of your action space $A$ or state space $S$ is to large, I'd suggest approximating $Q$ instead

$\endgroup$
3
  • $\begingroup$ I have three agents, each of which can have 20 actions, which can be combined into 20^3=8000 actions. How can I limit this? $\endgroup$
    – znb
    Commented Nov 7, 2022 at 3:14
  • $\begingroup$ When the number of states is large in the approximate Q-learning, we describe the state by defining the feature. How can the approximate Q-learning be used when the number of actions is large? Is there an example of this on the internet? $\endgroup$
    – znb
    Commented Nov 7, 2022 at 3:19
  • $\begingroup$ @znb Can you please include this info in your original question? It may be a good idea to quantify "too many actions". 20 possible actions don't seem too many. $\endgroup$
    – nbro
    Commented Dec 11, 2022 at 16:19
0
$\begingroup$

When the number of actions becomes large, in Q-learning you may hit a major sticking point. The Q-learning training process, and the trained agent both require you to calculate

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

and that requires evaluating $Q(s,a)$ for each possible action. Which becomes more expensive to compute when there are more actions. At some number of actions, it will start to become inefficient and eventually infeasible at an even higher number. There are no fixed numbers to assess for this, because it will depend on other factors.

The usual way to address this is to use a different, parametric, policy function, and to optimise that more directly (you may also track the value function to help with estimating returns efficiently). That means not performing Q learning anymore, but typically:

  • Policy gradient methods like REINFORCE
  • Actor-critic methods like A2C or DDPG. Actor-critic methods are a combination of policy gradient and value-based methods

Note this does not solve the related problem of exploration and needing to experience all possible actions. Sometimes this resolves OK in large action spaces because action descriptions can be arranged such that similar actions are near each other and the policy function designed to focus on more similar actions as it improves, taking advantage of approximation. But if there are lots of radically different actions, then the problem may require a more brute force approach - at least for statistical learners.

$\endgroup$

You must log in to answer this question.

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