Reinforcement Learning with Trajectory Feedback
This addresses a practical limitation in reinforcement learning for applications where frequent reward feedback is unavailable, representing an incremental step in feedback modeling.
The paper tackles the problem of reinforcement learning with infrequent feedback by introducing trajectory feedback, where only cumulative rewards over entire trajectories are observed, and develops algorithms for both known and unknown transition models with regret analysis.
The standard feedback model of reinforcement learning requires revealing the reward of every visited state-action pair. However, in practice, it is often the case that such frequent feedback is not available. In this work, we take a first step towards relaxing this assumption and require a weaker form of feedback, which we refer to as \emph{trajectory feedback}. Instead of observing the reward obtained after every action, we assume we only receive a score that represents the quality of the whole trajectory observed by the agent, namely, the sum of all rewards obtained over this trajectory. We extend reinforcement learning algorithms to this setting, based on least-squares estimation of the unknown reward, for both the known and unknown transition model cases, and study the performance of these algorithms by analyzing their regret. For cases where the transition model is unknown, we offer a hybrid optimistic-Thompson Sampling approach that results in a tractable algorithm.