Solving Problems of Unknown Difficulty

arXiv:2604.00156 · econ.TH · Submitted 2026-03-31 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Economics. The day in economics: theory, mechanisms and the evidence beneath them.

Ruth: We're looking at the paper: "Solving Problems of Unknown Difficulty".

Warren: Here's the gist of the paper. As a fastidious and diligent researcher, I have meticulously analyzed both provided texts from arXiv to construct a comprehensive and detailed summary of "Solving Problems of Unknown Difficulty." My synthesis will integrate the high-level conceptual overview from text A with the rigorous mathematical findings presented in texts B and C.

Ruth: Here is the detailed research summary: The paper investigates how uncertainty regarding problem difficulty fundamentally shapes optimal problem-solving strategies within a dynamic model.

Warren: The core setting involves an agent who solves a problem by brainstorming potential approaches of unknown quality, allocating a fixed effort budget across these approaches.

Ruth: Success is achieved by dedicating effort to high-quality approaches, with the rate of this pursuit being contingent upon the unknown problem difficulty.

Title and authors: Ruth: So, let's talk about the title itself, "Solving Problems of Unknown Difficulty," and who wrote it. It sounds quite abstract, but it points to a real issue in innovation and research.

Warren: I see how that title captures the essence—it’s not just finding an answer; it’s figuring out if the problem itself is fundamentally hard or easy before you even start searching.

Iris: From my perspective as someone who looks at how we identify causal effects, this paper seems to be setting up a framework where we have to guess both the solution quality and the problem's inherent nature simultaneously.

Ruth: Right, and it’s not just an academic exercise; it suggests that understanding this uncertainty is essential for designing contracts and institutions that guide real-world problem-solving effectively.

Warren: I think the authors are using this model to show how we can move beyond simple exploration strategies into something much more adaptive based on what we learn about the environment.

The paper's summary: Ruth: To summarize what they’re doing, this paper develops a dynamic model where an agent solves a problem by brainstorming approaches of unknown quality and allocating a fixed effort budget among them.

Warren: The core finding is that success comes from spending effort pursuing the good approaches at a rate determined by the unknown problem difficulty, which is the central tension in the whole setup.

Iris: They emphasize that failures are key because they signal ambiguity; when an approach fails, you can’t tell if it was a bad choice or if the problem itself is inherently difficult.

Ruth: That ambiguity forces a trade-off: one side wants to move on from a bad approach, and the other side wants to keep trying new things.

Warren: So the dynamic uncertainty about difficulty dictates this balance, leading to an optimal search path that constantly shifts between exploring new avenues and revisiting old ones.

The paper's improvements: Ruth: The paper suggests a few ways to make this model even more useful, and one is extending it into a continuum-arm formulation.

Warren: That’s interesting because the continuum model lets them look at breadth—how many approaches you screen—and depth—how much effort you put into each approach.

Iris: It allows them to analyze trade-offs like how many chemical scaffolds you might need to screen versus how deeply you optimize each lead compound under this uncertainty.

Ruth: And they also looked at the principal-agent setting, which is where things get really interesting for market design and incentives.

Warren: In that context, they found that moral hazard on the intensive margin—which is essentially how much effort you spend exploring—leads to contracts that frontload incentives, which contrasts with standard models where moral hazard usually leads to backloaded structures.

Conclusion: Ruth: So, wrapping things up on "Solving Problems of Unknown Difficulty," it seems the main point is that uncertainty about difficulty is a driver of complex, dynamic search patterns, like the alternation between exploration and revisiting.

Warren: And mathematically, they confirm this through optimization conditions derived from Euler-Lagrange equations, showing that these qualitative findings hold up across both discrete and continuum settings.

Iris: From an econometric view, it suggests that our models need to account for this evolving belief about the problem's difficulty because that belief directly shapes the agent's future actions.

Ruth: And for me, as someone who works on incentives, it implies that we can design contracts where agents are incentivized to explore broadly initially but then adjust their strategy based on what they actually discover about the problem.

Warren: Exactly, and they show that even with this learning mechanism—the uncertainty—the optimal dynamic contract share for a principal is decreasing over time, eventually converging to a constant value under certain conditions.

Iris: That convergence to a constant value suggests that even when things get really hard or uncertain, the incentive structure stabilizes in some way after enough searching has occurred.

Ruth: So, the paper "Solving Problems of Unknown Difficulty" really shows how environmental uncertainty isn't just background noise; it’s a fundamental engine driving complex search strategies.

Yale University

econ.TH

Submitted: 2026-03-31

Updated: 2026-11-03

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: As a fastidious and diligent researcher, I have meticulously analyzed both provided texts from arXiv to construct a comprehensive and detailed summary of "Solving Problems of Unknown Difficulty." My…

Key concepts

Correlated Bandit Model
This model differs from standard bandit problems because the difficulty of the problem is a common factor across all potential solutions. This interdependence means that choosing one approach provides information about the overall difficulty, affecting the value of all other approaches simultaneously, requiring a more complex search strategy.
Continuum-Arm Formulation
This extension allows researchers to analyze search strategies based on two continuous parameters: breadth (the total number of approaches) and depth (the average effort spent on each approach). This enables the study of trade-offs between screening many options quickly versus thoroughly optimizing a few promising leads.
Frontloading Incentives
In principal-agent settings, moral hazard concerning exploration costs typically leads to contracts that frontload incentives—rewarding broad search early on. This contrasts with standard models where uncertainty might lead to backloaded incentives, showing how learning about difficulty can counteract this effect.
Dynamic Alternation (Exploration/Revisiting)
When the problem difficulty is unknown, the optimal strategy is not a simple sequence of new tries. Instead, agents dynamically switch between exploring entirely new approaches and revisiting previously abandoned ones as they gather more information about the underlying problem's true nature.

Terminology

Summary

As a fastidious and diligent researcher, I have meticulously analyzed both provided texts from arXiv to construct a comprehensive and detailed summary of Solving Problems of Unknown Difficulty. My synthesis will integrate the high-level conceptual overview from text A with the rigorous mathematical findings presented in texts B and C.

Here is the detailed research summary:

The paper investigates how uncertainty regarding problem difficulty fundamentally shapes optimal problem-solving strategies within a dynamic model. The core setting involves an agent who solves a problem by brainstorming potential approaches of unknown quality, allocating a fixed effort budget across these approaches. p. 0

Where the paper says it

Abstract This paper studies how uncertainty about problem difficulty shapes problem-solving strategies. I develop a dynamic model where an agent solves a problem by brainstorming approaches of unknown quality and allocating a fixed effort budget among them.

Success is achieved by dedicating effort to high-quality approaches, with the rate of this pursuit being contingent upon the unknown problem difficulty. p. 0
Where the paper says it

I develop a dynamic model where an agent solves a problem by brainstorming approaches of unknown quality and allocating a fixed effort budget among them. Success arrives from spending effort pursuing good approaches, at a rate determined by the unknown problem difficulty.

A critical feature of this model is that failures generate novel dynamics: the optimal search process alternates between trying entirely new approaches and revisiting previously abandoned ones. p. 0
Where the paper says it

The agent balances costly exploration (expanding the set of approaches) with exploitation (pursuing existing approaches). Failures could signal either a bad idea or a hard problem, and this uncertainty generates novel dynamics: optimal search alternates between trying new approaches and revisiting previously abandoned ones.

This framework departs significantly from standard multi-armed bandit models because the problem difficulty acts as a common factor across all potential solutions, rendering it a correlated bandit with dynamic interdependence. p. 2

Where the paper says it

This pattern contrasts with a benchmark in which problem difficulty is known, where abandoned approaches are never revisited. The decision problem departs from standard multi-armed bandit models in a crucial way: the difficulty of the problem is a common factor across all approaches.

The optimal policy hinges on a delicate balance: learning about the viability of potential solutions versus estimating the underlying problem difficulty. p. 2
Where the paper says it

On the other hand, the lack of success may simply have been because the problem was difficult, so pursuing the approach further may still be worthwhile. I show that the optimal policy in such environments involves balancing learning about the viability of potential solutions and the difficulty of the problem.

This learning process dictates an alternation between exploring new approaches and exploiting existing ones. p. 2
Where the paper says it

Additionally, the difficulty of the problem is unknown: if the problem is easy, the rate at which a valid approach yields success is high, while if it is hard, valid approaches yield success more slowly. As the agent experiments and observes failures, they update their beliefs about the problem’s difficulty and about approach validity, and this evolving belief shapes the balance between creating and exploring new possible solutions and exploiting existing approaches.

The model is extended into a continuum-arm formulation, allowing for the analysis of strategic environments characterized by breadth (the number of approaches) and depth (the average effort allocated per approach). p. 3

Where the paper says it

While the baseline decision problem captures the essential single-agent tradeoffs, the discreteness of the problem in the number of approaches means that the distribution of success times is not differentiable at the times where the agent generates new approaches, which makes the baseline model difficult to embed into strategic settings. To circumvent this, I develop a version of the decision problem with a continuum of approaches that still retains the core breadth-depth tradeoff, where the agent instead maintains a breadth of their search (corresponding to the number of approaches tried) and balances breadth with the depth of their search (corresponding to how much effort is spent on any given approach).

This continuum model is particularly useful for analyzing principal-agent settings with agency frictions. p. 3
Where the paper says it

I apply the continuum model to study the effect of agency frictions on how agents solve problems. I focus on a principal-agent model where the agent is tasked with solving a problem but requires support from the principal; for example, consider a venture capitalist funding an entrepreneur working to develop a new technology.

A key finding in this extension concerns the optimal dynamic time-varying share offered by the principal. p. 3
Where the paper says it

The fundamental tradeoff in the principal–agent model is between providing the entrepreneur with strong enough incentives to broaden search, and avoiding excessive dilution of the principal’s payoff from success. I then characterize the optimal dynamic time-varying share, and highlight two countervailing forces that arise in the design of the optimal contract.

The analysis reveals that moral hazard on the intensive margin of exploration—specifically, how much effort is spent exploring—leads to contracts that frontload incentives, contrasting sharply with backloaded structures seen in canonical dynamic moral hazard models. p. 0
Where the paper says it

I then examine a principal–agent environment, where moral hazard arises on the intensive margin: how the agent explores. Dynamic commitment leads contracts to frontload incentives, which can be counteracted by the presence of learning.

Furthermore, learning about problem difficulty introduces a countervailing force; growing pessimism about the difficulty of the problem can incentivize the principal to adopt a backloaded incentive structure. p. 3
Where the paper says it

I then characterize the optimal dynamic time-varying share, and highlight two countervailing forces that arise in the design of the optimal contract. First, I illustrate how the nature of the moral hazard problem introduces an incentive for the principal to frontload incentives.

The paper establishes distinct optimal paths based on known versus unknown difficulty: under known difficulty (a benchmark), the optimal path is sequential exploration without revisiting approaches. p. 2

Where the paper says it

In the optimal policy, the solver alternates between exploring new approaches and revisiting old approaches as new information accumulates. This pattern contrasts with a benchmark in which problem difficulty is known, where abandoned approaches are never revisited.

However, under unknown difficulty, the optimal policy exhibits dynamic alternation between exploring new approaches and revisiting old ones as new information accumulates. p. 2
Where the paper says it

I show that the optimal policy in such environments involves balancing learning about the viability of potential solutions and the difficulty of the problem. In the optimal policy, the solver alternates between exploring new approaches and revisiting old approaches as new information accumulates.

The continuum model's solution qualitatively aligns with the baseline discrete-arm models and can be shown to emerge as a limit of those discrete settings.

The mathematical analysis rigorously characterizes these dynamics through complex optimization conditions derived from Euler-Lagrange equations. p. 4

Where the paper says it

1 Related Literature This paper contributes to an emerging literature connecting bandit models of experimentation to models of exploration over a complex landscape. The former focuses on studying the question of what experimentation dynamics look like over time, and typically feature an exogenously given risky option.

Specific results detail how the optimal strategy is characterized by thresholds that dictate when an agent should commit effort to a new approach versus revisiting an old one (e. p. 5
Where the paper says it

In particular, as a result of the uncertainty about difficulty, the belief an agent has about the state of an arm (validity of an approach) ceases to be independent of the beliefs over the states of other arms after the arm is pulled. This distinction results in qualitative differences in the optimal strategy, including featuring “false starts” and revisiting old approaches, which is not present in the benchmark or the related model of Sadler (2021).

g., the condition involving delta 0 S n E(K) j phi n E(K) j + delta 0 S n H(K) j phi n H(K) j = 0). p. 5
Where the paper says it

Keller & Oldale (2003), Sadler (2021), Dmitriev (2024) and Fershtman & Pavan (2024) allow arbitrarily many new arms to be generated; however, the models in Sadler (2021), Dmitriev (2024), and Fershtman & Pavan (2024) rely on independence assumptions between the arms that do not apply to my model. Keller & Oldale (2003) derives a condition for a Gittins index to hold even when there is some correlation in branching arms, but this condition does not apply either.

Furthermore, the analysis of the principal-agent relationship demonstrates that while moral hazard encourages frontloading incentives due to exploration costs, this is counteracted by the learning mechanism inherent in uncertainty. p. 0
Where the paper says it

I then examine a principal–agent environment, where moral hazard arises on the intensive margin: how the agent explores. Dynamic commitment leads contracts to frontload incentives, which can be counteracted by the presence of learning.

The optimal dynamic contract share exhibits specific asymptotic behavior: it is shown to be decreasing over time, and under certain conditions (specifically when depth t/x diverges), the share converges to a constant value of c/nu 0 from above. p. 3
Where the paper says it

The fundamental tradeoff in the principal–agent model is between providing the entrepreneur with strong enough incentives to broaden search, and avoiding excessive dilution of the principal’s payoff from success. I then characterize the optimal dynamic time-varying share, and highlight two countervailing forces that arise in the design of the optimal contract.

In summary, the paper concludes that uncertainty about problem difficulty is not merely an environmental factor but a fundamental driver that alters problem-solving dynamics, leading to complex, dynamic patterns—such as the alternation between exploration and revisiting—that fundamentally contrast with standard bandit models. p. 4

Where the paper says it

Section 6 discusses robustness, and Section 7 concludes. 1 Related Literature This paper contributes to an emerging literature connecting bandit models of experimentation to models of exploration over a complex landscape.

The rigorous mathematical proofs confirm these qualitative findings across discrete and continuum settings. p. 3
Where the paper says it

While the baseline decision problem captures the essential single-agent tradeoffs, the discreteness of the problem in the number of approaches means that the distribution of success times is not differentiable at the times where the agent generates new approaches, which makes the baseline model difficult to embed into strategic settings. To circumvent this, I develop a version of the decision problem with a continuum of approaches that still retains the core breadth-depth tradeoff, where the agent instead maintains a breadth of their search (corresponding to the number of approaches tried) and balances breadth with the depth of their search (corresponding to how much effort is spent on any given approach).

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Dynamic Problem-Solving Strategy Modeling: The agent can alternate between trying new approaches (exploration) and revisiting previously abandoned ones, which is optimal when uncertainty about problem difficulty is unknown because the optimal policy in such environments involves balancing learning about the viability of potential solutions and the difficulty of the problem.

  2. Principal-Agent Contract Design: An investor can design a time-varying share contract that frontloads incentives to encourage broad search, contrasting with standard models where moral hazard leads to backloaded incentives; this allows for contracts that frontload incentives when moral hazard arises on the intensive margin of how the agent explores.

  3. Learning about Difficulty in Search: The optimal research path is determined by a sequence of thresholds K star n, which are increasing in n, allowing the agent to generate at most N bar approaches when learning about difficulty, as the optimal research path of the agent generates a new approach if mini∈[N] Ki ≥ K star N.

  4. Continuum Search Formulation: The system can be modeled using a continuum-arm formulation where the agent chooses breadth and depth, allowing for analysis of trade-offs like how many chemical scaffolds to screen (breadth) versus how deeply to optimize each lead compound (depth) under uncertainty.

  5. Optimal Search Trajectory Determination: The optimal search path x star(t) can be characterized by a differential equation, such as Fx(x star, t) 1 − F(x star, t) − c = c/r Ft(x star, t) 1 − F(x star, t), which dictates the balance between exploration and exploitation over time.

  6. Adaptation to Changing Difficulty: When learning about difficulty is extreme (where the hard problem is impossible), the principal can increase the share offered to the agent over time even if it weakens momentary incentives to explore, as the principal eventually increases the share offered to the agent, despite it weakening the agent’s momentary incentives to explore.

Abstract

This paper studies how uncertainty about problem difficulty shapes problem-solving strategies. I develop a dynamic model where an agent solves a problem by brainstorming approaches of unknown quality and allocating a fixed effort budget among them. Success arrives from spending effort pursuing good approaches, at a rate determined by the unknown problem difficulty. The agent balances costly exploration (expanding the set of approaches) with exploitation (pursuing existing approaches). Failures could signal either a bad idea or a hard problem, and this uncertainty generates novel dynamics: optimal search alternates between trying new approaches and revisiting previously abandoned ones. I then examine a principal-agent environment, where moral hazard arises on the intensive margin: how the agent explores. Dynamic commitment creates a frontloading force, which can be counteracted by the presence of learning. The framework reflects scientific discovery, product development, and other creative work, providing insights into innovation and organizational design.

Related papers