Policy Learning from Reward Totals

A reward total records how much a group received, but not which interaction produced it. We study policy learning from $N$ interactions released as at most $M$ disjoint, unweighted reward totals. An encoder may use all contexts, actions, and logging propensities to form groups before seeing rewards; the learner receives the totals, metadata, and assignments. In a fixed two-policy family, data-independent grouping has worst-case regret at least of order $M^{-1/2}$, whereas two comparison-aware totals attain $N^{-1/2}$. For larger finite libraries, randomized block encoders trade the number of totals against estimation variance, and lower bounds cover every outcome-blind partition fitted to the complete metadata batch. The bounds match in specified polynomial-budget and large-sample linear-budget regimes. For policies generated by $r$ fixed gates and $A$ actions, a shared value-moment table requires at most $rA+1$ totals per reporting window and supports optimization over all stochastic heads after release. The reward mean need not be realizable by the gates; under i.i.d. logging and coverage, the binary-action rate matches individual feedback. Simulations and a retrospective click-log study distinguish policy-selection error, same-log acquisition loss, and later-period return: shared totals reduce acquisition loss on the observed log, while later-period intervals do not establish return dominance.