Negotiable Reinforcement Learning for Pareto Optimal Sequential Decision-Making
It is commonly believed that an agent making decisions on behalf of two or more principals who have different utility functions should adopt a Pareto optimal policy, i.e. a policy that cannot be improved upon for one principal without making sacrifices for another. Harsanyi's theorem shows that when the principals have a common prior on the outcome distributions of all policies, a Pareto optimal policy for the agent is one that maximizes a fixed, weighted linear combination of the principals' utilities. In this paper, we derive a more precise generalization for the sequential decision setting in the case of principals with different priors on the dynamics of the environment. We refer to this generalization as the Negotiable Reinforcement Learning (NRL) framework. In this more general case, the relative weight given to each principal's utility should evolve over time according to how well the agent's observations conform with that principal's prior. To gain insight into the dynamics of this new framework, we implement a simple NRL agent and empirically examine its behavior in a simple environment.
** update ** I really enjoyed reading this paper, however I do not change my rating since the authors' response as well as the other reviews confirm the problems raised in mine. The first point is shared with reviewer 2: the proofs must be integrated into the paper, and the authors agree. The second point, also present in the second review, concerns how to define players' beliefs in practice: the authors propose to give adequate references dealing with this problem. Finally, I am not convinced by the authors' response to the use of the term "reinforcement learning".  Their answer includes the word "Bayesian" which indeed seems to me more appropriate for the work they propose.  ** summary ** In this paper the authors formalize the situation where two entities choose to cooperate sequentially in uncertainty  without having the same criterion to optimize or the same model for the considered system. The mathematical models of each entity are probabilistic, Markov in time,  partially observable and share the same actions and observations. After an introduction of the type of situation considered using a simple example of cake sharing,  the entities' models of the system are defined as POMDPs.  The definition of an Pareto-optimal policy is also given explicitly.  A first result (Lemma 2.) makes it possible to identify all the optimal policies  based on the expectations of gain of the entities under these policies and arbitrary weights. From this result and the definition of a POMDP having the weights mentioned above  as initial belief on the true model, the main result of this paper (Theorem 4) is derived. This result makes it possible to calculate the probability distribution on the actions  at each stage of the process (the Pareto-optimal strategy). The authors point out that optimization favours the entity whose model best explains  the observations obtained over time, which is verified in the following experimental section. The application proposed in the experimental part sets up an agent on a grid.  Each of the entities wants the agent to reach a different grid cell.  One entity believes that the system is deterministic,  while the other believes that agent transitions are random.  Simulations, governed by each model, are performed, described and explained.  ** quality ** This paper is well introduced, ideas are properly developed and interesting results are obtained. I personally find it interesting that entities have an interest in providing a model  that explains reality well (observations) because it eliminates the problem of cheating  (providing a model that one does not believe in order to maximize one's own utility  knowing the calculations made by the jointly-owned agent).  However, I find it extremely unfortunate that the proofs of the two main results  do not appear in the paper but only in the supplementary materials. As noted in the conclusion, "it employs only basic facts about convexity and linear algebra" thus the authors could at least have provided a sketch of proof  in order to make their work more self-contained.  Moreover it seems that there is a problem of vocabulary with this paper.  Since the models are known in advance and the actions are selected  from calculations based on these models  and not on estimates based on rewards received during tests,  this work is not part of Reinforcement Learning  but part of the domain of sequential decision making in uncertainty.  Finally this paper exceeds the page limit (two extra lines).  These three points must be changed if the paper is accepted.  ** clarity ** I found this paper fairly easy to read and understand. However the following remarks should be taken into account.  page 4:  The formalization of the POMDP model is associated with  (Smallwood "The optimal control of partially observable Markov processes over a finite horizon."  Operations research 1973) rather than  (Russel 2003).  < P( o_i | s_i ) > P( o_{i+1} | s_{i+1} ) Otherwise, no observation for s_{n+1}. Usually, i=0:n, no observation for s_0, but an initial belief b_0)  < P( s_{i+1} | s_i a_i ) > P( s_{i+1} | s_i, a_i )  < e.g. > \textit{e.g.}  page 5,6: The prior distribution is often call "initial belief".  page 7: < Figure > Figure 1.  The design of the point-based algorithms for POMDP solving is associated with  (Pineau "Point-based value iteration: An anytime algorithm for POMDPs." IJCAI 2003) rather than  (Ross 2008).  page 8: < is shown in the top/bottom frame > is shown in the right/left frame  ** originality ** To the best of my knowledge this paper is the first to propose a solution  for calculating optimal policies in the context where competing or cooperating entities  have a different modeling of the system. The authors have done a good bibliographical work to position their study  in the relevant literature. However, work has also been carried out with different models of uncertainty. Indeed entities may not be able to provide precise probabilities  about the system under consideration and this should be mentioned. The study is limited to the case where the entities  have a very precise guess about how works the system.  There are other models taking into account this imprecision  which is unfortunately often present in practice. For example work was produced for planning under Knightian Uncertainty, (Trevizan "Planning under Risk and Knightian Uncertainty." IJCAI 2007), with Dempster-Shafer belief Theory (Merigo "Linguistic aggregation operators for linguistic decision making  based on the Dempster-Shafer theory of evidence." International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 2010), with Possibility Theory (Drougard "Structured Possibilistic Planning Using Decision Diagrams" AAAI 2014), and with Imprecise Probability Theory (Itoh "Partially observable Markov decision processes with imprecise parameters."  Artificial Intelligence 2007). Some of these references should be cited since this model is intended to work in practice.  ** significance ** The theoretical and application results are very interesting and make this work quite significant. It would be much more so if the proofs were present and the applications more diversified. Indeed the application is a problem with very few states and the entities' models of the system  are only MDPs and not POMDPs.