1
$\begingroup$

I am trying to implement a Q-learning algorithm for energy optimization. It is a finite MDP with states represented as 6 dimensional vectors of integers. The number of discrete values in each index of the state vector varies from 24 to 90.

The action space varies from state to state and goes up to 300 possible actions in some states, and below 15 possible actions in some states.

If I could make some assumptions (just for the purpose of testing the model), I could reduce the states to about 400 and actions to less than 200.

How can I construct a Q-table for such an environment? I am not sure how to approach this in Python, how to prevent the table containing lots of impossible state/action combinations, or prevent the agent trying to take those unwanted actions.

$\endgroup$
13
  • $\begingroup$ It occurs to me that perhaps you are confusing time step id with state identity? E.g. the symbol $s_1$ could mean the first state in a set of (in your case 24) states, or it could mean the state at $t=1$. Your mention of a horizon and a "state vector" implies that really you mean the latter, because if you really had 24 states, there would be no need for any vector of information. In which case, could you explain how complex that vector is? It may be too much to use tabular RL $\endgroup$ Jul 16, 2019 at 17:34
  • $\begingroup$ Okay I see. So what I have is that there is excel data showing state variables like time and corresponding power demand and grid tariff, which is to be read at every time step, all through to the horizon T (24 hours). I decided to have all those in one state vector, so there are up to 24 of them. But since I am using batteries (2 of them, and I do not want to lump their parameters), I decided to append the energy levels of each to the state vector (they are vital in deciding the optimal action). An action vector contains power values committed to the load and the two batteries. $\endgroup$
    – EArwa
    Jul 16, 2019 at 20:21
  • $\begingroup$ Hence, the next state is gotten by reading the static state variables from the excel table, then updating and appending to that vector the new battery energy. I decided to deal with optimization constraint by ensuring all possible action vectors allowed are those that are within constraints, so that the agent learns within the boundaries (deterministic environment). $\endgroup$
    – EArwa
    Jul 16, 2019 at 20:25
  • $\begingroup$ OK. Could you give a rough indication of number of dimensions per state vector and how many discrete values per dimension? If continuous variables, how realistic is it to use discrete values for them (e.g. would it lose really important details of the problem)? $\endgroup$ Jul 16, 2019 at 20:43
  • $\begingroup$ Wow! Your questions have made me understand my problem even much better. So the the state vectors have 6 elements. The first four elements of the state vector has 24 discrete values (can be 48 or 96 depending on the choice of time steps), while the next two range from 10 to 90, discretized in steps of 1 (to fit the load which takes integer values) and from 10 to 60 (also discretized in steps of 1). Now each state has a different number of possible actions. $\endgroup$
    – EArwa
    Jul 17, 2019 at 9:35

1 Answer 1

2
$\begingroup$

It is a finite MDP with states represented as 6 dimensional vectors of integers. The number of discrete values in each index of the state vector varies from 24 to 90.

The action space varies from state to state and goes up to 300 possible actions in some states, and below 15 possible actions in some states.

In combination, this could be over a billion state/action combinations. It is likely to be too much for running a tabular method over. The dynamic actions, changing depending on what the state is are not an issue, but the total size of such a table probably will be.

If I could make some assumptions (just for the purpose of testing the model), I could reduce the states to about 400 and actions to less than 200.

This is a much more tractable number for creating a table. Your total number of records will be at most 80,000.

There are a couple of things worth looking at in more detail:

Number of training examples needed

With a tabular method, as well as constructing the table, you need to collect data for each possible state/action combination. If there is some randomness in the environment, then you need to collect data from each possible state/action combination multiple times. For a table with size 80,000 this might be very fast and easy if you have a fast simulation of the environment. However, it might still not be a feasible size if you can only collect information from a single real environment and the time step represents a day . . .

You will need to check your own numbers to figure out whether this is an issue.

Perhaps even the billion plus items for your full description is not an issue if you have a fast computer and lots of memory to store the table.

Dealing with ragged data in a table

You don't have to do this. If you have enough memory spare and want to take the easy route, you could just use a tensor description (i.e. allow all values in each dimension, and enumerate them from 0 to whatever size). See next section for how you should limit action choice.

However, it may be more efficient to do something about the ragged data.

The simplest way to do this is to generate a unique ID for each allowed state vector, and use that to reference a value in a nested hash structure, e.g. a Python dict of dicts.

A very simple ID generator would be to concatenate your state vector and action labels into a list, then convert that into a string using some kind of join function. Example in Python:

# Empty Q table
q = dict()

# Define an example state, action and value
state = [20,12,56,9,76,30]
action = 176
value = -2.4

# Store an example state, action and value

# This state to state_id conversion should be a re-usable function
state_id = '/'.join([str(x) for x in state])
# Example state_id is '20/12/56/9/76/30'

if state_id in q:
  q[state_id][action] = value
else
  q[state_id] = {action: value}

The easiest way to manage the Q table with this approach is to add entries as and when you need them. Don't pre-populate with zeros, only write action values when they are needed by your agent. That will mean that you only create table entries for state, action pairs that exist.

Filtering action values

You will need code, that you consider to be part of the environment, that knows which actions are valid depending on the current state. This code could return the list of all possible actions. For instance you might define a function allowed_actions(state). You then use that list when working with the Q table:

  • When looking for a maximising action to drive a policy, look up the whole dictionary of action to value (in q[state_id] and pick the max one)

  • When you reach a new state that you have not seen before, it may be convenient to populate all possible actions from that state with zeros. Prototype Python code for doing that might look like this:

state_id = '/'.join([str(x) for x in state])
if not state_id in q:
  q[state_id] = { action: 0 for action in allowed_actions(state) }
$\endgroup$
17
  • $\begingroup$ Okay, I see. An episode consists of 24 (48 or 96 depending on size time steps) time steps, and at the end of each episode, the agent gets to the original state; but depending on the actions taken, it may or may not visit the states visited in the first episode. So you mean that every time step, I need a statement to check if the state exists in the dictionary? $\endgroup$
    – EArwa
    Jul 18, 2019 at 7:02
  • $\begingroup$ @EArwa: Yes you will need to check every time you want to use the Q table, whether you have defined the entry, otherwise you will get errors. How you manage the Q table storage is not directly related to how experience is split into episodes. $\endgroup$ Jul 18, 2019 at 7:58
  • $\begingroup$ If I get what you are saying; you mean that I will need a dictionary of states, and each state will have the list of actions. Does that mean that for the values associated with actions in those states, I will have another dictionary within the dictionary so that each action has its Q-value in the state it was taken? $\endgroup$
    – EArwa
    Jul 18, 2019 at 14:13
  • $\begingroup$ No you only need one state index and one action index in the Q table lookup, it does not need to go deeper. q[state_id][action_id] = value is enough to represent $Q(s,a) \rightarrow \mathbb{R}$ as a table $\endgroup$ Jul 18, 2019 at 14:26
  • 1
    $\begingroup$ I am very grateful for your help in the process. I managed to implement the algorithm and published two papers from it. $\endgroup$
    – EArwa
    Mar 18, 2020 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.