Katkat
Back

Optimize a Two-Box Place-or-Take Game

Jane StreetSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenStatistics & Math

Last updated

Analyze and optimize a 100-turn, two-box stochastic game with capacity constraints and opaque states. Derive the optimal decision policy, examine boundary/edge cases, and evaluate how the strategy changes when core assumptions are relaxed.

Problem Description

You are playing a 100-turn single-player game involving two opaque boxes, Box A and Box B. Both boxes are initially empty, and each box has a capacity of exactly 1 coin. You cannot observe whether either box currently contains a coin.

On each turn t from 1 to 100, you must choose exactly one of three actions:

  1. PLACE: Nature attempts to deposit a coin. With probability p, the coin is directed to Box A; with probability 1 - p, it is directed to Box B (0 < p < 1). If the target box already contains a coin, the coin overflows and is lost.
  2. TAKE_A: You open Box A and collect its contents (yielding 1 coin if full, 0 if empty). Box A is left empty. Box B is untouched.
  3. TAKE_B: You open Box B and collect its contents (yielding 1 coin if full, 0 if empty). Box B is left empty. Box A is untouched.

Your goal is to maximize the expected total number of coins collected across all 100 turns.

Tasks

  1. Model & Assumptions: Formulate the state of the system. State the necessary assumptions regarding independence, information, and risk neutrality.
  2. Policy Derivation: Without loss of generality, assume p >= 0.5. Derive the optimal policy in the steady-state / asymptotic regime. Specifically, determine the conditions under which you should harvest both boxes versus harvesting only Box A, and calculate the optimal number of PLACE actions between harvests.
  3. Finite Horizon & Edge Cases: Explain how the optimal strategy adjusts as the game approaches turn 100 (terminal boundary effects). Analyze the edge cases p = 0.5 and p -> 1.
  4. Relaxing Assumptions: Describe how the optimal strategy shifts if:
    • Box capacity is unbounded (C = infinity).
    • The parameter p is initially unknown and must be inferred from the outcomes of TAKE actions.
    • Each box has an independent per-turn hazard rate q of being cleared by the house if uncollected.

Hints

Hint 1

Because the boxes are opaque and capacity is 1, track your belief state as the pair of probabilities (P(Box A has a coin), P(Box B has a coin)) as a function of the number of PLACE actions since each box was last emptied.

Hint 2

For the bulk of the 100 turns, model the game as a renewal reward process to maximize the expected coins collected per turn across repeating cycles.

Hint 3

Notice that if p is sufficiently close to 1, harvesting Box B is suboptimal because spending a turn to take from Box B yields a lower expected rate of return than running another cycle on Box A alone.

Follow-up questions

  • At exactly what critical value of p does it become optimal to completely abandon Box B and only cycle between PLACE and TAKE_A?
  • If p is unknown with a Beta(1, 1) prior, how does a TAKE action create an exploration-exploitation trade-off, and why does an empty harvest provide information?
  • How does the dynamic programming backward induction change in the final 5 turns compared to the stationary renewal cycle?