# Q-learning with a state-action-state reward structure and a Q-matrix with states as rows and actions as columns

I have set up a Q-learning problem in R, and would like some help with the theoretical correctness of my approach in framing the problem.

Problem structure For this problem, the environment consists of 10 possible states. When in each state, the agent has 11 potential actions which it can choose from (these actions are the same regardless of the state which the agent is in). Depending on the particular state which the agent is in and the subsequent action which the agent then takes, there is a unique distribution for transition to a next state i.e. the transition probabilities to any next state are dependant on (only) the previous state as well as the action then taken.

Each episode has 9 iterations i.e. the agent can take 9 actions and make 9 transitions before a new episode begins. In each episode, the agent will begin in state 1.

In each episode, after each of the agent's 9 actions, the agent will get a reward which is dependant on the agent's (immediately) previous state and their (immediately) previous action as well as the state which they landed on i.e. the agent's reward structure is dependant on a state-action-state triplet (of which there will be 9 in an episode).

The transition probability matrix of the agent is static, and so is the reward matrix.

I have set up two learning algorithms. In the first, the q-matrix update happens after each action in each episode. In the second, the q-matrix is updated after each episode. The algorithm uses an epsilon greedy learning formula.

The big problem is that in my Q-learning, my agent is not learning. It gets less and less of a reward over time. I have looked into other potential problems such as simple calculation errors, or bugs in code, but I think that the problem lies with the conceptual structure of my q-learning problem.

Questions

I have set up my Q-matrix as being a 10 row by 11 column matrix i.e. all the 10 states are the rows and the 11 actions are the columns. Would this be the best way to do so? This means that an agent is learning a policy which says that "whenever you are in state x, do action y" Given this unique structure of my problem, would the standard Q-update still apply? i.e. Q[cs,act]<<-Q[cs,act]+alpha*(Reward+gamma*max(Q[ns,])-Q[cs,act]) Where cs is current state; act is action chosen; Reward is the reward given your current state, your action chosen and the next state which you will transition to; ns is the next state which you will transition to given your last state and last action (note that you transitioned to this state stochastically). Is there an open AI gym in R? Are there Q-learning packages for problems of this structure?

## 1 Answer

The problem as you describe it is close to the simplest setup you can get for a RL problem (stationary distributions everywhere, sufficiently small state and action spaces for tabular RL to be feasible, etc.

The Q-learning update rule as you described it also looks correct.

The only somewhat unusual thing that comes to mind from your description is this bit:

Each episode has 9 iterations i.e. the agent can take 9 actions and make 9 transitions before a new episode begins.

This means that "time" is a relevant property of your state-space. Suppose that your state-space is a grid, and your agent has 4 actions to move in the 4 Up/Down/Left/Right. I realise this is different from your description, but this is easier to understand / "visualize" in your head. Suppose that there is a small reward 1 step to the left, and a very big reward 2 steps to the right.

In exactly this same "state", the optimal action depends on how much time you have left / how many steps you have already taken; if the episode terminates after one more action, your agent won't have time to pick up the big reward 2 steps to the right anymore, so the optimal action will be to move to the left. If there is time left more two or more actions, the optimal action will probably be to move to the right and pick up the big reward instead. So, this implies that "time spent" or "time left" should be included in your state-space representation.

The most obvious way to do this is to simply multiply the size of your state space by 9. For every state you have right now, you'll get:

• A copy for the case where there are 9 actions remaining to take
• A copy for the case where there are 8 actions remaining to take
• ...
• A copy for the case where there is 1 action remaining to take

I don't think you need one for the case with 0 remaining actions, because you don't need Q-values for those states.

This will increase the size of your state-action space (and therefore the size of your table of Q-values) from 10 x 11 = 110 to 9 x 10 x 11 = 990. That's obviously a bit of an increase, but... probably should still be fine on modern hardware? You'll have to try and see how it works for you, it also depends on how much computation time you have obviously.

Is there an open AI gym in R? Are there Q-learning packages for problems of this structure?

These questions I'm not sure about, I've never done any Reinforcement Learning in R.