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))


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
  1. 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?

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.


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.