1
$\begingroup$

I never saw any rule of thumb as to what size is said as large for a q-table but I have a Q-table with like 2500 entries. Is it considered large for a tabular approach? Anyone from experience can answer maybe. I assume I can visit all state-action pairs enough times but is it efficient in terms of space complexity/memory? Or is a deep neural network required?

I asked a related connected question, in case anyone wants to answer this current question better w.r.t that question context.

$\endgroup$

1 Answer 1

2
$\begingroup$

There a couple of "rules of thumb" you might apply to decide whether a Q table is large enough that some kind of approximation would help:

  • Does it fit into memory?

  • Does the rate of gathering experience mean that the agent can reasonably sample enough from each relevant state/action pair to assess policies?

For a state/action space of 2500, it should trivially fit into memory on any modern device, even if you need to use some kind of string description of the states and actions, using them as keys to a dictionary lookup of value. Even if you are short of space in some embedded device, the space required by code for approximation is probably larger than the table.

In my experience I would rate the state/action space of 2500 as very small. If you can simulate the environment on a computer, then you could reasonably expect to find the optimal policy in under a second. For fast simulations, or with full models using value iteration, Q tables with millions of values to calculate may be feasible.

However, you have not stated what it takes to sample a time step (measuring start state, action, reward, next state) in your environment, or how long you have to run the training process. This could still make a difference in how you want to represent the action value function.

$\endgroup$

You must log in to answer this question.

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