CS Paper Radar

Competitive exploration in structured environments

James P. Wolfe, Joshua B. Plotkin

cs.GT physics.soc-phq-bio.PE ·submitted 2026-10-26 00:02 UTC · v1
code/data

Abstract

Organisms must constantly weigh exploiting the resources they know against exploring for better ones. When foragers compete, the best behavior for each forager also depends on what its competitors do. How does competition change the strategic balance between exploration and exploitation? Here we address this question in a minimal model: two $ε$-greedy temporal-difference learners on a one-dimensional lattice, who start at a small reward at one end and are unaware of a larger reward at the other. For a lone forager, the optimal exploration rate increases monotonically with the value of the distant reward, and with its distance up to a critical distance. When two foragers share the lattice and split rewards, the choice of exploration rate becomes a game whose Nash equilibria have both foragers exploring, both staying, or one exploring while the other stays (anti-coordination). Under local best-response dynamics, pairs of foragers often converge on both exploring or both staying, even when anti-coordination would be socially optimal. This social dilemma arises for a wide range of parameters, and it persists even in a simplified model without explicit spatial structure. A minimal, naturalistic signal, in which one forager informs the other that it has found the distant reward, can remove many of the dilemmas in which both foragers explore, and can produce a Nash equilibrium whose collective payoff exceeds that of every outcome available without signaling.

Comment
41 pages, 15 figures, 5 tables (19 pages, 6 figures, 3 tables main text; 22 pages, 9 figures, 2 tables SI Appendix). Code: https://github.com/james-wolfe/competitive-exploration

Closest papers

Nearest neighbours by meaning across the whole index.

Emergent aggregation from collective foraging

cs.LG cond-mat.stat-mechcs.MAnlin.AO+1 ·2026-08-28 ·Gorka Muñoz-Gil, Andrea López-Incera, Vide Ramsten, Giovanni Volpe, Thomas Müller +1 more
similarity 0.69
Abstract · 11 pages, 8 figures

Collective behaviour in living systems is usually modelled as the outcome of a \emph{direct} social drive: agents are rewarded, or hard-wired, to align with or approach their neighbours. Here we show that aggregation can instead emerge from an \emph{indirect} objective. We let reinforcement learning foragers, initially performing a random walk, optimize their dynamics from a purely individual reward for finding replenishable targets, while perceiving only their conspecifics and never the targets themselves. As the visual range grows, the agents undergo a sharp crossover from an environment-tuned individual search to a scale-agnostic collective one, and this crossover coincides with the onset of spatial aggregation. Thus a collective phase arises as a by-product of optimal foraging, without any direct reward for grouping. A minimal analytical first-passage model reproduces the transition as a crossover between the two search strategies. Our results identify indirect, resource-driven reward as a generic route to emergent collective phenomena.

0.27

Effectiveness of Curriculum Learning Depends on Reward Sparsity and Competing Optima

cs.LG cs.AI ·2026-10-22 ·John J. Vastola, Ann Huang, Satpreet H. Singh, Samuel J. Gershman, Kanaka Rajan
top venue similarity 0.62
Abstract · Accepted to NeurIPS 2026

While animals and people tend to learn a task more quickly and reliably when they first train on simpler versions of it, curriculum learning's effectiveness in artificial settings varies, and appears substantially greater in reinforcement learning than in supervised learning. In this work, we construct and analyze a minimal model of policy learning to better understand why. We consider an open-loop, episodic target interception task whose parameters---especially how close the agent must be to the target to receive an informative reward signal---can be chosen so that the agent either receives informative rewards frequently ('dense' rewards) or rarely ('sparse' rewards). We mathematically and numerically analyze the dynamics of REINFORCE-based policy learning in both cases. In the dense reward case, curricula have only marginal benefits; in the sparse case, curricula can be required for learning to occur at all. We find that this is especially true when the agent has the conflicting goals of minimizing effort and accumulating high reward, since this can produce distinct reward landscape optima which compete with one another. Our characterization of useful curricula in this setting indicates that they address two issues: they (i) make rewards less sparse to speed up learning, and (ii) shape the reward landscape to steer agents away from bad local optima.

0.27

Multi-Agent Learning of Reactive Strategies in Iterated Games

cs.GT physics.soc-phq-bio.PE ·2026-10-10 ·James P. Wolfe, Joshua B. Plotkin
theorycode/data similarity 0.61
Abstract · 27 pages, 14 figures (12 pages + 3 figures main text; 15 pages + 11 figures Supplemental Material). Code: https://github.com/james-wolfe/rea…

Learning agents, whether humans or algorithms, adapt to one another rather than to a fixed environment. Selfish learning need not produce a good outcome for the group, especially when learners face a social dilemma. The iterated prisoner's dilemma (IPD) is the classical example, but it is usually studied in populations of agents who imitate successful strategies. Here, we instead study selfish gradient ascent learners on the two-dimensional space of reactive strategies. A reactive strategy is described by two continuous traits: reciprocity, the chance of cooperating after the co-player cooperates, and forgiveness, the chance of cooperating after the co-player defects. Each learner updates its strategy in the direction that most rapidly improves its payoff against all other learners, by an amount governed by its learning rate. We show that heterogeneity in learning rates can qualitatively change the long-term outcome: a population with uniform learning rates converges to always-defect (ALLD), whereas a population with variable learning rates approaches generous-tit-for-tat (GTFT), which produces nearly optimal collective payoffs. In simulations, every population passes through a transient state of minimal forgiveness, in which the distribution of reciprocity determines the outcome. Variable learning rates promote cooperation because slow learners preserve high reciprocity until the population reaches this state. We prove sufficient conditions on the distribution of reciprocity for convergence to ALLD or to tit-for-tat (TFT). Variable learning rates also allow cooperation to recover from perturbation, which is provably impossible under uniform learning. These results suggest that purely selfish and myopic learning can produce persistent cooperation provided the population has intrinsic variability in learning rates.

0.40

Satisfied, Not Solving: Wireheading of Bounded Homeostatic Rewards in Reinforcement Learning

cs.LG cs.AI ·2026-10-31 ·Chase J. Metoyer
code/data similarity 0.60
Abstract · 33 pages, 5 figures, 11 tables. Code and data: https://github.com/chasemetoyer/satisfied-not-solving

Bounded intrinsic rewards are often assumed to be safe from exploitation: if a signal can yield at most a fixed amount, gaming it should not pay. We test this for a homeostatic satiation reward, in which needs build up and relieving them is rewarding, and give the agent a cheap action that resets its needs. In MiniGrid DoorKey-8x8, PPO agents with this action solved 2 of 80 seeds, against 71 of 80 on the same seeds without it; in KeyCorridorS3R1, 0 of 20 against 20 of 20. Their policies stayed near uniform. The reward does not ask for this: a telescoping argument caps any policy's satiation return at the needs' starting drive, and a post-hoc computation shows that, at every growth rate we trained, a solving trajectory beats that cap on all sampled layouts. In DoorKey with advantage normalization on, a satisfaction signal the agent could fill itself was worse than none (11 of 20 solved with task reward alone, 1 of 20 with the tamperable signal), and a per-press cost of 0.1 restored the task in every seed. Farming of positive reward cycles appeared in DoorKey but not persistently in KeyCorridorS3R1. All predictions were pre-registered, and hash-locked from round 3 on; 9 of our 23 hypotheses were not supported, and we report each.

0.65

When Does Opponent Modeling Pay Off? Spatial Inference Stabilises Reinforcement Learning under Partial Observability

cs.GT cs.LGcs.MA ·2026-10-13 ·Marcel Petran, Stefan Edelkamp
similarity 0.60
Abstract · 9 pages, 7 figures, 2 algorithms, 4 tables, submitted to AAMAS 2027

Deep reinforcement learning agents in partially observable competitive games must act on beliefs about an unseen opponent's intent. We study a spatial opponent model: a transformer trained with hindsight-relabelled opponent goals that outputs a subgoal heatmap from the opponent's observed trajectory, fused early into a dueling double DQN. In symmetric constant-sum foraging games with partial observability, the module stabilises training. Plain TD(0) DQN suffers degenerate seeds in three of four one-step configurations, whereas the opponent-model agent never collapses and, wherever training succeeds, recovers the majority of the symmetric game value. Transfers zero-shot to a foraging opponent unseen by the learner, with a positive goal advantage over the baseline, and loses this edge exactly where an information argument predicts: against a full-information tracking adversary whose intent is the learner itself, and on resource-dense maps where both agents saturate. A blindfold ablation, zeroing the heatmap at deployment, decomposes the advantage into two mechanisms: training-time stabilisation, which dominates where the credit assignment is hard and survives blinding on the dense map, and deployment-time inference, whose reliance shrinks as fog thins on the sparse map. We conclude that opponent-goal inference is a stability-and-transfer mechanism whose value is governed by measurable boundary conditions: visibility (fog thickness), opponent intent, and resource density.

0.26

Bayesian Replicator Dynamics and the Inversion of Strict Dominance in Bimatrix Games

cs.GT cs.MA ·2026-10-26 ·Jaime Ruiz-Serra, Nihat Ay, Michael Harré
similarity 0.59
Abstract · 18 pages, 3 figures

Replicator dynamics, the central model of evolutionary game theory, describe populations evolving under selection and agents learning by trial and error. They also admit a third use: continuous-time Bayesian inference, in which an agent planning against an opponent accumulates evidence for each candidate strategy. Here we show that this use divides all two-player games into two classes. With the standard expected-utility payoff, the dynamics can be expressed as Bayesian updating only in games (with any number of actions) where no player has a dominant strategy. The logarithmic payoff of Ay and Erb (2005) admits the Bayesian representation in every game. Coordination, anti-coordination, and cyclic games share qualitative dynamics under both payoff definitions, with equilibria displaced and selection thresholds shifted. In contrast, the flows of every game with a dominant strategy are reversed between the payoff definitions, with the strictly dominant strategy eliminated under logarithmic payoffs. Cooperation therefore emerges in the Prisoner's Dilemma, and games of common interest converge to mutual defection. For two-action games the classification is complete and rests on an exact Hamiltonian structure shared by both payoff definitions. The structure gives a behavioural test: cycles in the classic Matching Pennies game have amplitude-independent period (isochronous) under logarithmic payoffs, but not under expected utility. Logarithmic evidence integration thus determines which strategic outcomes dynamical selection can reach, wherever learning approximates Bayesian updating.

0.23

A self-organizing mechanism for collective foraging: recruitment cascades couple Levy search to a clustered maximum-entropy resource field

cs.DC physics.soc-phcs.SImath-ph+1 ·2026-10-17 ·Galen J. Wilkerson
code/data similarity 0.59
Abstract · 21 pages, 19 figures (7 main + 12 SI), 1 tables, Code and data: https://github.com/galenwilkerson/collective-foraging-cascades

Foraging recruitment is modeled as a contagion: an agent that finds a resource triggers a linear-threshold cascade on the group's communication network. Because activation is degree-normalized, crowding shuts the cascade off, so the swarm aggregates on a resource and then disperses to explore again. Acting on the cascade moves agents in space, and that motion rewires the network, so recruitment and exploration are one coupled process; removing this coupling alone abolishes the self-limitation. Recruitment spreads only within a connectivity window, bounded below by percolation onset and above by degree-blocking. The swarm self-organizes to the near-critical edge of this window -- self-organized quasi-criticality: recruitment sits near but below the critical point without settling onto a clean, size-invariant critical state, and the activity spectrum has a finite correlation time (Lorentzian-like, not 1/f), consistent with local rather than global criticality. Recruitment raises harvest up to 2.7x over solitary search on sparse, clustered resource fields and loses (down to 0.37x) on abundant or uniform ones; because resources generically aggregate, the favourable regime is the common one. The empirically motivated Levy search and the resource field it exploits are both least-committal: the search a maximum-caliber walk, and the field a maximum-entropy point process whose generic, aggregation-set sign is clustered (attractive). The search exponent that maximizes harvest tracks the field's fractal dimension (a heavier-tailed, more ballistic search for more strongly clustered fields). These are one coupled mechanism: heavy-tailed Levy exploration crosses the field's sparse voids while recruitment cascades exploit its clusters, so one maximum-entropy geometry binds exploration and recruitment into a single self-organizing cycle.

0.40

Bandits with Probing: Optimal Coverage and the Role of Feedback

cs.LG cs.DSstat.ML ·2026-09-14 ·Yongjie Guan
similarity 0.59
Abstract · 40 pages, 1 table

In bandits with probing, a learner selects at most $k$ of $n$ arms per round, earns the largest of their rewards, and competes with the best fixed single arm. For independent arms with i.i.d. rewards in $[0,1]$ and $2\le k<n$, the minimax regret is $Θ\bigl(\frac{n-k}{n}\min\{T,n/k\}\bigr)$, the cost of locating an unknown good arm, and observing only the maximum suffices to attain it. In particular, two probes give $Θ(\min\{T,n\})$ regret, which resolves two open questions of Bhaskara et al. (2023) with weaker feedback. Our policy turns the probing surplus, the excess of the maximum over each probed arm, into exploration capital, and a permanent random core yields the sharp dependence on $k$. On arbitrary fixed reward arrays, same-round contrasts between blocks of arms attain the same rate, because the surplus pays for the stability of mirror descent. Winner feedback, the maximum together with its winning label, instead incurs an additional learning cost under joint i.i.d. rewards and on fixed arrays. We characterize this cost even when values are revealed only intermittently, using policies that know neither the horizon nor the revelation rate. For three independent arms and two probes, exact maxima, Bernoulli-rounded maxima with winning labels, and winning labels alone have minimax regret $Θ(1)$, $Θ(\sqrt T)$, and $Θ(T)$: rounding preserves conditional means but not the rate.

0.25