Solving Problems of Unknown Difficulty

1. Problem Statement

The paper addresses the fundamental economic problem of strategic experimentation under uncertainty regarding both solution quality and problem difficulty.

• The Core Challenge: Agents (e.g., scientists, entrepreneurs) must solve a problem by searching for a "valid" approach among many possibilities. However, they face a dual uncertainty:
  1. Approach Validity: They do not know if a specific approach is valid (capable of solving the problem) or flawed.
  2. Problem Difficulty: They do not know if the problem is "easy" (high success rate for valid approaches) or "hard" (low success rate).
• The Ambiguity of Failure: A critical feature of the model is that a failure (lack of success) is ambiguous. It could signal that the chosen approach is bad, or that the problem is inherently difficult. This ambiguity creates a tradeoff: should the agent abandon the current approach to try a new one (exploration), or persist with the current one (exploitation), hoping the problem is just hard and time will yield a result?
• Agency Frictions: The paper extends this to a Principal-Agent setting where the Principal (investor) cannot observe the Agent's (entrepreneur) specific allocation of effort between exploring new ideas and deepening existing ones (moral hazard on the intensive margin).

2. Methodology

The author employs a dynamic, continuous-time framework combining Multi-Armed Bandit (MAB) theory with Optimal Control and Contract Theory.

A. Baseline Model (Discrete Approach)

• Setup: An agent allocates a unit of effort over time to a set of approaches.
• States:
  • Approaches are drawn from a Bernoulli distribution (valid with probability $\nu_0$).
  • Problem difficulty $\theta \in \{E, H\}$ (Easy/Hard) is drawn with probability $\delta_0$.
  • Success arrives via a Poisson process with rate $\lambda_\theta$ if the approach is valid.
• Actions: The agent can either allocate effort to existing approaches or pay a cost $c$ to "brainstorm" a new approach.
• State Space: Defined by the vector of historical effort exerted on each approach. The state is not just the current belief, but the history of effort, which serves as a sufficient statistic for beliefs due to the correlation induced by the unknown difficulty.

B. The Continuum Limit Model

To facilitate the analysis of dynamic contracts and strategic interactions, the author derives a continuum limit of the discrete model.

• Breadth vs. Depth: Instead of discrete arms, the agent chooses a "breadth" $x(t)$ (number of approaches) and a "depth" $d(t)$ (effort per approach).
• Constraint: The agent has a unit effort budget: $x(t)d(t) = t$ (assuming constant expansion).
• Success Distribution: The breakthrough distribution $F(x, t)$ is derived as the limit of the discrete Poisson processes, resulting in a double-exponential form that captures the correlation between approaches induced by the unknown difficulty.

C. Solution Techniques

• Interchange Arguments: The author uses interchange arguments (perturbing the timing of effort allocation) to derive necessary conditions for optimality.
• Gittins Index Adaptation: The paper demonstrates why standard Gittins index theorems fail here (due to the "restless" nature of arms caused by the common difficulty state) and derives a new characterization based on threshold sequences.
• Calculus of Variations: Used to solve the Principal-Agent problem, imposing the agent's Euler-Lagrange condition as a constraint on the contract design.

3. Key Contributions

A. Theoretical Innovation: Correlated Bandits with Unknown Difficulty

The paper identifies that uncertainty about problem difficulty creates endogenous correlation between arms. Learning about one arm (e.g., failing on it) updates beliefs about the difficulty of the entire problem, thereby updating beliefs about all other arms. This breaks the independence assumption standard in MAB literature.

B. Optimal Search Dynamics: "False Starts" and Revisiting

Unlike standard models where abandoned arms are never revisited, the optimal policy in this environment involves:

1. Task Juggling: The agent splits effort across multiple approaches simultaneously.
2. Revisiting (False Starts): As the agent learns the problem might be hard (due to failures), the posterior probability that a previously abandoned approach was actually valid increases. Consequently, the optimal policy involves alternating between exploring new approaches and revisiting old ones.
3. Increasing Thresholds: The amount of effort required before switching to a new approach increases over time as the agent becomes more pessimistic about difficulty.

C. Contract Theory: Frontloading vs. Backloading

The paper challenges the canonical result in dynamic moral hazard literature (e.g., Rogerson 1985, Sannikov 2008) that optimal contracts are backloaded (incentives increase over time).

• Intensive Margin Moral Hazard: Because the moral hazard arises from how the agent explores (breadth vs. depth) rather than whether they work, the Principal has a strong incentive to frontload incentives.
• Mechanism: The Principal offers a high share of success early on to induce the agent to explore broadly. This early exploration creates a persistent increase in the future success rate (a positive externality of exploration).
• Countervailing Force (Learning): If the agent learns the problem is likely impossible (or very hard), the Principal may need to backload incentives (increase the share later) to prevent the agent from giving up. This interaction can lead to non-monotonic optimal contracts (e.g., high initial share, dip, then rise).

4. Key Results

1. The Optimal Policy (Single Agent)

• Benchmark (Known Difficulty): The agent works sequentially on one approach until a threshold $K^*$ is reached, then moves to the next. No revisiting occurs.
• Unknown Difficulty: The agent works on the first approach until $K^*_1$, then brainstorms a second. They then work on the second until the first reaches $K^*_1$, then work on both until both reach $K^*_2$, and so on.
• Threshold Sequence: The sequence of thresholds $\{K^*_n\}$ is strictly increasing. The agent spends more effort on later approaches because the belief that the problem is hard has increased, making it more likely that previous failures were due to difficulty rather than invalidity.

2. The Continuum Model Solution

• The optimal breadth path $x^*(t)$ is concave when learning about difficulty is present.
• The optimal depth (effort per approach) increases over time.
• The model is rigorously shown to be the limit of the discrete model as the number of approaches goes to infinity and the cost per approach goes to zero.

3. Principal-Agent Dynamics

• Static Contract: Under a fixed equity share, the agent under-explores (searches too narrowly) compared to the first-best because they bear the full cost of creativity but only receive a fraction of the reward.
• Dynamic Contract (No Learning): If difficulty is known, the optimal contract features a strictly decreasing share over time. The Principal frontloads incentives to induce early broad search.
• Dynamic Contract (With Learning):
  • If the problem is potentially impossible ($\lambda_H = 0$), the Principal may increase the share over time to keep the agent from quitting (backloading).
  • If the problem is hard but possible ($\lambda_H > 0$), the frontloading force (due to the persistent benefits of early exploration) eventually dominates, but the contract may exhibit non-monotonicity in intermediate periods.
  • Result: The optimal contract can reward early failure (by maintaining high equity) to encourage persistence, contrasting with standard models where failure leads to termination or reduced incentives.

5. Significance and Implications

• Organizational Design: The paper provides a theoretical basis for why innovative firms (e.g., R&D labs, venture capital) often structure incentives to reward early-stage exploration and tolerate failure. It suggests that "frontloading" equity or bonuses is optimal when the agent's search strategy (breadth) has persistent positive externalities.
• Scientific Discovery: The model explains the phenomenon of "revisiting old ideas." In scientific research, as time passes without a breakthrough, the community may realize the problem is harder than thought, leading to a re-evaluation of previously discarded hypotheses as potentially valid but simply requiring more time.
• Contract Theory: It identifies a distinct class of moral hazard (intensive margin of exploration) that reverses the standard backloading result. This is crucial for designing contracts in creative industries, startups, and research grants.
• Methodological Contribution: The derivation of the continuum limit for correlated bandits provides a tractable framework for analyzing complex search problems that were previously intractable due to high-dimensional state spaces.

In summary, Nicholas Wu's paper fundamentally alters our understanding of problem-solving under uncertainty by showing that ambiguity about difficulty forces agents to revisit abandoned paths and that optimal contracts for creative work must frontload incentives to harness the persistent benefits of broad exploration, unless learning about extreme difficulty forces a shift toward backloading to prevent abandonment.