TabularMDP canonical representations

[markkho]

TabularMDP constructs a transition_matrix and reward_matrix without considering is_terminal(s). This means that it is up to whoever is using those matrices to ensure that terminal states are being handled correctly. An alternative is for the matrices to be constructed such that terminal states always return a reward of 0 and self-loop. I lean towards keeping the original version, but we should be explicit about this.

see 3513789

[markkho]

After discussion with @cgc , it seems like the best policy is to assume that different TabularMarkovDecisionProcess methods are "decoupled" and that the matrix associated with a method cover all possible inputs. That is, we do not selectively fill out the matrix associated with a method based on the behavior of another method.

Concretely, this means that every entry associated with a state, action, and next state in transition_matrix will correspond to .next_state_dist(s, a).prob(ns), even if .is_terminal(s) == True. Similarly, every entry in reward_matrix will correspond to .reward(s, a, ns), even if .next_state_dist(s, a).prob(ns) == 0.0.

This has been implemented in 3db623f. However, the change breaks tests associated with the VaryingActionNumber test domain, since that throws an error if an action not in a state's action set is chosen. Based on the logic of decoupling methods above, this test should be changed so that it accepts actions, even if they can't be taken at a state s according to .actions(s). @cgc , since you originally wrote those tests what do you think?

[cgc]

Yeah this seems to be a pretty tricky one... I can definitely see how this does break some of the separation of concerns that come from entirely decoupling the matrices. One of my arguments for decoupling was to better support changes in the reward / termination functions; I often have to change these, but rarely change the state/action spaces. The decoupling makes it easy to partially change an MDP without reallocating the entire transition matrix. Do we think changing state/action spaces would be a common use-case?

A very practical consideration is I came to these implementations after some rounds of optimization (detailed in 724dc99); though it's not broken out in the commit message, avoiding enumerating state & next state was one of the two changes that led to a 50% performance improvement.

It might ultimately make more sense for me to keep a local copy/subclass of TabularMDP that bakes in my assumptions; might otherwise just be too hard to fit my (very particular) usecase into a fully generic copy.

[markkho]

Notes

• separate canonical transition/reward function from ergonomic versions
• compilation target for TabularMDPs: _transition_matrix and _reward_matrix <- canonical representation passed to algorithms "mathematical metal"
• can have wrapper for functions to tabularize (add in default arguments/variable spaces)
• formal mdp:

class FormalMDP(MDP):
  def __init__(self, mdp):
    self.mdp = mdp
  def initial_state_dist(self):
    ? return self.mdp.initial_state_dist()
  def is_terminal(self, s):
    return all(self.next_state_dist(s, a).prob(s)==1 for a in self.actions(s))
  def next_state_dist(self, s, a):
    if (
      a not in self.mdp.actions(s) or
      self.mdp.is_terminal(s)
    ):
      return deterministic(s)
    return self.mdp.next_state_dist(s, a)
  def reward(self, s, a, ns):
    if (
      # This should not be self.mdp.next_state_dist
      self.next_state_dist(s, a).prob(ns) == 0 or
      self.mdp.is_terminal(s)
    ):
      return 0
    if a not in self.mdp.actions(s):
      return -float('inf')
    return self.mdp.reward(s, a, ns)

TODO:

• figure out how to implement canonical mdp representation
• separate out decoupled semantic componenets

[cgc]

I'm still feeling pretty good about our conversation on this the other day. I do think the usability issues with the current MDP reward/transition matrices have to do with the abstractions (is_terminal, per-state actions()) that we've layered into our MDP implementation. I think the way to deal with these issues is to make it easy to deal with the MDP with or without these abstractions layered in. The concrete use-cases we've talked about are 1) bugs we've accidentally run into when using MDP reward/transition matrices for transfer learning and 2) wanting to centralize/reuse the ways policy iteration and value iteration implement/encode these abstractions.

As far as potential solutions go, we'd make the reward/transition/etc matrices of TabularMDP to minimally engage with the abstractions we've added / be decoupled from other functions, then add one of the below:

1. Add new properties for reward/transition matrices to TabularMDP that bake in the abstractions; these would be directly used by PI/VI.
2. Make MDPs have a superclass like the above FormalMDP; this gets tricky b/c the subclass can choose when/how to call the superclass, so this could potentially be the most difficult to implement, and might have a pretty large impact on existing code.
3. Make an adapter/wrapper class like the above FormalMDP; this could be pretty elegant depending on details. I like that it's a pretty clear formalization of the abstractions we've added. Can also probably get the reward/transition matrices by simply subclassing TabularMDP. the MDP class could even have a canonicalized() method that returns a wrapped instance if we really want to bake it in; otherwise, we could just have VI/PI do the wrapping/calling. I think the transition/reward functions as above would work well, but we'd have to think about the actions/is_terminal behavior.

[markkho]

I've come to agree with you and like option 3 the most! I think for now, we should have this be all behind the scenes (e.g., have the planning algs formalize the mdp or have a "private" method like _formalmdp()).

[markkho]

Other edge cases to handle with a canonical representation:

• if there are no actions at a terminal state VI and PI can break
• if there are no actions at a state, throw an error

[cgc]

Not sure if this is a priority anymore, but closed the associated PR for now #49

[markkho]

Sounds good - I'd like to revisit this soon though.