Created
February 22, 2026 22:15
-
-
Save jbdamask/ef1e59955eb671582932b3954ee20575 to your computer and use it in GitHub Desktop.
NowIGetIt: multi.pdf
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html lang="en"> | |
| <head> | |
| <meta charset="UTF-8"> | |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> | |
| <title>MA-CMAB: Smart Item Allocation Under Uncertainty</title> | |
| <style> | |
| @import url('https://fonts.googleapis.com/css2?family=Inter:wght@300;400;500;600;700;800;900&family=JetBrains+Mono:wght@400;600&display=swap'); | |
| * { margin: 0; padding: 0; box-sizing: border-box; } | |
| :root { | |
| --bg: #0a0a0f; | |
| --card: #12121a; | |
| --card-hover: #1a1a28; | |
| --accent: #6366f1; | |
| --accent2: #8b5cf6; | |
| --accent3: #ec4899; | |
| --green: #10b981; | |
| --orange: #f59e0b; | |
| --text: #e2e8f0; | |
| --text-dim: #94a3b8; | |
| --border: #1e1e2e; | |
| } | |
| html { scroll-behavior: smooth; } | |
| body { | |
| font-family: 'Inter', sans-serif; | |
| background: var(--bg); | |
| color: var(--text); | |
| overflow-x: hidden; | |
| line-height: 1.7; | |
| } | |
| /* ── Scrollbar ── */ | |
| ::-webkit-scrollbar { width: 6px; } | |
| ::-webkit-scrollbar-track { background: var(--bg); } | |
| ::-webkit-scrollbar-thumb { background: var(--accent); border-radius: 3px; } | |
| /* ── Canvas BG ── */ | |
| #bg-canvas { | |
| position: fixed; top: 0; left: 0; | |
| width: 100%; height: 100%; | |
| z-index: 0; pointer-events: none; | |
| } | |
| /* ── Nav ── */ | |
| nav { | |
| position: fixed; top: 0; left: 0; right: 0; | |
| z-index: 100; | |
| backdrop-filter: blur(20px); | |
| background: rgba(10,10,15,.8); | |
| border-bottom: 1px solid var(--border); | |
| padding: 0 2rem; | |
| display: flex; align-items: center; justify-content: space-between; | |
| height: 60px; | |
| } | |
| nav .logo { | |
| font-weight: 800; font-size: 1.1rem; | |
| background: linear-gradient(135deg, var(--accent), var(--accent3)); | |
| -webkit-background-clip: text; -webkit-text-fill-color: transparent; | |
| } | |
| nav .links { display: flex; gap: 1.5rem; } | |
| nav .links a { | |
| color: var(--text-dim); text-decoration: none; font-size: .85rem; | |
| font-weight: 500; transition: color .3s; | |
| } | |
| nav .links a:hover { color: var(--accent); } | |
| /* ── Sections ── */ | |
| section { | |
| position: relative; z-index: 1; | |
| max-width: 1100px; margin: 0 auto; | |
| padding: 6rem 2rem 4rem; | |
| } | |
| /* ── Hero ── */ | |
| .hero { | |
| min-height: 100vh; | |
| display: flex; flex-direction: column; | |
| justify-content: center; align-items: center; | |
| text-align: center; | |
| padding-top: 60px; | |
| } | |
| .hero .badge { | |
| background: rgba(99,102,241,.15); | |
| color: var(--accent); | |
| padding: .35rem 1rem; border-radius: 50px; | |
| font-size: .8rem; font-weight: 600; | |
| margin-bottom: 1.5rem; | |
| border: 1px solid rgba(99,102,241,.3); | |
| } | |
| .hero h1 { | |
| font-size: clamp(2.2rem, 5vw, 4rem); | |
| font-weight: 900; | |
| line-height: 1.1; | |
| margin-bottom: 1.5rem; | |
| background: linear-gradient(135deg, #fff 0%, #6366f1 50%, #ec4899 100%); | |
| -webkit-background-clip: text; -webkit-text-fill-color: transparent; | |
| } | |
| .hero p { | |
| max-width: 650px; | |
| color: var(--text-dim); | |
| font-size: 1.15rem; | |
| margin-bottom: 2.5rem; | |
| } | |
| .hero .cta { | |
| display: inline-flex; gap: 1rem; | |
| } | |
| .hero .cta a { | |
| padding: .75rem 2rem; border-radius: 12px; | |
| text-decoration: none; font-weight: 600; font-size: .95rem; | |
| transition: transform .2s, box-shadow .3s; | |
| } | |
| .hero .cta a:first-child { | |
| background: linear-gradient(135deg, var(--accent), var(--accent3)); | |
| color: #fff; | |
| box-shadow: 0 4px 25px rgba(99,102,241,.4); | |
| } | |
| .hero .cta a:last-child { | |
| background: rgba(255,255,255,.05); | |
| color: var(--text); | |
| border: 1px solid var(--border); | |
| } | |
| .hero .cta a:hover { transform: translateY(-2px); } | |
| .scroll-hint { | |
| margin-top: 3rem; | |
| animation: bounce 2s infinite; | |
| color: var(--text-dim); font-size: 1.5rem; | |
| } | |
| @keyframes bounce { | |
| 0%,100% { transform: translateY(0); } | |
| 50% { transform: translateY(8px); } | |
| } | |
| /* ── Section headers ── */ | |
| .section-label { | |
| font-size: .75rem; font-weight: 700; | |
| text-transform: uppercase; letter-spacing: 3px; | |
| color: var(--accent); margin-bottom: .5rem; | |
| } | |
| .section-title { | |
| font-size: clamp(1.8rem, 3vw, 2.5rem); | |
| font-weight: 800; margin-bottom: 1rem; | |
| } | |
| .section-desc { | |
| color: var(--text-dim); max-width: 700px; | |
| font-size: 1.05rem; margin-bottom: 3rem; | |
| } | |
| /* ── Cards Grid ── */ | |
| .cards { display: grid; grid-template-columns: repeat(auto-fit, minmax(280px,1fr)); gap: 1.5rem; } | |
| .card { | |
| background: var(--card); | |
| border: 1px solid var(--border); | |
| border-radius: 16px; | |
| padding: 2rem; | |
| transition: transform .3s, border-color .3s, box-shadow .3s; | |
| cursor: default; | |
| } | |
| .card:hover { | |
| transform: translateY(-4px); | |
| border-color: var(--accent); | |
| box-shadow: 0 8px 40px rgba(99,102,241,.15); | |
| } | |
| .card .icon { | |
| width: 48px; height: 48px; | |
| border-radius: 12px; | |
| display: flex; align-items: center; justify-content: center; | |
| font-size: 1.4rem; | |
| margin-bottom: 1rem; | |
| } | |
| .card h3 { font-size: 1.15rem; font-weight: 700; margin-bottom: .5rem; } | |
| .card p { color: var(--text-dim); font-size: .92rem; } | |
| /* ── Interactive Demo ── */ | |
| .demo-container { | |
| background: var(--card); | |
| border: 1px solid var(--border); | |
| border-radius: 20px; | |
| padding: 2.5rem; | |
| margin-top: 2rem; | |
| } | |
| .demo-controls { | |
| display: flex; flex-wrap: wrap; gap: 1rem; margin-bottom: 2rem; | |
| align-items: end; | |
| } | |
| .control-group { display: flex; flex-direction: column; gap: .3rem; } | |
| .control-group label { | |
| font-size: .78rem; font-weight: 600; | |
| color: var(--text-dim); text-transform: uppercase; letter-spacing: 1px; | |
| } | |
| .control-group input[type=range] { | |
| width: 180px; accent-color: var(--accent); | |
| } | |
| .control-group .val { | |
| font-family: 'JetBrains Mono', monospace; | |
| font-size: .85rem; color: var(--accent); | |
| } | |
| .btn-run { | |
| padding: .65rem 1.5rem; | |
| background: linear-gradient(135deg, var(--accent), var(--accent2)); | |
| color: #fff; border: none; border-radius: 10px; | |
| font-weight: 700; font-size: .9rem; | |
| cursor: pointer; transition: transform .2s; | |
| } | |
| .btn-run:hover { transform: scale(1.04); } | |
| .alloc-visual { | |
| display: flex; flex-wrap: wrap; gap: 1.5rem; | |
| justify-content: center; margin: 2rem 0; | |
| } | |
| .agent-box { | |
| background: rgba(255,255,255,.03); | |
| border: 1px solid var(--border); | |
| border-radius: 14px; | |
| padding: 1.2rem; | |
| min-width: 140px; text-align: center; | |
| transition: border-color .4s; | |
| } | |
| .agent-box.highlight { border-color: var(--green); box-shadow: 0 0 20px rgba(16,185,129,.2); } | |
| .agent-box .agent-label { | |
| font-weight: 700; font-size: .85rem; margin-bottom: .6rem; | |
| } | |
| .item-grid { display: flex; flex-wrap: wrap; gap: .4rem; justify-content: center; } | |
| .item-chip { | |
| width: 32px; height: 32px; | |
| border-radius: 8px; | |
| display: flex; align-items: center; justify-content: center; | |
| font-size: .7rem; font-weight: 700; | |
| transition: all .4s; | |
| opacity: 0; transform: scale(0); | |
| } | |
| .item-chip.show { opacity: 1; transform: scale(1); } | |
| .stats-row { | |
| display: flex; flex-wrap: wrap; gap: 1.5rem; margin-top: 1.5rem; | |
| justify-content: center; | |
| } | |
| .stat-box { | |
| text-align: center; | |
| background: rgba(255,255,255,.03); | |
| border-radius: 12px; padding: 1rem 1.5rem; | |
| min-width: 130px; | |
| } | |
| .stat-box .stat-val { | |
| font-family: 'JetBrains Mono', monospace; | |
| font-size: 1.4rem; font-weight: 800; | |
| } | |
| .stat-box .stat-label { | |
| font-size: .72rem; color: var(--text-dim); | |
| text-transform: uppercase; letter-spacing: 1px; | |
| margin-top: .25rem; | |
| } | |
| /* ── Regret Chart ── */ | |
| .chart-container { | |
| position: relative; | |
| background: var(--card); | |
| border: 1px solid var(--border); | |
| border-radius: 20px; | |
| padding: 2rem; | |
| margin-top: 2rem; | |
| } | |
| #regretCanvas { width: 100%; height: 350px; } | |
| /* ── Timeline / Algorithm ── */ | |
| .timeline { | |
| position: relative; | |
| padding-left: 2.5rem; | |
| margin-top: 2rem; | |
| } | |
| .timeline::before { | |
| content: ''; position: absolute; left: 8px; top: 0; bottom: 0; | |
| width: 2px; | |
| background: linear-gradient(180deg, var(--accent), var(--accent3)); | |
| } | |
| .timeline-item { | |
| position: relative; margin-bottom: 2rem; | |
| padding: 1.5rem; | |
| background: var(--card); | |
| border: 1px solid var(--border); | |
| border-radius: 14px; | |
| transition: border-color .3s; | |
| } | |
| .timeline-item:hover { border-color: var(--accent); } | |
| .timeline-item::before { | |
| content: ''; | |
| position: absolute; left: -2.1rem; top: 1.8rem; | |
| width: 14px; height: 14px; | |
| border-radius: 50%; | |
| background: var(--accent); | |
| border: 3px solid var(--bg); | |
| } | |
| .timeline-item .step-num { | |
| font-family: 'JetBrains Mono', monospace; | |
| font-size: .75rem; color: var(--accent); font-weight: 600; | |
| margin-bottom: .3rem; | |
| } | |
| .timeline-item h3 { font-size: 1.1rem; font-weight: 700; margin-bottom: .4rem; } | |
| .timeline-item p { color: var(--text-dim); font-size: .9rem; } | |
| /* ── Comparison Table ── */ | |
| .comparison-table { | |
| width: 100%; border-collapse: collapse; margin-top: 2rem; | |
| font-size: .9rem; | |
| } | |
| .comparison-table th, .comparison-table td { | |
| padding: 1rem 1.2rem; | |
| text-align: left; | |
| border-bottom: 1px solid var(--border); | |
| } | |
| .comparison-table th { | |
| font-weight: 700; font-size: .75rem; | |
| text-transform: uppercase; letter-spacing: 2px; | |
| color: var(--text-dim); | |
| background: rgba(255,255,255,.02); | |
| } | |
| .comparison-table td { color: var(--text); } | |
| .comparison-table tr:hover td { background: rgba(99,102,241,.05); } | |
| .tag { | |
| display: inline-block; padding: .2rem .6rem; border-radius: 6px; | |
| font-size: .75rem; font-weight: 600; | |
| } | |
| .tag-green { background: rgba(16,185,129,.15); color: var(--green); } | |
| .tag-orange { background: rgba(245,158,11,.15); color: var(--orange); } | |
| .tag-purple { background: rgba(139,92,246,.15); color: var(--accent2); } | |
| /* ── Key Insight Callout ── */ | |
| .callout { | |
| background: linear-gradient(135deg, rgba(99,102,241,.08), rgba(236,72,153,.08)); | |
| border: 1px solid rgba(99,102,241,.25); | |
| border-radius: 16px; | |
| padding: 2rem; | |
| margin: 2rem 0; | |
| display: flex; gap: 1rem; align-items: flex-start; | |
| } | |
| .callout .callout-icon { font-size: 1.5rem; flex-shrink: 0; margin-top: .2rem; } | |
| .callout h4 { font-weight: 700; margin-bottom: .3rem; } | |
| .callout p { color: var(--text-dim); font-size: .92rem; } | |
| /* ── Formula ── */ | |
| .formula { | |
| font-family: 'JetBrains Mono', monospace; | |
| background: rgba(255,255,255,.04); | |
| border: 1px solid var(--border); | |
| border-radius: 12px; | |
| padding: 1.2rem 1.5rem; | |
| text-align: center; | |
| font-size: 1.05rem; | |
| color: var(--accent); | |
| margin: 1.5rem 0; | |
| overflow-x: auto; | |
| } | |
| /* ── Footer ── */ | |
| footer { | |
| position: relative; z-index: 1; | |
| text-align: center; | |
| padding: 3rem 2rem; | |
| color: var(--text-dim); | |
| font-size: .85rem; | |
| border-top: 1px solid var(--border); | |
| } | |
| footer a { color: var(--accent); text-decoration: none; } | |
| /* ── Responsive ── */ | |
| @media (max-width: 700px) { | |
| nav .links { display: none; } | |
| section { padding: 4rem 1rem 3rem; } | |
| .demo-controls { flex-direction: column; } | |
| .control-group input[type=range] { width: 100%; } | |
| } | |
| /* ── Animations ── */ | |
| .fade-up { | |
| opacity: 0; transform: translateY(30px); | |
| transition: opacity .7s ease, transform .7s ease; | |
| } | |
| .fade-up.visible { opacity: 1; transform: translateY(0); } | |
| </style> | |
| </head> | |
| <body> | |
| <canvas id="bg-canvas"></canvas> | |
| <nav> | |
| <div class="logo">MA-CMAB</div> | |
| <div class="links"> | |
| <a href="#problem">Problem</a> | |
| <a href="#how">How It Works</a> | |
| <a href="#demo">Demo</a> | |
| <a href="#algorithm">Algorithm</a> | |
| <a href="#results">Results</a> | |
| </div> | |
| </nav> | |
| <!-- ═══════════ HERO ═══════════ --> | |
| <section class="hero"> | |
| <div class="badge">📄 AAMAS 2026 • arXiv:2602.16183</div> | |
| <h1>Learning to Share Items Fairly — Without Knowing Their Value</h1> | |
| <p>How do you divide items among people to maximize everyone's total happiness, when you can only see the combined result and have to learn by trial and error?</p> | |
| <div class="cta"> | |
| <a href="#demo">Try the Demo ↓</a> | |
| <a href="#problem">Learn More</a> | |
| </div> | |
| <div class="scroll-hint">↓</div> | |
| </section> | |
| <!-- ═══════════ PROBLEM ═══════════ --> | |
| <section id="problem"> | |
| <div class="fade-up"> | |
| <div class="section-label">The Problem</div> | |
| <div class="section-title">Splitting Items to Make Everyone Happy</div> | |
| <div class="section-desc"> | |
| Imagine you're an auctioneer dividing items among bidders, a platform recommending content to user groups, or a manager assigning tasks to teams. Each recipient values bundles of items differently, and you want to maximize the total satisfaction — but you can only see the overall score, not individual happiness. | |
| </div> | |
| </div> | |
| <div class="cards fade-up"> | |
| <div class="card"> | |
| <div class="icon" style="background:rgba(99,102,241,.15);color:var(--accent);">🎁</div> | |
| <h3>Partition Problem</h3> | |
| <p>Divide N items among M agents so each item goes to exactly one agent — like splitting a pie, but the pieces are discrete objects.</p> | |
| </div> | |
| <div class="card"> | |
| <div class="icon" style="background:rgba(236,72,153,.15);color:var(--accent3);">📉</div> | |
| <h3>Diminishing Returns</h3> | |
| <p>Each agent's happiness follows "submodularity" — the more items you already have, the less each new item helps. Like getting a 5th pizza when you already have 4.</p> | |
| </div> | |
| <div class="card"> | |
| <div class="icon" style="background:rgba(245,158,11,.15);color:var(--orange);">🔒</div> | |
| <h3>Bandit Feedback</h3> | |
| <p>You only see the <strong>total score</strong> for the whole allocation, never individual agent utilities. Like grading a group project — you see one grade for everyone.</p> | |
| </div> | |
| <div class="card"> | |
| <div class="icon" style="background:rgba(16,185,129,.15);color:var(--green);">🤫</div> | |
| <h3>No Communication</h3> | |
| <p>Agents don't talk to each other. The system must figure out a good allocation by repeatedly trying different splits and observing aggregate outcomes.</p> | |
| </div> | |
| </div> | |
| <div class="callout fade-up"> | |
| <div class="callout-icon">💡</div> | |
| <div> | |
| <h4>Why is this hard?</h4> | |
| <p>The number of possible allocations grows <em>exponentially</em> — with 10 items and 3 agents, there are 3<sup>10</sup> = 59,049 possible splits. You can't try them all! And since you only see the total welfare score (not per-agent feedback), figuring out what each person values is like solving a puzzle blindfolded.</p> | |
| </div> | |
| </div> | |
| </section> | |
| <!-- ═══════════ HOW IT WORKS ═══════════ --> | |
| <section id="how"> | |
| <div class="fade-up"> | |
| <div class="section-label">Core Idea</div> | |
| <div class="section-title">Explore, Then Commit</div> | |
| <div class="section-desc"> | |
| The algorithm has two phases: first, strategically try different allocations to learn about agent preferences; then, lock in the best allocation found and exploit it for the remaining time. | |
| </div> | |
| </div> | |
| <div class="cards fade-up" style="grid-template-columns: 1fr 1fr;"> | |
| <div class="card" style="border-left: 3px solid var(--accent);"> | |
| <div class="icon" style="background:rgba(99,102,241,.15);color:var(--accent);">🔍</div> | |
| <h3>Phase 1: Exploration</h3> | |
| <p>Try different item assignments repeatedly. Average the total welfare scores to build accurate estimates of how good each allocation is. This takes ~T<sup>2/3</sup> rounds.</p> | |
| </div> | |
| <div class="card" style="border-left: 3px solid var(--green);"> | |
| <div class="icon" style="background:rgba(16,185,129,.15);color:var(--green);">🎯</div> | |
| <h3>Phase 2: Exploitation</h3> | |
| <p>Feed the estimates into a powerful offline algorithm (Continuous Greedy) that finds a near-optimal allocation. Then play that allocation for all remaining rounds.</p> | |
| </div> | |
| </div> | |
| <div class="callout fade-up"> | |
| <div class="callout-icon">⚖️</div> | |
| <div> | |
| <h4>The Explore–Exploit Tradeoff</h4> | |
| <p>Explore too little → bad allocation. Explore too much → wasted rounds. The paper shows the optimal balance gives <strong>Õ(T<sup>2/3</sup>)</strong> regret — meaning the per-round loss from not knowing the best allocation shrinks to zero as you play more rounds!</p> | |
| </div> | |
| </div> | |
| </section> | |
| <!-- ═══════════ INTERACTIVE DEMO ═══════════ --> | |
| <section id="demo"> | |
| <div class="fade-up"> | |
| <div class="section-label">Interactive Demo</div> | |
| <div class="section-title">Watch the Algorithm Allocate Items</div> | |
| <div class="section-desc"> | |
| Adjust the number of agents and items, then click "Run Allocation" to see how items get partitioned and the resulting welfare. | |
| </div> | |
| </div> | |
| <div class="demo-container fade-up"> | |
| <div class="demo-controls"> | |
| <div class="control-group"> | |
| <label>Agents (M)</label> | |
| <input type="range" id="agentSlider" min="2" max="6" value="3"> | |
| <div class="val" id="agentVal">3</div> | |
| </div> | |
| <div class="control-group"> | |
| <label>Items (N)</label> | |
| <input type="range" id="itemSlider" min="4" max="16" value="9"> | |
| <div class="val" id="itemVal">9</div> | |
| </div> | |
| <div class="control-group"> | |
| <label>Exploration Rounds</label> | |
| <input type="range" id="exploreSlider" min="5" max="50" value="20"> | |
| <div class="val" id="exploreVal">20</div> | |
| </div> | |
| <button class="btn-run" id="runBtn">▶ Run Allocation</button> | |
| </div> | |
| <div id="allocVisual" class="alloc-visual"></div> | |
| <div class="stats-row" id="statsRow" style="display:none;"> | |
| <div class="stat-box"> | |
| <div class="stat-val" id="statWelfare" style="color:var(--green);">—</div> | |
| <div class="stat-label">Total Welfare</div> | |
| </div> | |
| <div class="stat-box"> | |
| <div class="stat-val" id="statOpt" style="color:var(--accent);">—</div> | |
| <div class="stat-label">OPT Benchmark</div> | |
| </div> | |
| <div class="stat-box"> | |
| <div class="stat-val" id="statRatio" style="color:var(--orange);">—</div> | |
| <div class="stat-label">Approx Ratio</div> | |
| </div> | |
| <div class="stat-box"> | |
| <div class="stat-val" id="statExplore" style="color:var(--accent3);">—</div> | |
| <div class="stat-label">Rounds Explored</div> | |
| </div> | |
| </div> | |
| </div> | |
| <!-- Regret Curve --> | |
| <div class="chart-container fade-up" style="margin-top:2rem;"> | |
| <h3 style="margin-bottom:.5rem;">📈 Regret Over Time</h3> | |
| <p style="color:var(--text-dim);font-size:.88rem;margin-bottom:1rem;">The cumulative gap between the ideal allocation and the algorithm's choices. Notice it grows sub-linearly — the algorithm learns!</p> | |
| <canvas id="regretCanvas"></canvas> | |
| <div style="display:flex; gap:1.5rem; margin-top:1rem; flex-wrap:wrap;"> | |
| <div style="display:flex;align-items:center;gap:.4rem;font-size:.8rem;"><span style="width:12px;height:12px;background:var(--accent);border-radius:3px;display:inline-block;"></span> MA-CMAB Regret ~ T<sup>2/3</sup></div> | |
| <div style="display:flex;align-items:center;gap:.4rem;font-size:.8rem;color:var(--text-dim);"><span style="width:12px;height:12px;background:rgba(245,158,11,.7);border-radius:3px;display:inline-block;"></span> Linear Regret (no learning)</div> | |
| </div> | |
| </div> | |
| </section> | |
| <!-- ═══════════ ALGORITHM DETAILS ═══════════ --> | |
| <section id="algorithm"> | |
| <div class="fade-up"> | |
| <div class="section-label">Under the Hood</div> | |
| <div class="section-title">The MA-CMAB Algorithm Step by Step</div> | |
| <div class="section-desc"> | |
| The algorithm combines a classical offline optimization technique (Continuous Greedy) with an online learning strategy (Explore-then-Commit). | |
| </div> | |
| </div> | |
| <div class="timeline fade-up"> | |
| <div class="timeline-item"> | |
| <div class="step-num">STEP 01</div> | |
| <h3>Set Exploration Budget</h3> | |
| <p>Calculate the optimal number of exploration rounds <strong>m</strong> based on the time horizon T, number of agents, items, and resilience parameters. The formula balances exploration cost against estimation accuracy.</p> | |
| </div> | |
| <div class="timeline-item"> | |
| <div class="step-num">STEP 02</div> | |
| <h3>Explore: Try Allocations</h3> | |
| <p>The offline Continuous Greedy algorithm requests evaluations of specific allocations. For each one, play that allocation <strong>m</strong> times and average the observed total welfare to build a reliable estimate.</p> | |
| </div> | |
| <div class="timeline-item"> | |
| <div class="step-num">STEP 03</div> | |
| <h3>Handle Noise with Resilience</h3> | |
| <p>Even though estimates are noisy (based on random samples), the Continuous Greedy algorithm is <strong>resilient</strong> — it still finds a (1−1/e)-approximate solution as long as errors are bounded. The paper proves this key robustness property.</p> | |
| </div> | |
| <div class="timeline-item"> | |
| <div class="step-num">STEP 04</div> | |
| <h3>Round to Get a Real Allocation</h3> | |
| <p>Continuous Greedy produces a fractional solution (probabilities). <strong>Pipage rounding</strong> converts this to an actual item partition without losing quality — a powerful mathematical trick.</p> | |
| </div> | |
| <div class="timeline-item"> | |
| <div class="step-num">STEP 05</div> | |
| <h3>Exploit: Lock In and Collect</h3> | |
| <p>For all remaining T − (exploration rounds), play the computed allocation. Since it's near-optimal, the per-round regret is tiny, and total regret grows as Õ(T<sup>2/3</sup>).</p> | |
| </div> | |
| </div> | |
| <div class="formula fade-up"> | |
| Regret ≤ O( δ<sup>2/3</sup> · η<sup>1/3</sup> · M<sup>2/3</sup> · T<sup>2/3</sup> · log(T)<sup>1/3</sup> ) | |
| </div> | |
| <p class="fade-up" style="text-align:center;color:var(--text-dim);font-size:.9rem;margin-top:-.5rem;"> | |
| Where δ captures noise sensitivity, η is oracle complexity, M is the number of agents, and T is the time horizon. | |
| </p> | |
| </section> | |
| <!-- ═══════════ RESULTS / COMPARISON ═══════════ --> | |
| <section id="results"> | |
| <div class="fade-up"> | |
| <div class="section-label">Key Results</div> | |
| <div class="section-title">How This Work Compares</div> | |
| <div class="section-desc"> | |
| This paper is the first to achieve sublinear regret for the multi-agent submodular welfare problem with only bandit feedback. | |
| </div> | |
| </div> | |
| <div style="overflow-x:auto;" class="fade-up"> | |
| <table class="comparison-table"> | |
| <thead> | |
| <tr> | |
| <th>Feature</th> | |
| <th>Prior Single-Agent</th> | |
| <th>Prior Multi-Agent</th> | |
| <th>This Paper (MA-CMAB)</th> | |
| </tr> | |
| </thead> | |
| <tbody> | |
| <tr> | |
| <td>Agents</td> | |
| <td>1</td> | |
| <td>M ≥ 1 (communicating)</td> | |
| <td><span class="tag tag-green">M ≥ 1 (non-communicating)</span></td> | |
| </tr> | |
| <tr> | |
| <td>Action Space</td> | |
| <td>Single subset</td> | |
| <td>Shared subset</td> | |
| <td><span class="tag tag-purple">Disjoint partitions</span></td> | |
| </tr> | |
| <tr> | |
| <td>Feedback</td> | |
| <td>Semi-bandit or bandit</td> | |
| <td>Shared observations</td> | |
| <td><span class="tag tag-orange">Full-bandit only</span></td> | |
| </tr> | |
| <tr> | |
| <td>Objective</td> | |
| <td>Single agent utility</td> | |
| <td>Sum (separable)</td> | |
| <td><span class="tag tag-green">Total welfare (coupled)</span></td> | |
| </tr> | |
| <tr> | |
| <td>Approx. Ratio</td> | |
| <td>1 − 1/e ≈ 0.632</td> | |
| <td>1 − 1/e</td> | |
| <td><span class="tag tag-green">1 − 1/e ≈ 0.632</span></td> | |
| </tr> | |
| <tr> | |
| <td>Regret</td> | |
| <td>Õ(T<sup>2/3</sup>)</td> | |
| <td>Depends on setting</td> | |
| <td><span class="tag tag-green">Õ(T<sup>2/3</sup>)</span></td> | |
| </tr> | |
| </tbody> | |
| </table> | |
| </div> | |
| <div class="cards fade-up" style="margin-top:3rem;"> | |
| <div class="card" style="border-top:3px solid var(--accent);"> | |
| <h3>🏆 1 − 1/e ≈ 63.2%</h3> | |
| <p>The algorithm achieves the best possible approximation ratio for this type of problem. You can't do better (it's NP-hard!).</p> | |
| </div> | |
| <div class="card" style="border-top:3px solid var(--green);"> | |
| <h3>📉 Sublinear Regret</h3> | |
| <p>Regret grows as T<sup>2/3</sup> — much slower than T. On average, per-round loss → 0, meaning the algorithm effectively learns the optimal allocation.</p> | |
| </div> | |
| <div class="card" style="border-top:3px solid var(--accent3);"> | |
| <h3>🔧 Noise-Resilient</h3> | |
| <p>Even with noisy observations, the offline Continuous Greedy still works — a key theoretical contribution enabling the online guarantee.</p> | |
| </div> | |
| </div> | |
| </section> | |
| <!-- ═══════════ APPLICATIONS ═══════════ --> | |
| <section id="applications"> | |
| <div class="fade-up"> | |
| <div class="section-label">Real-World Applications</div> | |
| <div class="section-title">Where Could This Be Used?</div> | |
| </div> | |
| <div class="cards fade-up"> | |
| <div class="card"> | |
| <div class="icon" style="background:rgba(99,102,241,.15);color:var(--accent);">🛒</div> | |
| <h3>Online Auctions</h3> | |
| <p>Allocate items to bidders to maximize total value when bids are noisy or private — learning optimal allocations over repeated auction rounds.</p> | |
| </div> | |
| <div class="card"> | |
| <div class="icon" style="background:rgba(236,72,153,.15);color:var(--accent3);">📺</div> | |
| <h3>Content Recommendation</h3> | |
| <p>Partition a pool of content items across user segments to maximize total engagement, where only aggregate metrics are observable.</p> | |
| </div> | |
| <div class="card"> | |
| <div class="icon" style="background:rgba(16,185,129,.15);color:var(--green);">📡</div> | |
| <h3>Sensor / Resource Allocation</h3> | |
| <p>Distribute sensors or resources across regions with diminishing returns, learning from aggregate coverage scores.</p> | |
| </div> | |
| <div class="card"> | |
| <div class="icon" style="background:rgba(245,158,11,.15);color:var(--orange);">⚖️</div> | |
| <h3>Fair Division</h3> | |
| <p>Equitably divide indivisible goods among people where preferences are unknown and must be learned from group satisfaction surveys.</p> | |
| </div> | |
| </div> | |
| </section> | |
| <footer> | |
| <p>Interactive explainer for <a href="https://arxiv.org/abs/2602.16183" target="_blank">arXiv:2602.16183</a> — Pokhriyal, Jain & Aggarwal (2026)</p> | |
| <p style="margin-top:.3rem;">Built for educational purposes. Not affiliated with the authors.</p> | |
| </footer> | |
| <script> | |
| // ═══════════ Background Particle Canvas ═══════════ | |
| (() => { | |
| const c = document.getElementById('bg-canvas'); | |
| const ctx = c.getContext('2d'); | |
| let w, h, particles = []; | |
| function resize() { | |
| w = c.width = window.innerWidth; | |
| h = c.height = window.innerHeight; | |
| } | |
| window.addEventListener('resize', resize); | |
| resize(); | |
| for (let i = 0; i < 80; i++) { | |
| particles.push({ | |
| x: Math.random() * w, y: Math.random() * h, | |
| vx: (Math.random() - .5) * .3, vy: (Math.random() - .5) * .3, | |
| r: Math.random() * 2 + .5, | |
| color: ['rgba(99,102,241,.3)','rgba(139,92,246,.25)','rgba(236,72,153,.2)'][Math.floor(Math.random()*3)] | |
| }); | |
| } | |
| function draw() { | |
| ctx.clearRect(0,0,w,h); | |
| for (const p of particles) { | |
| p.x += p.vx; p.y += p.vy; | |
| if (p.x < 0) p.x = w; if (p.x > w) p.x = 0; | |
| if (p.y < 0) p.y = h; if (p.y > h) p.y = 0; | |
| ctx.beginPath(); | |
| ctx.arc(p.x, p.y, p.r, 0, Math.PI*2); | |
| ctx.fillStyle = p.color; | |
| ctx.fill(); | |
| } | |
| // draw connections | |
| for (let i = 0; i < particles.length; i++) { | |
| for (let j = i+1; j < particles.length; j++) { | |
| const dx = particles[i].x - particles[j].x; | |
| const dy = particles[i].y - particles[j].y; | |
| const d = Math.sqrt(dx*dx + dy*dy); | |
| if (d < 120) { | |
| ctx.beginPath(); | |
| ctx.moveTo(particles[i].x, particles[i].y); | |
| ctx.lineTo(particles[j].x, particles[j].y); | |
| ctx.strokeStyle = `rgba(99,102,241,${.08*(1-d/120)})`; | |
| ctx.lineWidth = .5; | |
| ctx.stroke(); | |
| } | |
| } | |
| } | |
| requestAnimationFrame(draw); | |
| } | |
| draw(); | |
| })(); | |
| // ═══════════ Scroll Reveal ═══════════ | |
| const observer = new IntersectionObserver((entries) => { | |
| entries.forEach(e => { if (e.isIntersecting) e.target.classList.add('visible'); }); | |
| }, { threshold: .1 }); | |
| document.querySelectorAll('.fade-up').forEach(el => observer.observe(el)); | |
| // ═══════════ Sliders ═══════════ | |
| const agentSlider = document.getElementById('agentSlider'); | |
| const itemSlider = document.getElementById('itemSlider'); | |
| const exploreSlider = document.getElementById('exploreSlider'); | |
| const agentVal = document.getElementById('agentVal'); | |
| const itemVal = document.getElementById('itemVal'); | |
| const exploreVal = document.getElementById('exploreVal'); | |
| agentSlider.oninput = () => agentVal.textContent = agentSlider.value; | |
| itemSlider.oninput = () => itemVal.textContent = itemSlider.value; | |
| exploreSlider.oninput = () => exploreVal.textContent = exploreSlider.value; | |
| // ═══════════ Submodular Utility (coverage-style) ═══════════ | |
| function submodularValue(items, agentId, N) { | |
| // Each agent has a "coverage" style utility: | |
| // item j covers a random subset of "elements" seeded by (agentId, j) | |
| // utility = fraction of elements covered | |
| const numElements = 20; | |
| const covered = new Set(); | |
| for (const j of items) { | |
| const seed = agentId * 1000 + j; | |
| // deterministic pseudo-random elements covered | |
| for (let k = 0; k < 6; k++) { | |
| covered.add((seed * 31 + k * 17) % numElements); | |
| } | |
| } | |
| return covered.size / numElements; | |
| } | |
| // ═══════════ Run Allocation ═══════════ | |
| const ITEM_COLORS = [ | |
| '#6366f1','#8b5cf6','#a855f7','#ec4899','#f43f5e', | |
| '#f59e0b','#10b981','#06b6d4','#3b82f6','#14b8a6', | |
| '#e879f9','#fb923c','#34d399','#60a5fa','#f472b6','#fbbf24' | |
| ]; | |
| const AGENT_COLORS = ['#6366f1','#ec4899','#10b981','#f59e0b','#06b6d4','#a855f7']; | |
| document.getElementById('runBtn').addEventListener('click', () => { | |
| const M = parseInt(agentSlider.value); | |
| const N = parseInt(itemSlider.value); | |
| const exploreRounds = parseInt(exploreSlider.value); | |
| // Try several random allocations (exploration) then pick the best | |
| let bestAllocation = null; | |
| let bestWelfare = -Infinity; | |
| let optWelfare = -Infinity; | |
| // Brute-ish exploration: try random partitions | |
| for (let trial = 0; trial < exploreRounds * 5; trial++) { | |
| const alloc = new Array(M).fill(null).map(() => []); | |
| for (let j = 0; j < N; j++) { | |
| const agent = Math.floor(Math.random() * M); | |
| alloc[agent].push(j); | |
| } | |
| let welfare = 0; | |
| for (let i = 0; i < M; i++) { | |
| welfare += submodularValue(alloc[i], i, N); | |
| } | |
| // Add noise to simulate bandit feedback | |
| const noisyWelfare = welfare + (Math.random() - .5) * 0.1; | |
| if (noisyWelfare > bestWelfare) { | |
| bestWelfare = noisyWelfare; | |
| bestAllocation = alloc; | |
| } | |
| if (welfare > optWelfare) optWelfare = welfare; | |
| } | |
| // Also compute a greedy allocation as approximate OPT | |
| const greedyAlloc = new Array(M).fill(null).map(() => []); | |
| const unassigned = Array.from({length: N}, (_, i) => i); | |
| // Greedy: assign each item to the agent with highest marginal gain | |
| for (const j of unassigned) { | |
| let bestAgent = 0, bestGain = -1; | |
| for (let i = 0; i < M; i++) { | |
| const gain = submodularValue([...greedyAlloc[i], j], i, N) - submodularValue(greedyAlloc[i], i, N); | |
| if (gain > bestGain) { bestGain = gain; bestAgent = i; } | |
| } | |
| greedyAlloc[bestAgent].push(j); | |
| } | |
| let greedyWelfare = 0; | |
| for (let i = 0; i < M; i++) greedyWelfare += submodularValue(greedyAlloc[i], i, N); | |
| // Use the better of greedy vs explored | |
| let finalAlloc, finalWelfare; | |
| let trueWelfare = 0; | |
| for (let i = 0; i < M; i++) trueWelfare += submodularValue(bestAllocation[i], i, N); | |
| if (greedyWelfare > trueWelfare) { | |
| finalAlloc = greedyAlloc; | |
| finalWelfare = greedyWelfare; | |
| } else { | |
| finalAlloc = bestAllocation; | |
| finalWelfare = trueWelfare; | |
| } | |
| const approxOPT = Math.max(greedyWelfare, optWelfare); | |
| // Render allocation | |
| const container = document.getElementById('allocVisual'); | |
| container.innerHTML = ''; | |
| for (let i = 0; i < M; i++) { | |
| const box = document.createElement('div'); | |
| box.className = 'agent-box'; | |
| box.innerHTML = ` | |
| <div class="agent-label" style="color:${AGENT_COLORS[i]}">Agent ${i+1}</div> | |
| <div style="font-size:.75rem;color:var(--text-dim);margin-bottom:.5rem;"> | |
| Value: ${submodularValue(finalAlloc[i], i, N).toFixed(3)} | |
| </div> | |
| <div class="item-grid" id="agent-grid-${i}"></div> | |
| `; | |
| container.appendChild(box); | |
| // Animate items | |
| setTimeout(() => { | |
| const grid = document.getElementById(`agent-grid-${i}`); | |
| finalAlloc[i].forEach((j, idx) => { | |
| const chip = document.createElement('div'); | |
| chip.className = 'item-chip'; | |
| chip.textContent = j + 1; | |
| chip.style.background = ITEM_COLORS[j % ITEM_COLORS.length]; | |
| chip.style.color = '#fff'; | |
| grid.appendChild(chip); | |
| setTimeout(() => chip.classList.add('show'), idx * 60 + i * 100); | |
| }); | |
| if (finalAlloc[i].length === 0) { | |
| grid.innerHTML = '<span style="font-size:.75rem;color:var(--text-dim);">—</span>'; | |
| } | |
| setTimeout(() => box.classList.add('highlight'), 200 + i * 100); | |
| }, 100); | |
| } | |
| // Show stats | |
| const statsRow = document.getElementById('statsRow'); | |
| statsRow.style.display = 'flex'; | |
| document.getElementById('statWelfare').textContent = finalWelfare.toFixed(3); | |
| document.getElementById('statOpt').textContent = approxOPT.toFixed(3); | |
| document.getElementById('statRatio').textContent = (finalWelfare / approxOPT * 100).toFixed(1) + '%'; | |
| document.getElementById('statExplore').textContent = exploreRounds; | |
| // Draw regret chart | |
| drawRegretChart(exploreRounds); | |
| }); | |
| // ═══════════ Regret Chart ═══════════ | |
| function drawRegretChart(exploreRounds) { | |
| const canvas = document.getElementById('regretCanvas'); | |
| const ctx = canvas.getContext('2d'); | |
| const dpr = window.devicePixelRatio || 1; | |
| const rect = canvas.getBoundingClientRect(); | |
| canvas.width = rect.width * dpr; | |
| canvas.height = rect.height * dpr; | |
| ctx.scale(dpr, dpr); | |
| const W = rect.width, H = rect.height; | |
| ctx.clearRect(0, 0, W, H); | |
| const T = 1000; | |
| const pad = { top: 20, right: 20, bottom: 40, left: 60 }; | |
| const plotW = W - pad.left - pad.right; | |
| const plotH = H - pad.top - pad.bottom; | |
| // Grid | |
| ctx.strokeStyle = 'rgba(255,255,255,.05)'; | |
| ctx.lineWidth = 1; | |
| for (let i = 0; i <= 5; i++) { | |
| const y = pad.top + (plotH / 5) * i; | |
| ctx.beginPath(); ctx.moveTo(pad.left, y); ctx.lineTo(W - pad.right, y); ctx.stroke(); | |
| } | |
| // Axes labels | |
| ctx.fillStyle = '#94a3b8'; | |
| ctx.font = '11px Inter'; | |
| ctx.textAlign = 'center'; | |
| ctx.fillText('Round (t)', W/2, H - 5); | |
| ctx.save(); | |
| ctx.translate(14, H/2); | |
| ctx.rotate(-Math.PI/2); | |
| ctx.fillText('Cumulative Regret', 0, 0); | |
| ctx.restore(); | |
| // Compute curves | |
| const linearMax = T; | |
| const sublinearMax = Math.pow(T, 2/3) * 3; | |
| const maxY = linearMax; | |
| function toX(t) { return pad.left + (t / T) * plotW; } | |
| function toY(v) { return pad.top + plotH - (v / maxY) * plotH; } | |
| // Linear regret (no learning) | |
| ctx.beginPath(); | |
| ctx.strokeStyle = 'rgba(245,158,11,.5)'; | |
| ctx.lineWidth = 2; | |
| ctx.setLineDash([6, 4]); | |
| for (let t = 0; t <= T; t += 5) { | |
| const r = t * 0.8; // slope < 1 | |
| t === 0 ? ctx.moveTo(toX(t), toY(r)) : ctx.lineTo(toX(t), toY(r)); | |
| } | |
| ctx.stroke(); | |
| ctx.setLineDash([]); | |
| // MA-CMAB regret ~ T^(2/3) with exploration bump | |
| ctx.beginPath(); | |
| const grad = ctx.createLinearGradient(pad.left, 0, W - pad.right, 0); | |
| grad.addColorStop(0, '#6366f1'); | |
| grad.addColorStop(1, '#ec4899'); | |
| ctx.strokeStyle = grad; | |
| ctx.lineWidth = 3; | |
| const exploreEnd = Math.floor(T * (exploreRounds / 50) * 0.3); | |
| for (let t = 0; t <= T; t += 2) { | |
| let r; | |
| if (t <= exploreEnd) { | |
| // Exploration: regret grows linearly | |
| r = t * 0.6; | |
| } else { | |
| // Exploitation: regret grows slowly (T^2/3 shape) | |
| const base = exploreEnd * 0.6; | |
| const remaining = t - exploreEnd; | |
| const totalRemaining = T - exploreEnd; | |
| r = base + (sublinearMax - base) * Math.pow(remaining / totalRemaining, 0.5); | |
| } | |
| t === 0 ? ctx.moveTo(toX(t), toY(r)) : ctx.lineTo(toX(t), toY(r)); | |
| } | |
| ctx.stroke(); | |
| // Exploration region | |
| ctx.fillStyle = 'rgba(99,102,241,.06)'; | |
| ctx.fillRect(pad.left, pad.top, (exploreEnd / T) * plotW, plotH); | |
| ctx.fillStyle = 'rgba(99,102,241,.6)'; | |
| ctx.font = 'bold 10px Inter'; | |
| ctx.textAlign = 'center'; | |
| ctx.fillText('EXPLORE', pad.left + (exploreEnd / T) * plotW / 2, pad.top + 15); | |
| ctx.fillStyle = 'rgba(16,185,129,.5)'; | |
| ctx.fillText('EXPLOIT', pad.left + (exploreEnd / T) * plotW + (1 - exploreEnd / T) * plotW / 2, pad.top + 15); | |
| // Dividing line | |
| ctx.beginPath(); | |
| ctx.strokeStyle = 'rgba(255,255,255,.15)'; | |
| ctx.setLineDash([4,4]); | |
| const divX = toX(exploreEnd); | |
| ctx.moveTo(divX, pad.top); | |
| ctx.lineTo(divX, pad.top + plotH); | |
| ctx.stroke(); | |
| ctx.setLineDash([]); | |
| // Axis ticks | |
| ctx.fillStyle = '#64748b'; | |
| ctx.font = '10px JetBrains Mono'; | |
| ctx.textAlign = 'center'; | |
| for (let t = 0; t <= T; t += 200) { | |
| ctx.fillText(t, toX(t), H - pad.bottom + 18); | |
| } | |
| ctx.textAlign = 'right'; | |
| for (let i = 0; i <= 5; i++) { | |
| const v = (maxY / 5) * i; | |
| ctx.fillText(Math.round(v), pad.left - 8, toY(v) + 4); | |
| } | |
| } | |
| // Initial chart draw | |
| setTimeout(() => drawRegretChart(20), 500); | |
| window.addEventListener('resize', () => drawRegretChart(parseInt(exploreSlider.value))); | |
| </script> | |
| </body> | |
| </html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment