In this paper, we present a link between preference-based and multiobjective sequential decision-making. While transforming a multiobjective problem to a preference-based one is quite natural, the other direction is a bit less obvious. We present how this transformation (from preference-based to multiobjective) can be done under the classic condition that preferences over histories can be represented by additively decomposable utilities and that the decision criterion to evaluate policies in a state is based on expectation. This link yields a new source of multiobjective sequential decision-making problems (i.e., when reward values are unknown) and justifies the use of solving methods developed in one setting in the other one.
A reinforcement learning problem is usually defined using the Markov Decision Process (MDP) model. A standard MDP @cite_3 is defined as a tuple @math where: @math is a finite set of states, @math is a finite set of actions, @math is a transition function with @math being the probability of reaching state @math after executing action @math in state @math , @math is a reward function with @math being the immediate numerical environmental feedback received by the agent after performing action @math in state @math . In this framework, a @math -step history @math is a sequence of state-action: where @math and @math . The value of such a history @math is defined as: where @math is a discount factor. A policy specifies how to choose an action in every state. A deterministic policy @math is a function from the set of states to the set of actions, while a randomized policy @math states the probability @math of choosing an action @math in a state @math .
@cite_3
2119567691
Consider the problem of approximating the optimal policy of a Markov decision process (MDP) by sampling state transitions. In contrast to existing reinforcement learning methods that are based on successive approximations to the nonlinear Bellman equation, we propose a Primal-Dual @math Learning method in light of the linear duality between the value and policy. The @math learning method is model-free and makes primal-dual updates to the policy and value vectors as new data are revealed. For infinite-horizon undiscounted Markov decision process with finite state space @math and finite action space @math , the @math learning method finds an @math -optimal policy using the following number of sample transitions @math where @math is an upper bound of mixing times across all policies and @math is a parameter characterizing the range of stationary distributions across policies. The @math learning method also applies to the computational problem of MDP where the transition probabilities and rewards are explicitly given as the input. In the case where each state transition can be sampled in @math time, the @math learning method gives a sublinear-time algorithm for solving the averaged-reward MDP.