  In Reinforcement Learning (RL), it is commonly assumed that an immediate
reward signal is generated for each action taken by the agent, helping the
agent maximize cumulative rewards to obtain the optimal policy. However, in
many real-world scenarios, immediate reward signals are not obtainable;
instead, agents receive a single reward that is contingent upon a partial
sequence or a complete trajectory. In this work, we define this challenging
problem as Reinforcement Learning from Bagged Reward (RLBR), where sequences of
data are treated as bags with non-Markovian bagged rewards. We provide a
theoretical study to establish the connection between RLBR and standard RL in
Markov Decision Processes (MDPs). To effectively explore the reward
distributions within these bags and enhance policy training, we propose a
Transformer-based reward model, the Reward Bag Transformer, which employs a
bidirectional attention mechanism to interpret contextual nuances and temporal
dependencies within each bag. Our empirical evaluations reveal that the
challenge intensifies as the bag length increases, leading to the performance
degradation due to reduced informational granularity. Nevertheless, our
approach consistently outperforms existing methods, demonstrating the least
decline in efficacy across varying bag lengths and excelling in approximating
the original MDP's reward distribution.
