Limits and constraints for Q-learning

Question

I have simple implementation of Q-learning algorithm and I'm trying to run it on

States space size = 36865
Actions space size = 25

So my resulting Q-table is basically 1 million items table.

1. Is there a definition for problem sizes (small/medium/large) based on action/space size and corresponding algorithms which fits best for those

Using implementation below I'm wondering

s_S = 36865
s_A = 25

alpha = 0.1  # learning rate
gamma = 0.9  # discount factor
eps = 0.4  # exploration factor
Q = np.zeros(shape=(s_S, s_A))

EPOCHS = 10

for i in range(EPOCHS):
    # reset env for each epoch
    agent = Agent(env=env)
    s = 0  # starting state
    while s is not None:  # rollout
        a = get_next_action(agent, Q, s, eps)

        r, s_ = agent.take_action(a, s)
        max_q = maximize_q(agent, Q, s_)  # maximize Q for the next state

        Q[s, a] = alpha*(r + gamma*max_q - Q[s, a])

        s = s_

policy = extract_policy(agent, Q)
# evaluate agent behaviour under the policy

2. Can I run N threads in parallel and share Q table between them? Will this approach converge or will I end up in a state with corrupted Q table? Is there any other way to speed up process for such a huge table?

Answer 1

There is no definition of how big a "large" state space is. That being said, a table with 1 million Q values is too large.

Instead of using the table lookup as an exact Q function, you should use function approximation with number of parameters $k << |\cal{S}|\!\times\!|\cal{A}|$. This could be something as simple as state aggregation (treat many states as one), linear function approximation, or nonlinear approximation with a neural network.

If you do some kind of function approximation, instead of updating the Q value directly, you'll update your function parameters.

$$\left.\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha\left[r+\gamma \max_{a'} \hat{Q}(S_{t+1},a';\mathbf{w}_t) - \hat{Q}(S_t,A_t; \mathbf{w}_t)\right]\nabla_{\mathbf{w}_t}\hat{Q}(S_t,A_t; \mathbf{w}_t)\right.$$

I recommend reading Chapter 9 of Sutton and Barto's Intro to RL book for more about function approximation in RL.

And you absolutely can speed up learning by having parallel agents share information! I don't know the specifics, but I wouldn't be worried about corrupted shared data. I'm pretty sure Python would handle a mutex or something for that.