Defining subset of available actions when using ValueIteration

[anachristinaac]

Hi,

I'm trying to implement a problem in which only a subset of all actions is available at each state. I'm doing this by making the return of the get_all_actions() function inside the PolicyModel class dependent on the state, as shown below:

class PolicyModel(pomdp_py.RolloutPolicy):
    def __init__(self, **kwargs):
        super().__init__(**kwargs)

    def sample(self, state):
        return random.sample(self.get_all_actions(state), 1)[0]

    def rollout(self, state, history=None):
        return self.sample(state)

    def get_all_actions(self, state=None, history=None):
        if state is None or state.name == "work":
            return [Action(a) for a in {"rail", "car", "cycle", "wait",
                                        "go-home", "relax", "drive"}]
        else:
            if state.name == "home":
                return [Action(a) for a in {"rail", "car", "cycle"}]
            if state.name == "wait-room":
                return [Action(a) for a in {"wait", "go-home"}]
            if state.name == "train":
                return [Action("relax")]
            if state.name == "light-traffic":
                return [Action("drive")]
            if state.name == "medium-traffic":
                return [Action("drive")]
            if state.name == "heavy-traffic":
                return [Action("drive")]

This doesn't seem to work if I'm using Value Iteration (planner = pomdp_py.ValueIteration(horizon=1, discount_factor=0.9)) to solve the problem. Below is an example of output. In the first step, the action chosen ("wait") is not one of the available ones at the current state ("home"). Then this results in a belief state with zero probability in every state.

==== Step 1 ====
True state: home
Belief: {State: home: 1.0, State: wait-room: 0.0, State: train: 0.0, State: light-traffic: 0.0, State: medium-traffic: 0.0, State: heavy-traffic: 0.0, State: work: 0.0}
Action: wait
Reward: -1000.0
>> Observation: home
==== Step 2 ====
True state: home
Belief: {State: home: 0.0, State: wait-room: 0.0, State: train: 0.0, State: light-traffic: 0.0, State: medium-traffic: 0.0, State: heavy-traffic: 0.0, State: work: 0.0}
Action: rail
Reward: -2.0
>> Observation: train

From what I understood while debugging, the ValueIteration method does not call the sample() function of the PolicyModel, so the get_all_actions() function is always called with the default argument state=None, resulting in all actions being considered as available.

How can I define these different subsets of actions when using ValueIteration then?

Here is the complete script. I'm running it using Python 3.9.6 with version 1.3.3 of the pomdp-py package.

Thank you!

Kind regards,
Ana

[zkytony]

This doesn't seem to work if I'm using Value Iteration (planner = pomdp_py.ValueIteration(horizon=1, discount_factor=0.9)) to solve the problem.

That is expected. ValueIteration requires explicit transition probabilities to be defined, which means for the actions that's not in the valid subset for a given state, you need to explicitly define the transition probability to be 0. I see that you haven't defined the probability function.

Also, if you'd like to use value iteration, I recommend to not use pomdp_py.ValueIteration since it is a naive implementation; Check out the documentation here for using a value iteration with pruning algorithm implemented in pomdp-solve. Here's an example.

[zkytony]

One more reference. This gist contains another style of using pomdp-py that explicitly defines the probabilities, which may be suitable for your situation. https://gist.github.com/zkytony/51d43ee6818375434eb3b84a77a47a5c

[anachristinaac]

Hi,

Thanks for the reply!

That is expected. ValueIteration requires explicit transition probabilities to be defined, which means for the actions that's not in the valid subset for a given state, you need to explicitly define the transition probability to be 0. I see that you haven't defined the probability function.

I thought this was done by the probability() function of the TransitionModel, which I had implemented already. But I guess you mean a function to the PolicyModel, is that correct? I implemented one as shown below:

class PolicyModel(pomdp_py.RolloutPolicy):
    def __init__(self, **kwargs):
        super().__init__(**kwargs)

    def probability(self, action, state):
        available_actions = self.get_all_actions(state)
        if action.name in available_actions:
            return 1/len(available_actions)
        else:
            return 0.0

    def sample(self, state):
        return random.sample(self.get_all_actions(state), 1)[0]

    def rollout(self, state, history=None):
        return self.sample(state)

    def get_all_actions(self, state=None, history=None):
        if state is None or state.name == "work":
            return [Action(a) for a in {"rail", "car", "cycle", "wait",
                                        "go-home", "relax", "drive"}]
        else:
            if state.name == "home":
                return [Action(a) for a in {"rail", "car", "cycle"}]
            if state.name == "wait-room":
                return [Action(a) for a in {"wait", "go-home"}]
            if state.name == "train":
                return [Action("relax")]
            if state.name == "light-traffic":
                return [Action("drive")]
            if state.name == "medium-traffic":
                return [Action("drive")]
            if state.name == "heavy-traffic":
                return [Action("drive")]

I also changed to the pruning algorithm as you suggested:

pomdp_solve_path = os.path.dirname(os.path.abspath(__file__))
pomdp_solve_path = pomdp_solve_path + "/pomdp-solve-5.5/src/pomdp-solve"
planner = pomdp_py.vi_pruning(agent, pomdp_solve_path,
                              discount_factor=0.9,
                              options=["-horizon", "1"],
                              remove_generated_files=False,
                              return_policy_graph=False)

To use this algorithm, I had to change the TransitionModel.probability() function to remove all the non-zero values (I'm using 0.001 instead of zero now). I've tested multiple times, and it seems that in Step 1 the actions are chosen correctly, but I still get an unavailable action being chosen from Step 2 onwards, as shown below ("drive" is the only action available in state "medium-traffic"):

==== Step 1 ====
True state: home
Belief: {State: home: 1.0, State: wait-room: 0.0, State: train: 0.0, State: light-traffic: 0.0, State: medium-traffic: 0.0, State: heavy-traffic: 0.0, State: work: 0.0}
Action: car
Reward: -1.0
>> Observation: medium-traffic
==== Step 2 ====
True state: medium-traffic
Belief: {State: home: 0.0, State: wait-room: 0.0, State: train: 0.0, State: light-traffic: 0.0, State: medium-traffic: 1.0, State: heavy-traffic: 0.0, State: work: 0.0}
Action: relax
Reward: -1000.0
>> Observation: medium-traffic
==== Step 3 ====
True state: medium-traffic
Belief: {State: home: 0.0, State: wait-room: 0.0, State: train: 0.0, State: light-traffic: 0.0, State: medium-traffic: 1.0, State: heavy-traffic: 0.0, State: work: 0.0}
Action: relax
Reward: -1000.0
>> Observation: medium-traffic

I'm using pomdp_py.POUCT to check if the rest of the code makes sense, and POUCT seems to work fine, with the selected actions always in the set of available ones, even with the zero probabilities in the TransitionModel.probability() function. So I'm assuming I'm missing something that is specific for the ValueIteration algorithms.

Is there any other probability() function I should implement? Or anything else you can detect I'm doing wrong, please?

Update script here.

---

One more reference. This gist contains another style of using pomdp-py that explicitly defines the probabilities, which may be suitable for your situation. https://gist.github.com/zkytony/51d43ee6818375434eb3b84a77a47a5c

Thanks for the recommendation! I've tried this code before. I guess the way I'm doing things now seems a bit too complicated for the problem I'm describing, but I'm actually using it to understand how to use the library. After that, I'll move to more complicated problems, to which I believe implementing the classes will give me more flexibility, that's why I'm trying this way now.

---

Thanks for your help!

[zkytony]

Oops, I meant probability() in the TransitionModel and ObservationModel (sorry I didn't look into your linked script). You already did them so that's good.

but I still get an unavailable action being chosen from Step 2 onwards

Hmm, from your config,

planner = pomdp_py.vi_pruning(agent, pomdp_solve_path,
                              discount_factor=0.9,
                              options=["-horizon", "1"],
                              remove_generated_files=False,
                              return_policy_graph=False)

the horizon is set to 1. This may be the reason why only the first action is planned correctly. Note that vi_pruning is an offline planner so everything is precomputed before the execution loop.

and POUCT seems to work fine, with the selected actions always in the set of available ones, even with the zero probabilities in the TransitionModel.probability()

Just to note, POUCT only uses sample, so it's not affected.

[anachristinaac]

Oops, I meant probability() in the TransitionModel and ObservationModel (sorry I didn't look into your linked script).

No worries!

This may be the reason why only the first action is planned correctly. Note that vi_pruning is an offline planner so everything is precomputed before the execution loop.

I've tried this before, and this is not the reason. See below the complete output with an horizon of 10 steps. Please note that even with the horizon correctly defined (line horizon = 10), Step 2 still chooses an action ("rail") not available in the current state ("train"). I've tried other horizons too, and couldn't make it work.

 //****************\\
||   pomdp-solve    ||
||     v. 5.5       ||
 \\****************//
      PID=29578
- - - - - - - - - - - - - - - - - - - -
time_limit = 0
mcgs_prune_freq = 100
verbose = context
stdout = 
inc_prune = normal
history_length = 0
prune_epsilon = 0.000000
save_all = false
o = temp-pomdp
fg_save = false
enum_purge = normal_prune
fg_type = initial
fg_epsilon = 0.000000
mcgs_traj_iter_count = 1
lp_epsilon = 0.000000
end_epsilon = 0.000000
start_epsilon = 0.000000
dom_check = false
stop_delta = 0.000000
q_purge = normal_prune
pomdp = ./temp-pomdp.pomdp
mcgs_num_traj = 1000
stop_criteria = weak
method = incprune
memory_limit = 0
alg_rand = 0
terminal_values = 
save_penultimate = false
epsilon = 0.000000
rand_seed = 
discount = -1.000000
fg_points = 10000
fg_purge = normal_prune
proj_purge = normal_prune
mcgs_traj_length = 100
history_delta = 0
f = 
epsilon_adjust = 0.000000
prune_rand = 0
vi_variation = normal
horizon = 10
stat_summary = false
max_soln_size = 0.000000
witness_points = false
- - - - - - - - - - - - - - - - - - - -
[Initializing POMDP ... done.]
[Initial policy has 1 vectors.]
++++++++++++++++++++++++++++++++++++++++
Epoch: 1...4 vectors in 0.00 secs. (0.00 total) (err=inf)
Epoch: 2...4 vectors in 0.00 secs. (0.00 total) (err=inf)
Epoch: 3...4 vectors in 0.00 secs. (0.00 total) (err=inf)
Epoch: 4...2 vectors in 0.00 secs. (0.00 total) (err=inf)
Epoch: 5...2 vectors in 0.00 secs. (0.00 total) (err=inf)
Epoch: 6...2 vectors in 0.00 secs. (0.00 total) (err=inf)
Epoch: 7...2 vectors in 0.00 secs. (0.00 total) (err=inf)
Epoch: 8...2 vectors in 0.00 secs. (0.00 total) (err=inf)
Epoch: 9...2 vectors in 0.00 secs. (0.00 total) (err=inf)
Epoch: 10...2 vectors in 0.00 secs. (0.00 total) (err=inf)
++++++++++++++++++++++++++++++++++++++++
Solution found.  See file:
	temp-pomdp.alpha
	temp-pomdp.pg
++++++++++++++++++++++++++++++++++++++++
User time = 0 hrs., 0 mins, 0.00 secs. (= 0.00 secs)
System time = 0 hrs., 0 mins, 0.00 secs. (= 0.00 secs)
Total execution time = 0 hrs., 0 mins, 0.00 secs. (= 0.00 secs)
==== Step 1 ====
True state: home
Belief: {State: home: 1.0, State: wait-room: 0.0, State: train: 0.0, State: light-traffic: 0.0, State: medium-traffic: 0.0, State: heavy-traffic: 0.0, State: work: 0.0}
Action: rail
Reward: -2.0
>> Observation: train
==== Step 2 ====
True state: train
Belief: {State: home: 0.0, State: wait-room: 0.0, State: train: 1.0, State: light-traffic: 0.0, State: medium-traffic: 0.0, State: heavy-traffic: 0.0, State: work: 0.0}
Action: rail
Reward: -1000.0
>> Observation: train
==== Step 3 ====
True state: train
Belief: {State: home: 0.0, State: wait-room: 0.0, State: train: 1.0, State: light-traffic: 0.0, State: medium-traffic: 0.0, State: heavy-traffic: 0.0, State: work: 0.0}
Action: rail
Reward: -1000.0
>> Observation: train

[zkytony]

Could you double-check if your transition / observation probabilities are correct (i.e. do the probabilities sum up to 1 for each of Pr(s'|s,a) and Pr(z|s',a))?

Looking at your log, belief update worked (I see it went from home to train which shouldn't have rail as a valid action). So the planner failed - but it looks like it "worked" because it says "Solution found" so I suspect the input to the planner is flawed (i.e. the POMDP file, which was built from the pomdp_py.Agent). Assuming the conversion from pomdp_py.Agent to POMDP file is correct, I think the issue should be in how the Agent was created which is then in whether the probabilities are defined correctly.

[anachristinaac]

Hi, @zkytony,

You were right, the problem was with the models, but not with the probabilities. I finally found a silly typo in the observation and transition models. It didn't break the code, so it wasn't that obvious, but it was causing the weird behaviour. It's now fixed and the actions are being chosen from the correct subsets.

Thank you for your help!