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 dict
s.
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) }