# Reinforcement learning of a policy for multiple actors in large state spaces

I have a real-time domain where I need to assign an action to N actors involving moving one of O objects to one of L locations. At each time step, I'm given a reward R, indicating the overall success of all actors.

I have 10 actors, 50 unique objects, and 1000 locations, so for each actor I have to select from 500000 possible actions. Additionally, there are 50 environmental factors I may take into account, such as how close each object is to a wall, or how close it is to an actor. This results in 25000000 potential actions per actor.

Nearly all reinforcement learning algorithms don't seem to be suitable for this domain.

First, they nearly all involve evaluating the expected utility of each action in a given state. My state space is huge, so it would take forever to converge a policy using something as primitive as Q-learning, even if I used function approximation. Even if I could, it would take too long to find the best action out of a million actions in each time step.

Secondly, most algorithms assume a single reward per actor, whereas the reward I'm given might be polluted by the mistakes of one or more actors.

How should I approach this problem? I've found no code for domains like this, and the few academic papers I've found on multi-actor reinforcement learning algorithms don't provide nearly enough detail to reproduce the proposed algorithm.

• (+1) this is a very interesting problem. I am curious: Which domain ? Can you tell us some more about the actors and objects (what are they, robots picking cans) ? It may not matter for the question itself, but as I said, I am very curious ;). – steffen Jan 24 '12 at 15:58
• It's a physical warehouse optimization task. Various robots (i.e. actors) have to decide which of N different objects to move, and to where. By "environmental factors", I mean how close the actor is to the object and each proposed target location, how close the object itself is to the target location, how close the target location is to a wall, etc. They're given a limited amount of time to think and react (so no batch analysis of data), and only get a simple floating-point reward feedback of [0:1]. Not exciting stuff, but it's a massive domain nonetheless. – Cerin Jan 25 '12 at 3:14
• For other readers: question on stackoverflow – steffen Jan 26 '12 at 15:45
• Surely the actors and objects are only in specific locations at any one time? This would mean that the action space is actually highly constrained - an actor can either move itself or move itself + the object. The action space is therefore only as large as the number of directions that you allow the actor to move in (e.g. 4 + 1 for standing still, or 8 + 1 if you allow diagonal moves). If you allow movements in any direction then of course you have a continuous action space and the problem is much harder. – tdc Feb 2 '12 at 10:19
• Also I wouldn't say that 1000 locations is a "huge" state space these days ... – tdc Feb 2 '12 at 10:20

I think there are two problems here:

1. The huge state space,
2. The fact that many agents are involved.

I have no experience with (2), but I guess if all the agents can share their knowledge (e.g. their observations) then this is no different than treating all different agents as a single agent, and learn sth like a "swarm policy". If this is not the case, you might need to search for "distributed reinforcement learning" or "multi agent reinforcement learning".

For (1), you might need to find a representation of the action/state space which is more compact. Some ideas follow.

You say that there are 1000 locations. Does it make sense to try to find a low dimensional embedding for them? E.g. are you able to find a suitable distance measure between them? If so, you can use multidimension scaling to embed them in a continuous, k-dimensional space with $k << 1000$.

Another approach would be to use policy gradients. The idea is that you use a parametrized policy, $$\pi: \Theta \times S \mapsto A$$

where each $\theta \in \Theta$ is a point in parameter space which defines the policy. This policy can then be optimized with gradient-based methods.

An example would be that you have a neural network which takes the current state as an input, and directly puts out "move object i to location j". You will not need to enumerate all possible actions explicitly.

Nevertheless, I doubt this approach will work without serious work. Even when using PGs, you will need to reduce your action/state space.