Exploring an unexplored domain by parallel reinforcement
View Patent ↗A computer-implemented method for exploring, by a table-based parallel reinforcement learning, PRL, algorithm, an unexplored domain comprising a plurality of agents and states, the unexplored domain represented by a state-action space. The method includes the steps performed by one or more of the plurality of agents receiving an assigned partition of the state-action space represented by a table; and executing during a plurality of episodes actions for states within the partition. An action transits a state; and granting to a transited state a reward; and exchanging state-action values with other agents of the plurality of agents in the domain; and updating the table.
1. A computer-implemented method for exploring, by a table-based parallel reinforcement learning, PRL, algorithm, an unexplored domain comprising a plurality of agents and states, the unexplored domain represented by a state-action space, the method comprising the following steps performed by one or more of the plurality of agents:
receiving an assigned partition of the state-action space represented by a table; and
executing during a plurality of episodes actions for states within the partition, wherein an action transits a state; and
granting to a transited state a reward; and
exchanging state-action values with other agents of the plurality of agents in the domain;
updating the table;
subdividing the partition into subpartitions based on the number of agents, wherein a subpartition comprises a subset of one or more states, by ordering the one or more states of the subpartitions based on a number of times a respective state is transited to in a descending order; and
deriving a local affinity policy based on actions transiting the agent to states within its respective partition.
2. The computer-implemented method according to claim 1 , further comprising the step of:
when an agent executes an action transiting to a state outside the assigned partition, communicating with an agent having the state within its assigned partition thereby exchanging the state-action value.
3. The computer-implemented method according to claim 1 , further comprising the steps of:
partitioning after a predefined number of episodes the state-action space based on the number of agents and the number of states in the domain thereby obtaining a number of partitions; and
assigning a respective partition to a respective agent.
4. The computer-implemented method according to claim 3 , wherein the assigning is performed when the agent is configured to store the associated table.
5. The computer implemented method according to claim 3 , wherein the respective partition comprises a state firstly transited to by the respective agent and for which no action has been taken.
6. The computer-implemented method according to claim 1 , wherein the number of times a respective state is transited to is normalized by the total number of transitions.
7. The computer-implemented method according to claim 1 , wherein the exchanging further comprises:
exchanging the state-action values of the ordered subpartitions comprising states below a predefined threshold.
8. The computer-implemented method according to claim 1 ,
wherein the PRL algorithm is a q-learning algorithm; and
wherein the state-action space is represented by a q-table.
9. A networking device configured to perform the steps by the agent according to claim 1 .
10. A controller configured to perform the partitioning and assigning according to claim 3 .
11. A system comprising a networking device configured to perform the steps by the agent and a controller according to claim 3 .
12. A non-transitory computer-readable data carrier having stored thereon a computer program comprising instructions which, when the program is executed by a computer, cause the computer to carry out the method according to claim 1 .