How to compare memory requirements for tabular Q-learning vs deep neural network?

Question

I want to compare the space complexity/memory requirement of tabular Q-learning v.s. deep neural Q-network (DQN). I think DQN would be faster and Q-table has a disadvantage at large table sizes but consider the following case.

A Q-table has the size 14 states *169 actions= 2366 entries and (say) a fully connected DNN whose number of parameters comes out to be like >8000. Space complexity/memory-wise, isn't storing a look-up q-table of 2366 size better than storing 8000 parameters of neural net? I never implemented a DNN before so no idea how much space neural net parameters take.

Answer 1

You don't say, but I suspect from your description, that you have designed the neural network to operate over one-hot-encoding representations of states and actions. Using such a representation offers no benefit whatsoever compared to a simple table. That is because the intended benefit of using neural networks, or any kind of approximation, is generalisation.

It is not possible to generalise results between states and actions, if those states and actions are simply enumerated. If you represent $\mathcal{S}$ as $\{s_0, s_1, s_2 ... s_{13}\}$ and $\mathcal{A}$ as $\{a_0, a_1, a_2 ... a_{168}\}$ to any function, then the best generalisation that can be made are only based on the mean of $Q(s, a)$ for all states or all actions. You cannot use experience gained for $Q(s_0, a_0)$ to say anything about expected return for $Q(s_1, a_1)$. That is true even if $s_0$ and $s_1$ are similar in some way - the representation does not capture that similarity, so the approximator cannot use it.

State and action representation are very important details when adding approximation to reinforcement learning.

To gain generalisation, an approximation scheme needs to have feature data that encapsulates how elements in the space are similar or different to each other. For example, if the 169 actions are arranged on a 13x13 grid, then each action can be represented as a 2-element vector. This will work for approximation if actions that are close to each other in this 13x13 space usually have similar expected returns.

Space complexity/memory-wise, isn't storing a look-up q-table of 2366 size better than storing 8000 parameters of neural net?

Yes, typically neural network parameters are 32-bit floats, which would also a suitable storage type for the q table values.

It is not common to have a neural network use more space to store its parameters than would be required to fully describe the entire function domain that it is approximating. So you are right to find it unwanted/unexpected. The answer to this puzzle is likely to be in your choices for state and action representation.