1 Introduction↩︎

Bidding in repeated auctions provides a compelling domain for reinforcement learning, combining continuous control, stochastic dynamics, and strategic interaction among agents. These environments are central to real-world applications such as digital advertising [1], where agents must learn to make sequential bidding decisions under uncertainty. At first glance, standard reinforcement learning approaches [2] — such as policy gradient methods [3], [4] for continuous control or value-based methods for reward modeling — appear well-suited to this setting. However, a subtle but critical challenge arises from the structure of the reward signal itself.

In many decision-making environments, rewards exhibit discontinuous, thresholded structure. For example, in first-price auctions, a bidder receives no reward unless their bid exceeds that of competitors, at which point they obtain a positive payoff that decreases with further increases in bid. This induces a reward landscape consisting of large flat zero-reward regions separated from high-reward regions by sharp thresholds. Similar structures arise more broadly in domains such as sparse-reward tasks or threshold-based decision problems. Conceptually, such reward functions resemble a “cliff” or “sawtooth” landscape, where small changes in action can result in abrupt changes in outcome.

We show that this reward structure presents a fundamental challenge for policy gradient methods. Driven by stochastic exploration and gradient-based updates, policies tend to move toward regions of higher reward, but may overshoot the optimal region and enter flat zero-reward regimes. Once in these regions, the absence of informative gradient signal makes recovery extremely sample-inefficient. This leads to a failure mode we term zero collapse, in which the policy becomes effectively trapped in low-signal regions of the reward landscape. Even in cases where rewards are not strictly zero but remain flat, gradient estimates can cancel out, leading to unstable or stalled learning dynamics.

We empirically observe this phenomenon across a range of policy gradient methods, including REINFORCE and actor-critic variants. While all methods are affected to some degree, actor-critic methods [4], [5] are particularly susceptible, as biased value estimates can accelerate movement toward unstable regions of the reward landscape, increasing the likelihood of collapse.

In summary, our contributions are as follows:

• We identify a failure mode of policy gradient methods — zero collapse — in environments with discontinuous reward landscapes.

• We provide a mechanistic explanation showing how flat zero-reward regions and discontinuities lead to vanishing gradient signal and sample inefficiency.

• We analyze the interaction between policy stochasticity and step size, demonstrating how policies can overshoot high-reward regions and collapse into unrecoverable regimes.

• We empirically demonstrate this phenomenon across multiple policy gradient variants, including REINFORCE and actor-critic methods.

• We propose practical mitigation strategies, including initialization schemes and architectural choices that improve stability and learning speed.

• We introduce a formal RL framework for auction environments, highlighting structural properties such as simultaneous independent actions (details in Appendix).

2 Related Work↩︎

Policy gradient methods have long been a fundamental approach for reinforcement learning in continuous and stochastic environments. Early work such as REINFORCE demonstrated how gradient ascent on expected return can be performed directly through stochastic policies [3]. Subsequent work extended these ideas to actor-critic methods, which combine policy optimization with learned value-function approximations to reduce variance and improve sample efficiency [4].

Modern reinforcement learning systems often employ policy optimization techniques that explicitly constrain policy updates. Examples include Trust Region Policy Optimization (TRPO) [6] and Proximal Policy Optimization (PPO) [7], which improve stability by limiting the magnitude of policy changes between updates. Such methods have become standard approaches for large-scale policy optimization.

Our work is also related to the broader literature on sparse-reward and exploration challenges in reinforcement learning. In environments where informative reward is rare, policies may struggle to discover useful behaviors, motivating techniques such as intrinsic motivation, count-based exploration, and reward shaping [8]. However, the phenomenon studied here differs from classical sparse-reward settings. In our case, informative reward may be readily discoverable, yet policies can still collapse due to the interaction between discontinuous reward geometry and policy optimization dynamics.

Finally, reinforcement learning has been applied extensively to auction and real-time bidding environments, particularly in digital advertising [1]. These domains naturally exhibit thresholded and discontinuous reward structures, making them a useful setting for studying the optimization challenges considered in this work.

To the best of our knowledge, prior work has not explicitly characterized the failure mode studied here, namely zero collapse arising from the interaction between discontinuous reward landscapes and policy gradient optimization.

3 Reward Geometry of Thresholded Environments↩︎

We begin by considering a simple one-dimensional reward function that captures the essential structure of many auction and decision-making problems: \[r(a) = \begin{cases} 0 & \text{if } a < h \\ f(a) & \text{if } a \geq h \end{cases}\]

where \(a\) denotes the action (e.g., a bid), \(h\) is a threshold, and \(f(a)\) is a decreasing function. This function is piecewise-defined, consisting of a flat zero-reward region for \(a<h\), and a non-flat region for \(a \geq h\) where reward decreases as the action increases.

As illustrated in Figure 1, this reward function exhibits several key structural properties. First, there exists a flat zero-reward region, in which a wide range of actions yield identical outcomes. Second, there is a discontinuous transition at the threshold \(h\), where reward abruptly changes from zero to a positive value. Third, beyond the threshold, reward decreases monotonically, making the optimal action lie near the boundary defined by the discontinuity. Conceptually, this produces a “cliff”-like or “sawtooth” landscape, where small changes in action near the threshold can result in large changes in reward.

While the above example is one-dimensional, this structure generalizes naturally to more complex settings. In many environments, multiple thresholds may exist along a given dimension, leading to repeated transitions between flat and non-flat regions (e.g., a “sawtooth” pattern). In higher-dimensional action spaces, similar discontinuities arise along decision boundaries, where different regions of the action space correspond to qualitatively different outcomes. Such structures are common in domains including multi-item auctions, sparse-reward reinforcement learning, and threshold-based control problems. Despite these variations, the key structural property remains consistent: large regions of the action space provide little or no informative signal, separated by sharp transitions to regions where reward varies meaningfully.

This reward geometry presents fundamental challenges for policy gradient methods. In flat regions, the reward remains constant across actions, providing little to no useful signal for gradient-based updates. Even when rewards are not strictly zero, flatness can lead to high-variance or canceling gradient estimates, resulting in unstable or slow learning. Furthermore, the presence of a sharp optimum at the boundary introduces sensitivity to both stochastic exploration and step size. Small perturbations can cause the policy to overshoot the optimal region and enter low-signal regimes, from which recovery is highly sample-inefficient. As we will show, these dynamics give rise to a characteristic failure mode in policy gradient methods.

4 Zero Collapse: Mechanism and Dynamics↩︎

We now examine how policy gradient methods behave under the reward geometry described above. Recall that policy gradient updates take the general form:

\[\begin{align} &\gradtheta{i} \agentobj{i} = \sum_{t=0}^{T-1} \gradtheta{i} \log \left(\agentpolicy{i}(\agentaction{i}{t} | s_{t})\right) \hat{Q}^{(i)}_{t} \\ \end{align}\]

with parameters updated via \(\theta_{i} \leftarrow \theta_{i} + \alpha \gradtheta{i} \agentobj{i}\). The policy gradient update follows the REINFORCE formulation [3]. As in supervised learning, this update resembles a weighted log-likelihood objective, where the weights are given by returns \(\hat{Q}^{(i)}_{t}\). Consequently, the magnitude and quality of the reward signal directly determine the effectiveness of gradient updates, as shown in Figure 1.

Under the reward structures considered in Section 3, the action space can be viewed as consisting of two regimes: a non-flat region, where reward varies with the action, and a flat region, where reward remains approximately constant (and often near or at zero). These regions are separated by a sharp discontinuity at the threshold.

In the non-flat region, learning proceeds as expected. Because reward varies with the action, trajectories provide informative signal about the direction of improvement, and gradient updates consistently move the policy toward higher-reward actions. As a result, optimization in this regime is relatively stable and efficient.

However, this behavior changes sharply near the threshold. Due to stochastic exploration and finite step sizes, policy updates can easily overshoot the optimal region and enter the flat regime. Once this occurs, the learning dynamics degrade significantly.

In the flat region, a large fraction of sampled trajectories yield little or no reward, resulting in trajectory-level sparsity. Consequently, gradient estimates become dominated by noise or canceling contributions, providing little reliable signal for improving the policy. Even when occasional informative trajectories are observed, they are insufficient to consistently guide the policy back toward the high-reward region, making recovery highly sample-inefficient.

This leads to a fundamental asymmetry: while it is relatively easy for the policy to move from the non-flat region into the flat region, it is substantially more difficult to escape once there. We refer to this failure mode as zero collapse, in which the policy becomes effectively trapped in low-signal regions of the reward landscape. Importantly, this phenomenon is not merely a consequence of vanishing gradients, but rather of degenerate gradient estimates dominated by uninformative trajectories.

5 Empirical Evidence of Zero Collapse↩︎

As shown in Figure 2, we evaluate several policy gradient algorithms in a simulated auction-like environment exhibiting the discontinuous reward structure described in Section 3. Specifically, we consider REINFORCE, REINFORCE with baseline, actor-critic (SARSA) with baseline, and actor-critic (TD). Each method is trained for 5000 epochs using batches of 200 trajectories, and performance is measured via average cumulative reward (maximum of 25). To isolate the learning dynamics, all methods use a shared policy architecture — a simple neural network with ReLU activations parameterizing a Gaussian policy, and are trained using SGD with a fixed learning rate.

Across all methods we observe consistent initial improvement from strongly negative reward toward near-zero performance. This indicates that policy gradient updates are able to identify and move toward the boundary of the non-zero reward region.

However, this progress is not sustained. Most methods rapidly collapse to near-zero reward and remain there for the remainder of training. This behavior is particularly pronounced in the actor-critic variants, which exhibit brief improvement before becoming trapped in low-reward regimes.

Notably, REINFORCE with a baseline is able to temporarily escape this failure mode and achieve near-optimal reward. However, this success is unstable. As training progresses, the method exhibits high variability in performance — visible as a “rain” of scattered rewards below the optimum — followed by a complete collapse back to near-zero reward. This transition illustrates the onset of instability and eventual failure even after apparent convergence.

These results are consistent with the mechanism described in Section 4. In all cases, policies are able to traverse the informative (non-flat) region but subsequently overshoot into flat regions of the reward landscape. Once there, learning becomes dominated by uninformative trajectories, preventing reliable recovery. Taken together, this provides empirical evidence that zero collapse is a systematic failure mode across policy gradient methods in environments with discontinuous reward structure.

6 Mitigating Zero Collapse↩︎

6.1 Step Size / Update Magnitude Control↩︎

One key factor driving zero collapse is the magnitude of policy updates. In policy gradient methods, parameter updates are scaled by both the learning rate (\(\alpha\)) and the reward-weighted gradient signal. As a result, larger rewards can amplify update magnitude, particularly in the non-flat region where reward increases toward the threshold. This creates a compounding effect: as the policy approaches high-reward regions, update magnitudes can grow, increasing the likelihood of overshooting into flat regions of the reward landscape.

Controlling the effective step size is therefore critical for stability. In our experiments, we found that using stochastic gradient descent (SGD) led to more stable behavior than momentum-based optimizers such as Adam. While we do not include full results here, preliminary experiments showed that Adam often led to substantially faster collapse, sometimes preventing even temporary convergence to high-reward regions. This is consistent with the proposed mechanism: momentum accumulates past gradients, effectively increasing update magnitude and making overshoot more likely.

More generally, one can mitigate overshooting by normalizing update magnitude directly. For example, an adaptive learning rate of the form \[\alpha = \sqrt{\frac{\epsilon}{||\nabla_\theta J(\theta)||^2 + \eta}}\]

where \(\eta > 0\) is a small constant for numerical stability. In the regime where \(|\nabla_\theta J(\theta)|^2 \gg \eta\), this rescales updates such that

\[||\Delta \theta|| = \alpha ||\nabla_\theta J(\theta)|| \approx \sqrt{\epsilon},\]

resulting in approximately constant step sizes in parameter space regardless of gradient magnitude. This normalization reduces sensitivity to reward scale and helps prevent excessively large updates near high-reward regions.

While this approach improves stability, it does not directly constrain changes in policy space, which can vary nonlinearly with respect to the parameters. This suggests a natural connection to policy optimization methods that explicitly control distributional shift, such as trust-region or natural gradient approaches(e.g. TRPO [6], PPO [7]). These methods bound changes in policy space rather than parameter space, and may therefore provide a more principled way to prevent overshooting in environments with discontinuous reward structure. We leave a detailed investigation of such approaches to future work.

6.2 Initialization Strategy↩︎

Another factor that exacerbates zero collapse is policy initialization. Standard approaches such as random initialization can place a significant portion of the policy’s probability mass within the flat region of the reward landscape. In this regime, many sampled trajectories yield minimal or identical reward, leading to weak or uninformative gradient estimates. As a result, learning becomes highly sample inefficient from the outset, and the policy may fail to reach informative regions altogether.

A simple yet effective mitigation is to initialize the policy within the informative (non-flat) region of the reward landscape, where actions yield non-trivial reward signal. This avoids starting in flat regions where gradient information is weak or absent, enabling more efficient early learning. Importantly, this does not require precise knowledge of the entry threshold at which reward first becomes non-zero. Instead, it is sufficient to obtain a coarse estimate of an upper bound within the informative region — i.e., a point beyond which reward becomes non-positive — thereby ensuring initialization occurs within the region where gradients are informative.

In practice, this can be achieved by biasing the initial policy toward actions near this upper bound, for example, by shifting the initial output distribution or applying an offset to the policy parameterization. Such estimates can often be obtained through domain knowledge, simulation, or historical data. For instance, in digital advertising with profit-based rewards (e.g., value minus cost), one can estimate a bid level at which marginal cost exceeds marginal value, providing an approximate upper boundary of the informative region. Initializing near this region increases the likelihood that early trajectories yield informative signal, facilitating efficient learning even when the true entry threshold is unknown.

6.3 Smooth Policy Parameterization↩︎

Another simple yet effective approach to mitigating zero collapse is to use a smooth activation function in the policy parameterization, particularly in the final layer. The choice of activation function affects how changes in parameters translate into changes in the policy’s output, and therefore into action selection.

The commonly used ReLU activation, (x), has a constant slope for positive inputs. As a result, a fixed parameter update \(\Delta \theta\) produces a proportional change in the output regardless of the current operating point. In the context of the policy, this implies that the effective step size in action space remains roughly constant, even as the policy approaches high-reward regions. This can exacerbate overshooting, as large updates near the reward boundary can easily push the policy into the flat region.

In contrast, smooth activation functions such as softplus exhibit a gradually varying slope. In particular, the slope decreases in regions corresponding to smaller outputs, resulting in a natural attenuation of output changes for a fixed parameter update. In the context of the policy, this leads to an adaptive effective step size: as the policy approaches sensitive regions of the reward landscape, updates become more conservative, reducing the likelihood of overshooting.

In our experiments, we found that using softplus in the final layer, combined with ReLU or ELU in the hidden layers, resulted in more stable learning. Fully saturating activations such as tanh or sigmoid were less effective, as they reduce gradient signal too aggressively and impede learning.

6.4 Baseline as a Stabilizing Signal↩︎

The use of a baseline, commonly employed to reduce variance in policy gradient methods [3], [4], also plays an important role in mitigating zero collapse. In standard formulations, updates take the form \(\nabla \log \pi(a|s) \cdot (R - b)\), where \(b\) is a baseline estimate of expected return.

In environments with flat reward regions, many trajectories yield identical or near-identical reward, resulting in little to no gradient signal when using raw returns. This exacerbates the collapse problem, as updates vanish and the policy becomes unable to recover. By subtracting a baseline, however, the learning signal is expressed in terms of relative performance. Actions that perform worse than the baseline receive negative updates, while better-than-average actions are reinforced.

This effect is particularly important near the boundary between informative and flat regions. In this regime, some trajectories yield positive reward while others fall into the flat region. With a baseline, flat-region trajectories are assigned negative advantage, while informative trajectories retain positive advantage. This creates a restoring effect, as shown in Figure 3, that pushes probability mass away from uninformative regions and back toward the reward boundary, reducing the likelihood of collapse.

Even when the policy has largely entered the flat region, the baseline can introduce small stochastic deviations in the update signal, preventing gradients from vanishing entirely. While this signal is weak and recovery remains unlikely, it provides a non-zero probability of escaping low-signal regimes. This is consistent with our empirical observations, where REINFORCE with a baseline exhibits more sustained learning and delayed collapse compared to other methods.

A potential limitation of this effect, however, is the introduction of oscillatory behavior near the reward boundary, as illustrated in Figure 4. Because the baseline induces both positive and negative updates depending on relative performance, policies operating near the threshold may experience alternating gradient directions. When combined with finite step sizes, this can lead to overshooting on either side of the boundary, resulting in back-and-forth updates rather than stable convergence. In practice, this manifests as “thrashing” around the reward threshold, where the policy repeatedly moves between informative and flat regions without settling. This behavior highlights an interaction between baselining and update magnitude, and further emphasizes the importance of step size control in such environments.

7 Mitigation Results↩︎

We evaluate the combined effect of the proposed mitigation strategies on the same auction-like environment described in Section 4. Figure 5 shows the learning dynamics across several policy gradient variants under a consistent experimental setup.

Across all methods, we observe that the proposed interventions significantly improve stability relative to the baseline experiments. In particular, REINFORCE with a baseline exhibits stable convergence to near-optimal reward, with no evidence of collapse over the course of training. This contrasts sharply with earlier results, where all methods eventually collapsed to the flat region.

REINFORCE without a baseline also demonstrates substantial improvement, achieving high reward and maintaining performance for a significant portion of training. However, it exhibits increased variance in later stages, as seen in the “rain” pattern of reward values, suggesting that instability remains without the additional stabilizing effect of a baseline.

In contrast, actor-critic methods continue to struggle despite the application of these mitigations. Both TD-based and SARSA-based variants exhibit early improvement followed by rapid collapse to near-zero reward, with no recovery. A Q-based variant shows slower improvement but ultimately fails to reach high reward and begins to degrade over time. These results suggest that while the proposed strategies improve learning dynamics for simpler policy gradient methods, they are insufficient to fully address the failure modes present in actor-critic approaches.

Overall, these results support the hypothesis that zero collapse arises from the interaction between reward geometry and optimization dynamics, and that targeted interventions — particularly step size control, initialization, and baselining — can significantly improve learning stability in such environments. Compared to the pre-mitigation results, collapse is no longer universal, and certain methods achieve sustained high reward.

8 Why Actor-Critic Methods Struggle↩︎

Despite the improvements introduced by the mitigation strategies, actor-critic methods continue to exhibit instability and eventual collapse. We now analyze the underlying cause of this behavior. To better understand the failure of actor-critic methods in this setting, we examine the behavior of the learned value function. Figure 6 illustrates the reward function alongside the value function learned after a substantial number of training iterations.

While the value network is expressive enough in principle to represent the discontinuity in the reward function, in practice it learns a much smoother approximation during training. In particular, even after many iterations, the value function fails to capture the sharp transition at the reward threshold, instead representing the environment as having a gradual slope.

This leads to a mismatch between the actor and the critic. The policy network operates in a relatively simple action space and can quickly learn directional improvements (e.g., increasing or decreasing actions), while the value network must learn a more complex, highly non-linear reward structure. As a result, the actor often updates based on an immature or inaccurate estimate of the value function.

This desynchronization has important consequences. Because the critic underestimates the sharpness of the reward boundary, it presents the actor with a distorted optimization landscape that does not reflect the true risk of entering the flat region. The policy is therefore encouraged to move aggressively across the threshold, leading to overshoot and eventual collapse.

This issue is further compounded by bootstrapping, as errors in the value function propagate directly into policy updates. In contrast, Monte Carlo methods such as REINFORCE [3] rely on sampled returns and are therefore less sensitive to inaccuracies in value estimation. As a result, actor-critic methods are particularly vulnerable to failure in environments with discontinuous reward structures.

9 Discussion and Future Work↩︎

The failure of actor-critic methods observed in this work appears to stem from a mismatch in learning dynamics between the actor and critic. While the policy can adapt quickly to directional signals in the action space, the value function must learn a more complex and discontinuous reward structure, leading to a lag in accurate value estimation. This suggests that improving synchronization between the actor and critic may be a promising direction for future work.

One potential approach is to regulate the relative update rates of the actor and critic, for example by slowing policy updates or prioritizing value function learning in early stages. Another direction is to improve sample efficiency for the value network, such as through experience replay or targeted sampling strategies that emphasize regions near reward discontinuities.

A complementary direction is to consider policy optimization methods that explicitly constrain updates in policy space rather than parameter space. Algorithms such as trust region methods [6] or proximal policy optimization [7] limit the magnitude of policy changes between updates, which may reduce the risk of overshooting across discontinuities in the reward landscape. Investigating whether such approaches can mitigate zero collapse in these environments is an interesting direction for future work.

10 Conclusion↩︎

In many decision-making domains, such as first-price auctions, rewards exhibit discontinuous, thresholded structure. In this work, we identify a failure mode of policy gradient methods in such environments, which we term zero collapse. This phenomenon arises from the interaction between optimization dynamics and reward geometry: policies readily ascend informative regions of the reward landscape, but are prone to overshooting across sharp discontinuities into flat regions where gradient signal is minimal.

We show that this behavior leads to unstable learning and poor sample efficiency across a range of policy gradient methods. To address this, we propose several practical mitigations, including step size control, informed initialization, smooth policy parameterization, and the use of baselines. Together, these interventions substantially improve stability and enable sustained learning in settings where collapse would otherwise be inevitable.

Despite these improvements, actor-critic methods continue to exhibit failure in this regime. We attribute this to a mismatch in learning dynamics between the actor and critic, where inaccurate value estimates induce systematically biased policy updates. This highlights a broader challenge for reinforcement learning in environments with discontinuous reward structure.

Overall, our results suggest that reward geometry plays a critical role in shaping learning dynamics, and that standard policy gradient methods may require careful modification to operate reliably in such settings.

11 Environment and Problem Formulation↩︎

11.1 Environment: Ad Exchange Simulation↩︎

We consider a stylized ad exchange (AdX) environment in which multiple agents compete in repeated first-price auctions over a finite horizon.

Each agent is assigned a single advertising campaign and participates in a sequence of auctions for impression opportunities (i.e., opportunities to display ads to users). The agent’s objective is to maximize profit, defined as total value obtained from fulfilling the campaign minus total spend incurred through bidding.

A campaign is defined by:

• a market segment \(s_{\text{seg}}\), corresponding to a subset of user attributes (e.g., demographic features)

• a reach \(R\), specifying the required number of impressions

• a budget \(B\), representing the reward received upon successful completion

An example campaign is: \[( \text{segment} = \text{Female\_Old}, \quad R = 500, \quad B = 40 )\]

To fulfill a campaign, an agent must obtain at least \(R\) impressions from users matching the specified segment. This requires repeatedly winning auctions for relevant users. Winning an auction incurs cost, while the campaign reward is realized proportional to the reach requirement by the end of the episode.

11.2 Markov Game Formulation↩︎

We model the environment as a fully observable Markov Game: \[\langle \mathcal{S}, \mathcal{A}, \mathcal{R}, \mathcal{T}, \gamma \rangle.\]

Let \(m\) denote the number of agents.

11.2.1 State↩︎

The global state is a product of agent-specific states: \[\mathcal{S} = \prod_{i=1}^m \mathcal{S}^{(i)}.\]

Each agent state \(s^{(i)} \in \mathcal{S}^{(i)}\) includes:

• the assigned campaign

• cumulative spend

• number of impressions obtained

• the current time step \(t\)

11.2.2 Actions↩︎

At each time step \(t\), each agent \(i\) selects an action: \[a_t^{(i)} \in \mathcal{A}^{(i)},\] where the action specifies bids across market segments: \[a_t^{(i)} = \{(b_{t,1}, u_{t,1}), \dots, (b_{t,K}, u_{t,K})\},\]

with \(b_{t, j}\) denoting the bid for segment \(j\) and \(u_{t, j}\) the allocated budget.

11.2.3 Rewards↩︎

The reward for agent \(i\) at time \(t\) is given by: \[r^{(i)}(s_t, a_t^{(1)}, \dots, a_t^{(m)}) = \text{value} - \text{cost}.\]

In this environment, agents typically incur cost throughout the episode while bidding in auctions, and only receive positive value upon successful campaign completion at the terminal step.

11.3 Single-Agent Reduction↩︎

To analyze learning dynamics, we consider a single learning agent \(i\), while all other agents follow fixed policies.

This induces a Markov Decision Process (MDP) [2]: \[\langle \mathcal{S}, \mathcal{A}, \mathcal{R}, \mathcal{T}, \gamma \rangle,\] where the action space corresponds to that of agent \(i\), i.e., \(a_t = a_t^{(i)}\), and the dynamics incorporate the behavior of the other agents through their fixed policies.

The reward function is given by: \[r(s_t, a_t) = r^{(i)}(s_t, a_t^{(1)}, \dots, a_t^{(m)}),\] where \(a_t^{(j)} \sim \pi_{\theta_j}(s_t)\) for \(j \neq i\).

Similarly, the transition dynamics are defined as: \[\mathcal{T}(s_{t+1} \mid s_t, a_t) = \mathcal{T}(s_{t+1} \mid s_t, a_t^{(1)}, \dots, a_t^{(m)}),\] with other agents’ actions sampled from their fixed policies.

This reduction allows us to analyze policy gradient methods in a standard single-agent setting, while preserving the stochasticity induced by multi-agent interaction.

11.4 Structural Properties of the Reward↩︎

The reward structure induced by the environment exhibits several properties that align with the discontinuous reward geometry described in Section 3.

First, rewards are sparse and delayed: agents incur cost throughout the episode while bidding in auctions, and receive positive reward only upon successful campaign completion at the terminal step. As a result, positive returns are contingent on satisfying a threshold condition (the reach constraint), and are therefore relatively rare under suboptimal policies.

Second, auction outcomes introduce thresholded behavior at the level of individual actions. For a given impression opportunity, reward depends on whether the agent’s bid exceeds competing bids, resulting in a discontinuous transition between losing (no value) and winning (positive value minus cost).

Finally, these effects combine to produce large regions of the action space with weak or uninformative signal, particularly when bids are consistently too low (leading to no wins) or when campaigns are not fulfilled. These regions are separated from informative regimes by sharp transitions, yielding a reward landscape with flat regions and discontinuities.

Together, these properties instantiate the reward geometry analyzed in Section 3, and give rise to the learning dynamics underlying zero collapse.

12 Multi-Agent Policy Factorization↩︎

We assume that agents act independently and simultaneously conditioned on the state.

12.0.0.1 Assumption (Conditional Independence).

The joint policy factorizes across agents: \[\pi_\theta(a_t^{(1)}, \dots, a_t^{(m)} \mid s_t) = \prod_{i=1}^m \pi_{\theta_i}(a_t^{(i)} \mid s_t).\]

12.0.0.2 Trajectory Distribution.

Under this assumption, the trajectory distribution can be written as: \[p_\theta(\tau) = p(s_0) \prod_{t=0}^{T-1} \left[ \left( \prod_{i=1}^m \pi_{\theta_i}(a_t^{(i)} \mid s_t) \right) \mathcal{T}(s_{t+1} \mid s_t, a_t^{(1)}, \dots, a_t^{(m)}) \right].\]

12.0.0.3 Implication for Gradients.

The factorization of the joint policy implies that the log-probability of a trajectory decomposes as: \[\log \pi_\theta(\tau) = \sum_{t=0}^{T-1} \sum_{i=1}^m \log \pi_{\theta_i}(a_t^{(i)} \mid s_t).\]

As a result, gradients with respect to each agent’s parameters depend only on its own policy: \[\nabla_{\theta_i} \log \pi_\theta(\tau) = \sum_{t=0}^{T-1} \nabla_{\theta_i} \log \pi_{\theta_i}(a_t^{(i)} \mid s_t).\]

This decomposition enables per-agent policy gradient updates while treating other agents as part of the environment.

13 Policy Gradient Derivations↩︎

13.1 Value Functions and Bellman Relations↩︎

For agent \(i\), define the value functions: \[V^{\pi_i}(s_t) = \mathbb{E}\left[\sum_{t'=t}^{T-1} r^{(i)}_{t'} \mid s_t \right], \quad Q^{\pi_i}(s_t, \mathbf{a}_t) = \mathbb{E}\left[\sum_{t'=t}^{T-1} r^{(i)}_{t'} \mid s_t, \mathbf{a}_t \right].\]

These satisfy the Bellman relation: \[Q^{\pi_i}(s_t, \mathbf{a}_t) = r^{(i)}_t + \mathbb{E}_{s_{t+1}}\left[V^{\pi_i}(s_{t+1})\right],\] where expectation is over \(p(s_{t+1} \mid s_t, \mathbf{a}_t)\), where \(r^{(i)}_t := r^{(i)}(s_t, a_t^{(1)}, \dots, a_t^{(m)})\), and where \(\mathbf{a}_t := (a_t^{(1)}, \dots, a_t^{(m)})\).

13.2 Multi-Agent Policy Gradient↩︎

The objective for agent \(i\) is: \[J_i(\theta_i) = \mathbb{E}_{\tau \sim p_\theta(\tau)}\left[r^{(i)}(\tau)\right].\]

Using the log-derivative trick and the factorization from Appendix B: \[\nabla_{\theta_i} J_i = \mathbb{E}_{\tau \sim p_\theta(\tau)}\left[ \sum_{t=0}^{T-1} \nabla_{\theta_i} \log \pi_{\theta_i}(a_t^{(i)} \mid s_t) \left(\sum_{t'=t}^{T-1} r^{(i)}_{t'}\right) \right].\]

This yields the standard REINFORCE estimator: \[\nabla_{\theta_i} J_i = \mathbb{E}_{\tau \sim p_\theta(\tau)}\left[ \sum_{t} \nabla_{\theta_i} \log \pi_{\theta_i}(a_t^{(i)} \mid s_t) \hat{Q}^{(i)}_t \right].\]

Where \(\hat{Q}^{(i)}_t := \sum_{t'=t}^{T-1} r^{(i)}_{t'}\).

13.3 Baseline and Advantage Estimation↩︎

Subtracting a baseline does not change the expectation: \[\nabla_{\theta_i} J_i = \mathbb{E}_{\tau \sim p_\theta(\tau)}\left[ \sum_{t} \nabla_{\theta_i} \log \pi_{\theta_i}(a_t^{(i)} \mid s_t) \left(\hat{Q}^{(i)}_t - V^{\pi_i}(s_t)\right) \right].\]

This defines the advantage: \[A^{(i)}(s_t, \mathbf{a}_t) = Q^{\pi_i}(s_t, \mathbf{a}_t) - V^{\pi_i}(s_t).\]

13.4 Actor-Critic Approximations↩︎

In practice, \(Q^{\pi_i}\) and \(V^{\pi_i}\) are approximated with function approximators: \[\hat{V}_{\mathbf{w}_i}(s), \quad \hat{Q}_{\mathbf{u}_i}(s, \mathbf{a}).\]

This yields the estimator: \[\nabla_{\theta_i} J_i \approx \mathbb{E}\left[ \sum_{t} \nabla_{\theta_i} \log \pi_{\theta_i}(a_t^{(i)} \mid s_t) \left(\hat{Q}_{\mathbf{u}_i}(s_t, \mathbf{a}_t) - \hat{V}_{\mathbf{w}_i}(s_t)\right) \right].\]

13.5 Temporal-Difference Learning↩︎

Using the Bellman relation, we obtain the TD advantage: \[A_t^{(i)} = r^{(i)}_t + \hat{V}_{\mathbf{w}_i}(s_{t+1}) - \hat{V}_{\mathbf{w}_i}(s_t).\]

This yields a low-variance actor-critic update: \[\nabla_{\theta_i} J_i \approx \mathbb{E}\left[ \sum_{t} \nabla_{\theta_i} \log \pi_{\theta_i}(a_t^{(i)} \mid s_t) A_t^{(i)} \right].\]

An alternative on-policy estimator replaces the bootstrap target with the value of the next sampled action: \[A_t^{(i)} = r^{(i)}_t + \hat{Q}_{\mathbf{u}_i}(s_{t+1}, \mathbf{a}_{t+1}) - \hat{V}_{\mathbf{w}_i}(s_t),\] where \(a_{t+1}^{(i)} \sim \pi_{\theta_i}(\cdot \mid s_{t+1})\).

This corresponds to a SARSA-style update, in contrast to the TD estimator which uses \(\hat{V}_{\mathbf{w}_i}(s_{t+1})\).

14 Experimental Details↩︎

For all versions of all algorithms, we do state and action scaling. This is important so as to keep the network weights from blowing up.

14.1 Policy Network↩︎

The policy network learns a Gaussian distribution using a Neural Net architecture portrayed in Figure7.

Where the activation layer is any non-linear function (e.g. ReLU, leaky ReLU, ELU, etc.).

Furthermore, it is vital to do state and action scaling, otherwise the policy weights can blow up.

14.2 Value Networks↩︎

For algorithms that learn Q or V, we do a standard setup: one or more dense layers taking state (and action for Q) as input and returning a Q or V value as output. Assume ReLU activation functions.

15 Framework↩︎

Source:

is a simple bidding, auction, and market framework for creating and running auction or market games. Environments in can be interfaced in a similar fashion as environments in OpenAI’s gym:

env = ...
    agents = ...
    env.init(agents, num_of_days)
    for i in range(num_of_trajs):
            all_agents_states = env.reset()
            for j in range(horizon_cutoff):
                actions = []
                for agent in env.agents:
                    agent_states = env.get_folded_states(
                                        agent, all_agents_states
                                    )
                    actions.append(agent.compute_action(agent_states))
                all_agents_states, rewards, done = env.step(actions)

A market can be thought of as a stateful, repeated auction:

• A market is initialized with \(m\) bidders, each of which has a state.

• A market lasts for \(N\) days.

• Each day, auction items are put on sale. Each day, the bidders participate in an auction for the available items.

• Each bidder’s state is updated at the end of every day. The state can track information such as auction items bought and amount spent.

References↩︎