How to create a Q-Learning agent when we have a matrix as an action space?

I have a 2-dimentional matrix as an action space, the rows being a resource to be allocated, and the columns are the users that we will allocate the resources to. (I built my own RL environment)

The possible actions are 'Zero' or 'One'. One if the resource was allocated to the user, Zero if not.

I have a constraint related to the resource allocation, which states that each resource can be allocated to one user only, and the resource should only be allocated to users who have requested a resource to be allocated to them, and that would be the state space which is another matrix.

A penalty would be applied if the agent violates the constraints and the episode would end and the reward would equal the penalty. Otherwise, the reward would equal the sum of all the users that were satisfied with the allocation.

I am struggling with the implementation. The agent starts by exploring, then little by little it starts exploiting. When it gets to be more exploitative, I've noticed that the action matrix's values are all set to 'One', and the penalty always has the same value from episode to episode.

• How does the state space evolve? If it is fixed for an episode, or changes independenty of actions taken, then this seems more like a contextual bandit scenario than full RL. It may also be better resolved as a constraint optimisation problem using a different tool to RL, so could you clairfy whether the point here is to solve the problem or learn RL? – Neil Slater Oct 17 '20 at 15:45
• could you give an example ? Initial data and optimal solution. – pasaba por aqui Oct 17 '20 at 18:06

I was thinking this strategy may work.

So, Q-learning takes vector input as state representation let's say your vector has n dimensions i.e. [$$n_0$$, $$n_1$$, $$n_2$$,..., $$n_{n-1}$$]

Now, from my interpretation you want to populate a matrix with 0 and 1's given the state vector but action-space has a high complexity e.g. an 8*8 matrix has 64 cells i.e. $$2^{64}$$ possible actions if you want the action to be a matrix.

I suggest this:

Fill each cell, one at a time. i.e. Your agent has only two possible action 0 and 1. To indicate to your agent that you are at a specific cell, concatenate the row and column number to the state vector before passing it as input to the Q-learning agent.

Example:

If you original state-vector is [55, 22, 100, 4] and you have to fill cell at position (10, 30) of the matrix, the state-vector should be modified as follows: [55, 22, 100, 4, 10, 30].

I'm not sure of the sample-efficiency of this approach though.