Minimizing Maximum Regret in Commitment Constrained Sequential Decision
  Making
  In cooperative multiagent planning, it can often be beneficial for an agent
to make commitments about aspects of its behavior to others, allowing them in
turn to plan their own behaviors without taking the agent's detailed behavior
into account. Extending previous work in the Bayesian setting, we consider
instead a worst-case setting in which the agent has a set of possible
environments (MDPs) it could be in, and develop a commitment semantics that
allows for probabilistic guarantees on the agent's behavior in any of the
environments it could end up facing. Crucially, an agent receives observations
(of reward and state transitions) that allow it to potentially eliminate
possible environments and thus obtain higher utility by adapting its policy to
the history of observations. We develop algorithms and provide theory and some
preliminary empirical results showing that they ensure an agent meets its
commitments with history-dependent policies while minimizing maximum regret
over the possible environments.
