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.
 A: I think there are two problems here:


*

*The huge state space,

*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.
