Paper: arXiv 2306.12658

Authors: Erhan Bayraktar, Bingyan Han

Abstract

We develop a fitted value iteration (FVI) method to compute bicausal optimal transport (OT) where couplings have an adapted structure. Based on the dynamic programming formulation, FVI adopts a function class to approximate the value functions in bicausal OT. Under the concentrability condition and approximate completeness assumption, we prove the sample complexity using (local) Rademacher complexity. Furthermore, we demonstrate that multilayer neural networks with appropriate structures satisfy the crucial assumptions required in sample complexity proofs. Numerical experiments reveal that FVI outperforms linear programming and adapted Sinkhorn methods in scalability as the time horizon increases, while still maintaining acceptable accuracy.

Complexity vs Empirical Score

  • Math Complexity: 0.0/10
  • Empirical Rigor: 0.0/10
  • Quadrant: Philosophers — conceptual discussion, limited math and data

Why this score: Scoring failed: Could not find valid JSON in LLM response: line 1 column 1 (char 0)

Research Flowchart

  flowchart TD
    A["Research Goal: Compute Bicausal Optimal Transport (OT)<br>for long time horizons efficiently"] --> B["Input: Dynamic Programming formulation<br>& Adapted Couplings"]
    B --> C["Fitted Value Iteration (FVI)<br>with Function Approximators"]
    C --> D["Theoretical Analysis<br>(Rademacher Complexity under<br>Concentrability & Completeness)"]
    C --> E["Neural Network Design<br>(Structured MLPs for Value Functions)"]
    D & E --> F["Numerical Experiments<br>(Comparison with LP & Adapted Sinkhorn)"]
    F --> G["Key Outcomes: Proven Sample Complexity<br>& Superior Scalability over Time Horizon"]