  We describe RA-E3 (Reward-Aware Explicit Explore or Exploit), an algorithm
with provable guarantees for solving a single or multi-objective Markov
Decision Process (MDP) where we want to maximize the expected value of a
nonlinear function over accumulated rewards. This allows us to model
fairness-aware welfare optimization for multi-objective reinforcement learning
as well as risk-aware reinforcement learning with nonlinear Von
Neumann-Morgenstern utility functions in the single objective setting. RA-E3
extends the classic E3 algorithm that solves MDPs with scalar rewards and
linear preferences. We first state a distinct reward-aware version of value
iteration that calculates a non-stationary policy that is approximately optimal
for a given model of the environment. This sub-procedure is based on an
extended form of Bellman optimality for nonlinear optimization that explicitly
considers time and current accumulated reward. We then describe how to use this
optimization procedure in a larger algorithm that must simultaneously learn a
model of the environment. The algorithm learns an approximately optimal policy
in time that depends polynomially on the MDP size, desired approximation, and
smoothness of the nonlinear function, and exponentially on the number of
objectives.
