acceptodds
Under review as a conference paper at ICLR 2027

Policy Learning from Reward Totals

Abstract

A reward total records how much a group received, but not which interaction produced it. We study policy learning from interactions released as at most 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 , whereas two comparison-aware totals attain . 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 fixed gates and actions, a shared value-moment table requires at most 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.

Primary area:
learning theory
Keywords:
reward aggregation, policy learning, outcome-blind partitioning, randomized block encoding

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_cWthOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies policy learning when individual rewards are hidden and only a limited number of aggregate reward totals can be released. It proposes policy-aware randomized grouping to estimate policy values and derives regret guarantees and minimax lower bounds. It also conducts experiments on synthetic data and logged click data to show improvements over some aggregate-feedback baselines.

Critical strengths

The paper addresses a meaningful and practically motivated problem.

The paper evaluates its method against a reasonably broad set of baselines, so I do not consider the baseline coverage a major concern.

Critical weaknesses

The practical significance depends on how broadly the assumed feedback model applies to real-world settings. If the theoretical results apply only to this particular setup, their significance may be limited. The authors should better justify the practical relevance and generality of their formulation.

Questions for authors

What real-world applications genuinely impose the specific feedback restrictions assumed in this paper? In particular, why are policy-aware unweighted reward totals necessary when other authorized aggregate queries, such as weighted sums or alternative statistical summaries, may be available?

2 comments

Thank you for asking us to clarify the model's practical scope and the role of other authorized statistics.

  1. Why use unweighted totals if other sufficient statistics are authorized?

If authorized weighted sums or other summaries determine the required policy comparisons, they should be used directly; our grouping step is unnecessary. For existing group totals, Appendix H.2 gives an exact criterion: a weighted comparison is recoverable for every reward vector if and only if its weights are constant within each group. Thus ordinary segment-by-action counts already suffice for policies using fixed customer segments under uniform logging.

  1. Practical motivation and evidence for the restrictions

Private advertising measurement addresses a real need to assess campaigns without sharing customer-level outcomes, as illustrated by Zenjob. For such a collaboration, AWS lets the owner approve a fixed grouped-sum query and permit one table use. Appendix H.3 shows how the learner can supply policy-dependent labels while the owner controls the statistic and further access. The public cases establish the business need, and the service controls make this configuration possible; they do not confirm its joint use in a particular deployment.

  1. Theoretical value and extensions to other reports

Within the totals model, §4 quantifies how the release budget limits the best attainable worst-case policy-selection accuracy. The minimax lower bounds allow arbitrary partitions fitted to the full metadata batch and match our construction in the stated regimes. This gives a basis for choosing a release budget according to the desired accuracy.

Appendix M uses the published Private Lift treatment/control converter counts to select future campaign eligibility across fixed customer segments. With all counts available, one table supports all choices of eligibility probabilities across those segments. The appendix also handles capacity constraints, bounds the regret from withheld counts, and derives guarantees from noisy treatment-effect estimates. For fixed segments, selection uses the existing reports, with no new query for each candidate. These results extend the shared-table selection guarantees; the general minimax lower bounds remain specific to the stated single-release totals model.

Thank you for the clarifications. The example illustrates how the proposed feedback model could arise in practice. My remaining concern is how common real-world reporting rules combine all three features: a cap on the number of group totals, permission to use policy-dependent grouping, and a prohibition on direct weighted comparisons. Evidence that these conditions recur across deployments would strengthen the practical motivation.

I would also appreciate a marked-up revision highlighting the main changes, as they are difficult to locate in the current revision.

I am maintaining my score.

Reviewer_DoCYOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper considers a problem of policy learning from reward totals where rewards from a sequence are randomly partitioned into G groups and released. Although each context and action pair's group membership is revealed, the specific reward is hidden. This paper develops an algorithm-based policy comparison for a policy class Π\Pi, and provides upper and lower bounds based on the number of policy comparisons allowed (linear and polynomial).

Critical strengths
  • This paper considers an interesting question of policy learning in this environment, which I believe has not been considered with all of these constraints. However significant prior work in related areas exists.
Critical weaknesses
  • This paper is extremely hard to read, and required significant time to parse. I believe that it should be mostly rewritten.
  • I am not convinced that the paper’s restrictions reflect a realistic application. Namely, the paper proposes that metadata and policy-aware grouping are available but weighted sums and repeated queries are prohibited. This setting feels a little bit contrived?
Questions for authors
  • How does this work extend to more general infinite policy classes (eg unrestricted linear functions, softmax policies)?
  • What are good real-world examples of where these exact constraints hold?
  • As the finite policy class grows, how do the number of required reward totals and computational cost scale? Does this algorithm remain practical?
2 comments

We apologize for the difficult presentation. Sections 1–5 now explain the learning goal and available information before the construction, and explain the purpose of each lower-bound argument.

  1. Where do the exact restrictions hold together?

Private advertising measurement provides a concrete motivation: Zenjob's campaign needed to measure effectiveness without sharing user-level outcomes with the platform. In this type of collaboration, AWS allows the outcome holder to approve a fixed analysis and set a one-use table budget.

Appendix H.3 specifies the resulting workflow. The platform supplies labels from its contexts, actions, and known logging probabilities. The owner permits one grouped-sum query, with each reward entering one of at most M totals, and retains control over the calculation and further access. AWS's documented expression and differencing risks provide reasons to control both the calculation and repeated access. The published customer cases do not confirm that the complete restriction set is jointly enforced in a particular deployment.

The theoretical contribution is to quantify the learning cost of this restricted release. Section 4 gives matching upper and lower bounds in specified budget and sample-size regimes, even allowing grouping based on the full metadata batch. Section 5 shows how policies sharing fixed context groups can be optimized from a single reward table. These results identify what accuracy a release can support and when policy structure reduces its cost.

  1. Unrestricted linear and softmax policy classes

Appendix L.1 directly treats unrestricted softmax parameters by enlarging and refining a finite parameter grid. Equation (61) separates approximation and estimation error; the schedule following it gives consistency for each fixed population as sample size and release budget grow. It assumes fixed feature dimension and action count, i.i.d. logging with known probabilities bounded away from zero, and one window without minimum-size constraints.

For linear decision rules, we consider choosing the action with the largest affine score. These rules are limits of softmax policies, so the same procedure competes with them while returning a softmax policy. This is a constructive consistency result; high-dimensional exhaustive search remains costly.

  1. Scaling and practicality

M counts released totals. For K candidates and one window, blocks of b comparisons use at most ceil((K−1)/b) 2^b totals. The b=1 option has cap 2(K−1); b=floor(log₂(K−1)) has cap Θ(K²/log K) for K≥3. Under i.i.d. logging with bounded importance ratios, before minimum-size repairs and for sufficiently large N, their leading regret bounds are respectively O(√(K log K/N)) and O(√(K/N)) (Table 13, p. 56).

With a known coefficient bound and center zero, lazy evaluation uses at most N(b+1) row–policy evaluations. Decoding m nonempty totals takes O(K+mb) arithmetic; grouping and storing the candidate models add costs. In the local scoring-through-selection benchmark with N=8,192, 128 features and b=4, runtime falls from 483.4 to 60.1 ms at K=1,025, but rises from 8.0 to 44.4 ms at K=17 (Table 17, p. 59). Thus computation can improve for larger candidate sets, while the growing release budget and model storage remain practical constraints. These timings do not measure clean-room query execution.

We would be grateful for the opportunity to have the revised manuscript reconsidered.

Thank you for the response.

The rewriting of the introduction for this paper indeed helped to clarify many of the missing details. Nevertheless, I believe more of the manuscript should be improved for clarity. Further, I maintain my concerns regarding the greater applicability of this method and the novelty of the techniques introduced. As a result, I will maintain my score.

Reviewer_5TRsOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies an offline contextual bandits setting where individual rewards are hidden, and the learner can only observe sums of rewards over groups of samples.

in this setting, an encoder uses contexts and and actions to form groups before seeing rewards. After that, the learner receives the totals, metadata, and assignments.

The authors give a series of regret guarantees under different budget settings.

Critical strengths

The studied setting looks novel and might be of practical interest.

Critical weaknesses

The paper was not written in a human-readable way. A lot of new terminologies were introduced without a proper definition.

The first example is the AWS Clean Rooms example used as the main motivation of the new setting. For readers who are not familiar with AWS, that paragraph is hard to understand. For example, the authors say ``AWS identifies a disclosure risk behind restricting expressions: they can isolate small subgroups inside a larger aggregate (Amazon Web Services, n.d.c). '' What are those expressions? Why are they related to the setting studied here?

Later, in the contribution part, the authors introduced a new notion called library, and its formal definition was not given until Section 2.1. Such omission are ubiquitous in the technical part of the paper. For example, ``correct propensity'' was never formally defined.

In short, the writing quality of the paper is not satifying, and it clearly does not meet the bar of ICLR.

Questions for authors

See weaknesses above.

1 comment

We apologize for the recurring gaps in definitions and explanation. Your examples reflect a problem throughout the exposition. We have rewritten the introduction and technical presentation with the reader's sequence of questions in mind.

  1. What are “expressions,” and how do they relate to the model?

An expression is a calculation inside an aggregate, such as weight * reward in SUM(weight * reward). A zero–one weight can restrict a large group's sum to purchases from a small subset. This is the disclosure risk discussed in the cited AWS documentation.

The connection is that an owner can approve grouping and SUM(reward) while requiring separate approval for a different calculation. Section 1 now explains the decision and each party's data first; Appendix H.3 explains this example and the corresponding permissions.

  1. Undefined terms and the technical presentation

“Library” meant the candidate policy set; we now use that name. “Correct propensity” meant the actual, known logging probability μ(a|x)=P(A=a|X=x), now defined in §2.1.

We also revised the surrounding argument. Equation (2) states the weighted comparisons needed to rank policies. Section 2.2 and Figure 1 show how two totals estimate one comparison before §3 extends the construction. Section 4 explains the role of each lower-bound construction, and §5 introduces the common reward table before its optimization guarantee. The proof appendices now explain the roles of the intermediate bounds.

We would be grateful for the opportunity to have the revised manuscript reconsidered.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Overview of Revisions

Thank you for the careful reviews. Thank you for the reviews. We apologize that the presentation made the problem and technical arguments difficult to follow. The revision addresses the following concerns.

  • 5TRs: exposition throughout the paper. Sections 1–5 now introduce the decision, available information, and policy comparisons before the grouping method. The two-total example precedes the general construction, and each lower-bound argument explains what makes policy selection difficult.

  • DoCY: the joint restrictions, general classes, and scaling. Appendix H.3 connects documented private-measurement needs to AWS controls that can enforce the feedback model, distinguishing configuration from deployment evidence. Appendix L gives a consistency construction for unrestricted softmax and affine-score decision rules; Appendix K states release and computation costs alongside measured runtimes.

  • cWth: necessity and generality. We identify when other authorized statistics make grouping unnecessary, explain what the budget/error bounds establish within the restricted model, and show how Appendix M extends policy selection to existing trial counts and noisy effect estimates.

The main constructions and rate statements are retained. We also corrected numerical tie handling and regenerated the affected appendix experiments; REVISION_LOG documents the changes.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.