Created
February 23, 2026 00:10
-
-
Save jbdamask/317b32036eab1280febc08495b20668c 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 Resource 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;500&display=swap'); | |
| * { margin: 0; padding: 0; box-sizing: border-box; } | |
| :root { | |
| --bg: #0a0a0f; | |
| --surface: #12121a; | |
| --surface2: #1a1a2e; | |
| --accent: #6c63ff; | |
| --accent2: #ff6584; | |
| --accent3: #43e97b; | |
| --accent4: #38f9d7; | |
| --text: #e8e8f0; | |
| --text-dim: #8888a0; | |
| --border: #2a2a3e; | |
| } | |
| html { scroll-behavior: smooth; } | |
| body { | |
| font-family: 'Inter', sans-serif; | |
| background: var(--bg); | |
| color: var(--text); | |
| overflow-x: hidden; | |
| line-height: 1.6; | |
| } | |
| /* Scrollbar */ | |
| ::-webkit-scrollbar { width: 6px; } | |
| ::-webkit-scrollbar-track { background: var(--bg); } | |
| ::-webkit-scrollbar-thumb { background: var(--accent); border-radius: 3px; } | |
| /* Canvas backgrounds */ | |
| #hero-canvas, #particles-canvas { | |
| position: absolute; | |
| top: 0; left: 0; | |
| width: 100%; height: 100%; | |
| pointer-events: none; | |
| } | |
| /* NAV */ | |
| nav { | |
| position: fixed; top: 0; left: 0; right: 0; z-index: 1000; | |
| backdrop-filter: blur(20px); | |
| background: rgba(10,10,15,0.8); | |
| border-bottom: 1px solid var(--border); | |
| padding: 0 2rem; | |
| transition: transform 0.3s; | |
| } | |
| nav .nav-inner { | |
| max-width: 1200px; margin: 0 auto; | |
| display: flex; align-items: center; justify-content: space-between; | |
| height: 64px; | |
| } | |
| nav .logo { | |
| font-weight: 800; font-size: 1.1rem; | |
| background: linear-gradient(135deg, var(--accent), var(--accent2)); | |
| -webkit-background-clip: text; -webkit-text-fill-color: transparent; | |
| } | |
| nav .nav-links { display: flex; gap: 2rem; list-style: none; } | |
| nav .nav-links a { | |
| color: var(--text-dim); text-decoration: none; font-size: 0.85rem; | |
| font-weight: 500; transition: color 0.3s; position: relative; | |
| } | |
| nav .nav-links a:hover { color: var(--text); } | |
| nav .nav-links a::after { | |
| content: ''; position: absolute; bottom: -4px; left: 0; | |
| width: 0; height: 2px; | |
| background: var(--accent); transition: width 0.3s; | |
| } | |
| nav .nav-links a:hover::after { width: 100%; } | |
| .hamburger { display: none; flex-direction: column; gap: 5px; cursor: pointer; background: none; border: none; } | |
| .hamburger span { display: block; width: 24px; height: 2px; background: var(--text); transition: 0.3s; } | |
| /* HERO */ | |
| .hero { | |
| position: relative; min-height: 100vh; | |
| display: flex; align-items: center; justify-content: center; | |
| text-align: center; padding: 6rem 2rem 4rem; | |
| overflow: hidden; | |
| } | |
| .hero-bg { | |
| position: absolute; inset: 0; | |
| background: radial-gradient(ellipse at 30% 20%, rgba(108,99,255,0.15) 0%, transparent 50%), | |
| radial-gradient(ellipse at 70% 80%, rgba(255,101,132,0.1) 0%, transparent 50%); | |
| } | |
| .hero-content { position: relative; z-index: 2; max-width: 900px; } | |
| .hero-badge { | |
| display: inline-block; padding: 0.4rem 1rem; border-radius: 50px; | |
| font-size: 0.75rem; font-weight: 600; text-transform: uppercase; letter-spacing: 2px; | |
| background: rgba(108,99,255,0.15); color: var(--accent); border: 1px solid rgba(108,99,255,0.3); | |
| margin-bottom: 1.5rem; | |
| } | |
| .hero h1 { | |
| font-size: clamp(2.5rem, 6vw, 4.5rem); font-weight: 900; | |
| line-height: 1.1; margin-bottom: 1.5rem; | |
| } | |
| .hero h1 .gradient-text { | |
| background: linear-gradient(135deg, var(--accent), var(--accent4), var(--accent3)); | |
| -webkit-background-clip: text; -webkit-text-fill-color: transparent; | |
| } | |
| .hero p { | |
| font-size: 1.15rem; color: var(--text-dim); max-width: 650px; | |
| margin: 0 auto 2.5rem; line-height: 1.7; | |
| } | |
| .hero-cta { | |
| display: inline-flex; align-items: center; gap: 0.5rem; | |
| padding: 0.9rem 2rem; border-radius: 12px; font-weight: 600; | |
| font-size: 0.95rem; text-decoration: none; color: #fff; | |
| background: linear-gradient(135deg, var(--accent), #8b5cf6); | |
| box-shadow: 0 4px 30px rgba(108,99,255,0.4); | |
| transition: transform 0.3s, box-shadow 0.3s; | |
| } | |
| .hero-cta:hover { transform: translateY(-2px); box-shadow: 0 8px 40px rgba(108,99,255,0.5); } | |
| .hero-stats { | |
| display: flex; justify-content: center; gap: 3rem; margin-top: 3rem; | |
| flex-wrap: wrap; | |
| } | |
| .hero-stat { text-align: center; } | |
| .hero-stat .num { | |
| font-size: 2rem; font-weight: 800; | |
| background: linear-gradient(135deg, var(--accent3), var(--accent4)); | |
| -webkit-background-clip: text; -webkit-text-fill-color: transparent; | |
| } | |
| .hero-stat .label { font-size: 0.75rem; color: var(--text-dim); text-transform: uppercase; letter-spacing: 1px; } | |
| /* SECTIONS */ | |
| section { padding: 6rem 2rem; position: relative; } | |
| .section-inner { max-width: 1100px; margin: 0 auto; } | |
| .section-label { | |
| font-size: 0.7rem; font-weight: 700; text-transform: uppercase; | |
| letter-spacing: 3px; color: var(--accent); margin-bottom: 0.75rem; | |
| } | |
| .section-title { | |
| font-size: clamp(1.8rem, 4vw, 2.8rem); font-weight: 800; | |
| margin-bottom: 1rem; line-height: 1.2; | |
| } | |
| .section-desc { | |
| font-size: 1.05rem; color: var(--text-dim); max-width: 700px; | |
| margin-bottom: 3rem; line-height: 1.7; | |
| } | |
| /* CARDS */ | |
| .card-grid { | |
| display: grid; gap: 1.5rem; | |
| grid-template-columns: repeat(auto-fit, minmax(300px, 1fr)); | |
| } | |
| .card { | |
| background: var(--surface); | |
| border: 1px solid var(--border); | |
| border-radius: 16px; padding: 2rem; | |
| transition: transform 0.3s, border-color 0.3s, box-shadow 0.3s; | |
| position: relative; overflow: hidden; | |
| } | |
| .card:hover { | |
| transform: translateY(-4px); | |
| border-color: var(--accent); | |
| box-shadow: 0 8px 40px rgba(108,99,255,0.15); | |
| } | |
| .card-icon { | |
| width: 48px; height: 48px; border-radius: 12px; | |
| display: flex; align-items: center; justify-content: center; | |
| font-size: 1.5rem; margin-bottom: 1.2rem; | |
| } | |
| .card h3 { font-size: 1.15rem; font-weight: 700; margin-bottom: 0.6rem; } | |
| .card p { font-size: 0.9rem; color: var(--text-dim); line-height: 1.6; } | |
| /* Interactive demo area */ | |
| .demo-container { | |
| background: var(--surface); | |
| border: 1px solid var(--border); | |
| border-radius: 20px; padding: 2.5rem; | |
| margin-top: 2rem; | |
| } | |
| .demo-header { display: flex; justify-content: space-between; align-items: center; flex-wrap: wrap; gap: 1rem; margin-bottom: 2rem; } | |
| .demo-header h3 { font-size: 1.2rem; font-weight: 700; } | |
| .btn { | |
| padding: 0.6rem 1.5rem; border-radius: 10px; font-weight: 600; | |
| font-size: 0.85rem; border: none; cursor: pointer; transition: all 0.3s; | |
| font-family: 'Inter', sans-serif; | |
| } | |
| .btn-primary { background: var(--accent); color: #fff; } | |
| .btn-primary:hover { background: #7c73ff; transform: translateY(-1px); } | |
| .btn-outline { background: transparent; color: var(--accent); border: 1px solid var(--accent); } | |
| .btn-outline:hover { background: rgba(108,99,255,0.1); } | |
| /* Allocation Viz */ | |
| #alloc-viz { | |
| display: grid; grid-template-columns: repeat(auto-fit, minmax(200px, 1fr)); | |
| gap: 1.5rem; margin-bottom: 2rem; | |
| } | |
| .agent-box { | |
| background: var(--surface2); border-radius: 14px; padding: 1.5rem; | |
| border: 1px solid var(--border); min-height: 150px; | |
| transition: border-color 0.5s, box-shadow 0.5s; | |
| } | |
| .agent-box.highlight { border-color: var(--accent3); box-shadow: 0 0 20px rgba(67,233,123,0.15); } | |
| .agent-label { | |
| font-size: 0.75rem; font-weight: 700; text-transform: uppercase; | |
| letter-spacing: 1px; margin-bottom: 0.8rem; display: flex; | |
| align-items: center; gap: 0.5rem; | |
| } | |
| .agent-dot { width: 8px; height: 8px; border-radius: 50%; } | |
| .agent-items { display: flex; flex-wrap: wrap; gap: 0.5rem; margin-top: 0.5rem; } | |
| .item-chip { | |
| display: inline-flex; align-items: center; gap: 0.3rem; | |
| padding: 0.35rem 0.75rem; border-radius: 8px; | |
| font-size: 0.75rem; font-weight: 600; | |
| background: rgba(108,99,255,0.12); color: var(--accent); | |
| border: 1px solid rgba(108,99,255,0.2); | |
| animation: chipIn 0.4s ease; | |
| } | |
| @keyframes chipIn { | |
| from { opacity: 0; transform: scale(0.7); } | |
| to { opacity: 1; transform: scale(1); } | |
| } | |
| .welfare-bar-container { margin-top: 1rem; } | |
| .welfare-bar-label { font-size: 0.8rem; color: var(--text-dim); margin-bottom: 0.3rem; } | |
| .welfare-bar-track { | |
| height: 8px; background: var(--surface2); border-radius: 4px; overflow: hidden; | |
| } | |
| .welfare-bar-fill { | |
| height: 100%; border-radius: 4px; transition: width 0.8s ease; | |
| background: linear-gradient(90deg, var(--accent), var(--accent3)); | |
| } | |
| .welfare-value { | |
| font-size: 1.5rem; font-weight: 800; margin-top: 0.5rem; | |
| background: linear-gradient(135deg, var(--accent3), var(--accent4)); | |
| -webkit-background-clip: text; -webkit-text-fill-color: transparent; | |
| } | |
| /* Regret Chart */ | |
| #regret-canvas { | |
| width: 100%; height: 300px; display: block; | |
| background: var(--surface2); border-radius: 14px; | |
| } | |
| /* Algorithm steps */ | |
| .algo-timeline { | |
| position: relative; padding-left: 3rem; | |
| } | |
| .algo-timeline::before { | |
| content: ''; position: absolute; left: 14px; top: 0; bottom: 0; | |
| width: 2px; background: var(--border); | |
| } | |
| .algo-step { | |
| position: relative; margin-bottom: 2.5rem; opacity: 0.5; | |
| transition: opacity 0.5s; | |
| } | |
| .algo-step.active { opacity: 1; } | |
| .algo-step::before { | |
| content: ''; position: absolute; left: -2.35rem; top: 4px; | |
| width: 12px; height: 12px; border-radius: 50%; | |
| background: var(--border); border: 2px solid var(--surface); | |
| transition: background 0.5s; | |
| } | |
| .algo-step.active::before { background: var(--accent); box-shadow: 0 0 12px rgba(108,99,255,0.5); } | |
| .algo-step h4 { font-size: 1rem; font-weight: 700; margin-bottom: 0.3rem; } | |
| .algo-step p { font-size: 0.85rem; color: var(--text-dim); } | |
| /* Equation box */ | |
| .eq-box { | |
| display: inline-block; padding: 1rem 1.5rem; border-radius: 12px; | |
| background: var(--surface2); border: 1px solid var(--border); | |
| font-family: 'JetBrains Mono', monospace; font-size: 0.95rem; | |
| color: var(--accent4); margin: 1rem 0; | |
| } | |
| /* Comparison Table */ | |
| .comparison-table { | |
| width: 100%; border-collapse: collapse; margin-top: 2rem; | |
| background: var(--surface); border-radius: 14px; overflow: hidden; | |
| border: 1px solid var(--border); | |
| } | |
| .comparison-table th, .comparison-table td { | |
| padding: 1rem 1.5rem; text-align: left; font-size: 0.85rem; | |
| border-bottom: 1px solid var(--border); | |
| } | |
| .comparison-table th { | |
| background: var(--surface2); font-weight: 700; font-size: 0.75rem; | |
| text-transform: uppercase; letter-spacing: 1px; color: var(--text-dim); | |
| } | |
| .comparison-table tr:last-child td { border-bottom: none; } | |
| .comparison-table .highlight-row { background: rgba(108,99,255,0.08); } | |
| .tag { | |
| display: inline-block; padding: 0.2rem 0.6rem; border-radius: 6px; | |
| font-size: 0.7rem; font-weight: 600; | |
| } | |
| .tag-green { background: rgba(67,233,123,0.15); color: var(--accent3); } | |
| .tag-purple { background: rgba(108,99,255,0.15); color: var(--accent); } | |
| .tag-pink { background: rgba(255,101,132,0.15); color: var(--accent2); } | |
| /* Applications */ | |
| .app-grid { | |
| display: grid; grid-template-columns: repeat(auto-fit, minmax(240px, 1fr)); | |
| gap: 1.5rem; | |
| } | |
| .app-card { | |
| background: var(--surface); border: 1px solid var(--border); | |
| border-radius: 16px; padding: 1.8rem; text-align: center; | |
| transition: all 0.3s; cursor: default; | |
| } | |
| .app-card:hover { border-color: var(--accent2); transform: translateY(-3px); } | |
| .app-icon { font-size: 2.5rem; margin-bottom: 1rem; } | |
| .app-card h4 { font-size: 1rem; font-weight: 700; margin-bottom: 0.5rem; } | |
| .app-card p { font-size: 0.8rem; color: var(--text-dim); } | |
| /* Scroll animations */ | |
| .fade-up { | |
| opacity: 0; transform: translateY(40px); | |
| transition: opacity 0.7s ease, transform 0.7s ease; | |
| } | |
| .fade-up.visible { opacity: 1; transform: translateY(0); } | |
| /* Divider */ | |
| .divider { | |
| height: 1px; max-width: 1100px; margin: 0 auto; | |
| background: linear-gradient(90deg, transparent, var(--border), transparent); | |
| } | |
| /* Footer */ | |
| footer { | |
| border-top: 1px solid var(--border); | |
| padding: 2rem; | |
| } | |
| .footer-inner { | |
| max-width: 1200px; margin: 0 auto; | |
| display: flex; justify-content: space-between; align-items: center; | |
| flex-wrap: wrap; gap: 1rem; | |
| } | |
| .footer-inner span { font-size: 0.85rem; color: var(--text-dim); } | |
| .footer-inner a { font-size: 0.85rem; color: var(--accent); text-decoration: none; transition: color 0.3s; } | |
| .footer-inner a:hover { color: var(--text); } | |
| /* Responsive */ | |
| @media (max-width: 768px) { | |
| nav .nav-links { display: none; } | |
| .hamburger { display: flex; } | |
| nav .nav-links.open { | |
| display: flex; flex-direction: column; | |
| position: absolute; top: 64px; left: 0; right: 0; | |
| background: rgba(10,10,15,0.98); padding: 2rem; | |
| border-bottom: 1px solid var(--border); | |
| } | |
| .hero-stats { gap: 1.5rem; } | |
| .demo-container { padding: 1.5rem; } | |
| .comparison-table { font-size: 0.75rem; } | |
| .comparison-table th, .comparison-table td { padding: 0.7rem; } | |
| } | |
| /* Glow pulse */ | |
| @keyframes glow-pulse { | |
| 0%, 100% { box-shadow: 0 0 20px rgba(108,99,255,0.2); } | |
| 50% { box-shadow: 0 0 40px rgba(108,99,255,0.4); } | |
| } | |
| .slider-container { display: flex; align-items: center; gap: 1rem; flex-wrap: wrap; } | |
| .slider-container label { font-size: 0.85rem; font-weight: 600; } | |
| input[type="range"] { | |
| -webkit-appearance: none; appearance: none; | |
| width: 180px; height: 6px; border-radius: 3px; | |
| background: var(--border); outline: none; | |
| } | |
| input[type="range"]::-webkit-slider-thumb { | |
| -webkit-appearance: none; appearance: none; | |
| width: 18px; height: 18px; border-radius: 50%; | |
| background: var(--accent); cursor: pointer; | |
| } | |
| .slider-val { | |
| font-family: 'JetBrains Mono', monospace; | |
| font-size: 0.85rem; color: var(--accent4); | |
| min-width: 30px; | |
| } | |
| /* Phase indicator */ | |
| .phase-indicator { | |
| display: flex; gap: 0; margin: 1.5rem 0; border-radius: 10px; overflow: hidden; | |
| border: 1px solid var(--border); | |
| } | |
| .phase-seg { | |
| padding: 0.7rem 1.2rem; font-size: 0.75rem; font-weight: 700; | |
| text-transform: uppercase; letter-spacing: 1px; flex: 1; | |
| text-align: center; transition: all 0.5s; | |
| } | |
| .phase-seg.explore-phase { background: rgba(108,99,255,0.15); color: var(--accent); } | |
| .phase-seg.exploit-phase { background: rgba(67,233,123,0.08); color: var(--text-dim); } | |
| .phase-seg.active-phase { background: rgba(108,99,255,0.3); } | |
| .phase-seg.exploit-active { background: rgba(67,233,123,0.25); color: var(--accent3); } | |
| .round-counter { | |
| font-family: 'JetBrains Mono', monospace; | |
| font-size: 1.5rem; font-weight: 700; color: var(--accent); | |
| margin-bottom: 0.5rem; | |
| } | |
| .info-tooltip { | |
| display: inline-flex; align-items: center; justify-content: center; | |
| width: 18px; height: 18px; border-radius: 50%; | |
| background: var(--border); color: var(--text-dim); | |
| font-size: 0.65rem; font-weight: 700; cursor: help; | |
| margin-left: 0.3rem; position: relative; | |
| } | |
| .info-tooltip:hover::after { | |
| content: attr(data-tip); | |
| position: absolute; bottom: 130%; left: 50%; transform: translateX(-50%); | |
| padding: 0.5rem 0.8rem; border-radius: 8px; background: var(--surface2); | |
| border: 1px solid var(--border); font-size: 0.7rem; color: var(--text); | |
| white-space: nowrap; z-index: 10; font-weight: 400; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <!-- NAV --> | |
| <nav id="navbar"> | |
| <div class="nav-inner"> | |
| <div class="logo">MA-CMAB</div> | |
| <ul class="nav-links" id="nav-links"> | |
| <li><a href="#problem">The Problem</a></li> | |
| <li><a href="#how">How It Works</a></li> | |
| <li><a href="#demo">Live Demo</a></li> | |
| <li><a href="#results">Results</a></li> | |
| <li><a href="#applications">Applications</a></li> | |
| </ul> | |
| <button class="hamburger" id="hamburger" aria-label="Menu"> | |
| <span></span><span></span><span></span> | |
| </button> | |
| </div> | |
| </nav> | |
| <!-- HERO --> | |
| <section class="hero"> | |
| <div class="hero-bg"></div> | |
| <canvas id="hero-canvas"></canvas> | |
| <div class="hero-content fade-up"> | |
| <div class="hero-badge">AAMAS 2026 · Accepted Paper</div> | |
| <h1>Smarter Resource Sharing<br/>Through <span class="gradient-text">Learning Under Uncertainty</span></h1> | |
| <p>How do you divide resources among multiple agents to maximize everyone's benefit—when you can only see the <em>total</em> outcome, not individual contributions? This paper solves it.</p> | |
| <a href="#problem" class="hero-cta">Explore the Research ↓</a> | |
| <div class="hero-stats"> | |
| <div class="hero-stat"> | |
| <div class="num">M</div> | |
| <div class="label">Non-Communicating Agents</div> | |
| </div> | |
| <div class="hero-stat"> | |
| <div class="num">N</div> | |
| <div class="label">Indivisible Items</div> | |
| </div> | |
| <div class="hero-stat"> | |
| <div class="num">T</div> | |
| <div class="label">Learning Rounds</div> | |
| </div> | |
| <div class="hero-stat"> | |
| <div class="num">Õ(T<sup style="font-size:0.6em">⅔</sup>)</div> | |
| <div class="label">Regret Bound</div> | |
| </div> | |
| </div> | |
| </div> | |
| </section> | |
| <!-- THE PROBLEM --> | |
| <div class="divider"></div> | |
| <section id="problem"> | |
| <div class="section-inner fade-up"> | |
| <div class="section-label">The Problem</div> | |
| <h2 class="section-title">Dividing Items Fairly When You Can't See Everything</h2> | |
| <p class="section-desc"> | |
| Imagine you're an auctioneer dividing items among bidders, a platform assigning tasks to workers, or a system allocating bandwidth to users. Each recipient values bundles of items differently. Your goal: maximize <strong>total welfare</strong> — the sum of everyone's satisfaction. | |
| </p> | |
| <div class="card-grid"> | |
| <div class="card"> | |
| <div class="card-icon" style="background: rgba(108,99,255,0.15);">🧩</div> | |
| <h3>Submodular Welfare Problem</h3> | |
| <p>Each agent has a utility function with <strong>diminishing returns</strong> — getting more items helps, but each extra item helps a little less. This "submodularity" makes the math tractable but optimization hard.</p> | |
| </div> | |
| <div class="card"> | |
| <div class="card-icon" style="background: rgba(255,101,132,0.15);">🔒</div> | |
| <h3>Bandit Feedback Only</h3> | |
| <p>You only see the <strong>total reward</strong> after each allocation — not how much each agent individually benefited. It's like knowing a team's total score but not who scored each point.</p> | |
| </div> | |
| <div class="card"> | |
| <div class="card-icon" style="background: rgba(67,233,123,0.15);">🤐</div> | |
| <h3>Non-Communicating Agents</h3> | |
| <p>Agents <strong>can't talk to each other</strong>. There's no sharing of strategies, rewards, or information. Each operates independently, yet they compete for the same pool of items.</p> | |
| </div> | |
| <div class="card"> | |
| <div class="card-icon" style="background: rgba(56,249,215,0.15);">✂️</div> | |
| <h3>Partition Constraint</h3> | |
| <p>Each item goes to <strong>exactly one agent</strong> — no sharing or duplicating. This creates a complex partition matroid constraint that couples all agents' decisions together.</p> | |
| </div> | |
| </div> | |
| </div> | |
| </section> | |
| <!-- HOW IT WORKS --> | |
| <div class="divider"></div> | |
| <section id="how"> | |
| <div class="section-inner fade-up"> | |
| <div class="section-label">The Solution</div> | |
| <h2 class="section-title">Explore, Learn, Then Commit</h2> | |
| <p class="section-desc"> | |
| The MA-CMAB algorithm uses a two-phase strategy: first explore different allocations to learn about utilities, then commit to the best one found. Simple in concept, powerful in practice. | |
| </p> | |
| <div style="display: grid; grid-template-columns: 1fr 1fr; gap: 3rem; align-items: start;" class="algo-layout"> | |
| <div> | |
| <div class="algo-timeline" id="algo-timeline"> | |
| <div class="algo-step active" data-step="1"> | |
| <h4>1. Initialize</h4> | |
| <p>Set up the exploration budget <em>m</em> based on the time horizon T, number of agents M, and items N. The key insight: explore for ~T<sup>2/3</sup> rounds.</p> | |
| </div> | |
| <div class="algo-step" data-step="2"> | |
| <h4>2. Exploration Phase</h4> | |
| <p>Try different allocations. For each one, play it <em>m</em> times and average the rewards to get a reliable estimate of its true welfare value.</p> | |
| </div> | |
| <div class="algo-step" data-step="3"> | |
| <h4>3. Offline Oracle</h4> | |
| <p>Feed the averaged estimates into the <strong>Continuous Greedy</strong> algorithm — a powerful offline method that finds a (1−1/e) ≈ 63% approximation of optimal welfare.</p> | |
| </div> | |
| <div class="algo-step" data-step="4"> | |
| <h4>4. Pipage Rounding</h4> | |
| <p>Convert the fractional solution (e.g., "assign item 3 to agent 1 with probability 0.7") into a concrete integer allocation with almost no loss in quality.</p> | |
| </div> | |
| <div class="algo-step" data-step="5"> | |
| <h4>5. Exploitation Phase</h4> | |
| <p>Commit to the best allocation found and play it for all remaining rounds. The exploration paid off — now reap the rewards.</p> | |
| </div> | |
| </div> | |
| </div> | |
| <div> | |
| <div style="background: var(--surface); border: 1px solid var(--border); border-radius: 16px; padding: 2rem; position: sticky; top: 80px;"> | |
| <h4 style="margin-bottom: 1rem; font-size: 0.95rem;">Key Equation: Regret Bound</h4> | |
| <div class="eq-box" style="display: block; text-align: center; font-size: 1.1rem;"> | |
| E[R(T)] = Õ(δ<sup>2/3</sup> · η<sup>1/3</sup> · C<sup>2/3</sup> · T<sup>2/3</sup>) | |
| </div> | |
| <div style="margin-top: 1.5rem;"> | |
| <div style="display: flex; align-items: start; gap: 0.8rem; margin-bottom: 0.8rem;"> | |
| <span class="tag tag-purple">α</span> | |
| <span style="font-size: 0.85rem; color: var(--text-dim);">= 1 − 1/e ≈ 0.632 — the offline approximation ratio</span> | |
| </div> | |
| <div style="display: flex; align-items: start; gap: 0.8rem; margin-bottom: 0.8rem;"> | |
| <span class="tag tag-pink">δ</span> | |
| <span style="font-size: 0.85rem; color: var(--text-dim);">= (4MN + 2M) — noise sensitivity parameter</span> | |
| </div> | |
| <div style="display: flex; align-items: start; gap: 0.8rem; margin-bottom: 0.8rem;"> | |
| <span class="tag tag-green">η</span> | |
| <span style="font-size: 0.85rem; color: var(--text-dim);">= (MN)<sup>8</sup> — oracle complexity (# queries)</span> | |
| </div> | |
| </div> | |
| <p style="font-size: 0.8rem; color: var(--text-dim); margin-top: 1rem; line-height: 1.6;"> | |
| The regret grows as T<sup>2/3</sup> — <strong>sublinearly</strong>. This means the average per-round regret → 0 as T → ∞. The algorithm eventually performs nearly as well as the best offline solution! | |
| </p> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| </section> | |
| <!-- LIVE DEMO --> | |
| <div class="divider"></div> | |
| <section id="demo"> | |
| <div class="section-inner fade-up"> | |
| <div class="section-label">Interactive Demo</div> | |
| <h2 class="section-title">Watch the Algorithm Learn in Real Time</h2> | |
| <p class="section-desc"> | |
| See how the explore-then-commit strategy works. Adjust parameters and watch agents learn to allocate items for maximum welfare. | |
| </p> | |
| <div class="demo-container"> | |
| <div class="demo-header"> | |
| <div> | |
| <h3>MA-CMAB Allocation Simulator</h3> | |
| <p style="font-size: 0.8rem; color: var(--text-dim);">Agents have submodular utilities — each item helps, but with diminishing returns</p> | |
| </div> | |
| <div style="display: flex; gap: 0.5rem;"> | |
| <button class="btn btn-primary" id="btn-run">▶ Run Simulation</button> | |
| <button class="btn btn-outline" id="btn-reset">↻ Reset</button> | |
| </div> | |
| </div> | |
| <div class="slider-container" style="margin-bottom: 1.5rem; gap: 2rem;"> | |
| <div class="slider-container"> | |
| <label>Agents (M):</label> | |
| <input type="range" id="slider-agents" min="2" max="5" value="3" /> | |
| <span class="slider-val" id="val-agents">3</span> | |
| </div> | |
| <div class="slider-container"> | |
| <label>Items (N):</label> | |
| <input type="range" id="slider-items" min="4" max="12" value="6" /> | |
| <span class="slider-val" id="val-items">6</span> | |
| </div> | |
| <div class="slider-container"> | |
| <label>Rounds (T):</label> | |
| <input type="range" id="slider-rounds" min="50" max="500" value="200" step="10" /> | |
| <span class="slider-val" id="val-rounds">200</span> | |
| </div> | |
| </div> | |
| <div class="phase-indicator" id="phase-indicator"> | |
| <div class="phase-seg explore-phase active-phase" id="phase-explore">🔍 Exploration</div> | |
| <div class="phase-seg exploit-phase" id="phase-exploit">🎯 Exploitation</div> | |
| </div> | |
| <div style="display: flex; align-items: center; gap: 1rem; margin-bottom: 1.5rem;"> | |
| <span style="font-size: 0.8rem; color: var(--text-dim);">Round:</span> | |
| <span class="round-counter" id="round-counter">0 / 200</span> | |
| </div> | |
| <div id="alloc-viz"></div> | |
| <div style="display: grid; grid-template-columns: 1fr 1fr; gap: 2rem;"> | |
| <div> | |
| <div class="welfare-bar-label">Current Total Welfare <span class="info-tooltip" data-tip="Sum of all agents' submodular utilities">?</span></div> | |
| <div class="welfare-bar-track"><div class="welfare-bar-fill" id="welfare-fill" style="width: 0%"></div></div> | |
| <div class="welfare-value" id="welfare-value">0.00</div> | |
| </div> | |
| <div> | |
| <div class="welfare-bar-label">Best Possible (1−1/e)·OPT <span class="info-tooltip" data-tip="The theoretical best the algorithm can guarantee">?</span></div> | |
| <div class="welfare-bar-track"><div class="welfare-bar-fill" id="opt-fill" style="width: 63%; background: linear-gradient(90deg, var(--accent2), #ff9a9e);"></div></div> | |
| <div class="welfare-value" id="opt-value" style="background: linear-gradient(135deg, var(--accent2), #ff9a9e); -webkit-background-clip: text;">≈ 0.63</div> | |
| </div> | |
| </div> | |
| <div style="margin-top: 2rem;"> | |
| <div class="welfare-bar-label">Cumulative Regret Over Time</div> | |
| <canvas id="regret-canvas"></canvas> | |
| </div> | |
| </div> | |
| </div> | |
| </section> | |
| <!-- RESILIENCE --> | |
| <div class="divider"></div> | |
| <section id="results"> | |
| <div class="section-inner fade-up"> | |
| <div class="section-label">Key Results</div> | |
| <h2 class="section-title">Robust Even With Noisy Information</h2> | |
| <p class="section-desc"> | |
| A major contribution is proving <strong>resilience</strong>: the Continuous Greedy algorithm still works well even when utility estimates are noisy — which is exactly what happens during online learning. | |
| </p> | |
| <div class="card-grid" style="grid-template-columns: 1fr 1fr;"> | |
| <div class="card" style="border-color: rgba(108,99,255,0.3);"> | |
| <h3>Resilience Theorem</h3> | |
| <p style="margin-bottom: 1rem;">Under noisy oracles with error ≤ ε, the Continuous Greedy algorithm achieves:</p> | |
| <div class="eq-box" style="font-size: 0.85rem;"> | |
| f(S) ≥ (1 − 1/e) · f(OPT) − (4MN + 2M)·ε | |
| </div> | |
| <p style="margin-top: 1rem; font-size: 0.85rem; color: var(--text-dim);"> | |
| The approximation degrades <em>gracefully</em> — only linearly in noise ε. When ε → 0, we recover the classic (1−1/e) guarantee. | |
| </p> | |
| </div> | |
| <div class="card" style="border-color: rgba(67,233,123,0.3);"> | |
| <h3>Clean Event Guarantee</h3> | |
| <p style="margin-bottom: 1rem;">With high probability (≥ 1 − 2η/T), all empirical estimates concentrate around truth:</p> | |
| <div class="eq-box" style="font-size: 0.85rem;"> | |
| |f̄(S) − f(S)| < √(log T / 2m) | |
| </div> | |
| <p style="margin-top: 1rem; font-size: 0.85rem; color: var(--text-dim);"> | |
| This "clean event" makes the offline-to-online transfer rigorous. Bad estimates are exponentially unlikely. | |
| </p> | |
| </div> | |
| </div> | |
| <h3 style="margin-top: 3rem; margin-bottom: 1rem; font-size: 1.1rem;">How This Compares</h3> | |
| <div style="overflow-x: auto;"> | |
| <table class="comparison-table"> | |
| <thead> | |
| <tr> | |
| <th>Framework</th> | |
| <th>Agents</th> | |
| <th>Communication</th> | |
| <th>Action Type</th> | |
| <th>Feedback</th> | |
| <th>Regret</th> | |
| </tr> | |
| </thead> | |
| <tbody> | |
| <tr> | |
| <td>C-ETC (Nie et al., 2023)</td> | |
| <td>Single</td> | |
| <td>N/A</td> | |
| <td>Single subset</td> | |
| <td>Full-bandit</td> | |
| <td>Õ(T<sup>2/3</sup>)</td> | |
| </tr> | |
| <tr> | |
| <td>Fourati et al. (2024a)</td> | |
| <td>Multi</td> | |
| <td><span class="tag tag-pink">Yes</span></td> | |
| <td>Shared subset</td> | |
| <td>Semi-bandit</td> | |
| <td>Õ(T<sup>2/3</sup>)</td> | |
| </tr> | |
| <tr class="highlight-row"> | |
| <td><strong>MA-CMAB (This Paper)</strong></td> | |
| <td><strong>Multi</strong></td> | |
| <td><span class="tag tag-green">None</span></td> | |
| <td><strong>Partition</strong></td> | |
| <td><strong>Full-bandit</strong></td> | |
| <td><strong>Õ(T<sup>2/3</sup>)</strong></td> | |
| </tr> | |
| </tbody> | |
| </table> | |
| </div> | |
| <p style="font-size: 0.8rem; color: var(--text-dim); margin-top: 0.8rem;"> | |
| ★ MA-CMAB achieves the same regret rate with the hardest feedback model (full-bandit) and no inter-agent communication — a strictly harder setting. | |
| </p> | |
| </div> | |
| </section> | |
| <!-- APPLICATIONS --> | |
| <div class="divider"></div> | |
| <section id="applications"> | |
| <div class="section-inner fade-up"> | |
| <div class="section-label">Real-World Impact</div> | |
| <h2 class="section-title">Where This Framework Applies</h2> | |
| <p class="section-desc"> | |
| The MA-CMAB framework applies wherever you need to divide resources among competing parties and learn from aggregate outcomes. | |
| </p> | |
| <div class="app-grid"> | |
| <div class="app-card"> | |
| <div class="app-icon">🛒</div> | |
| <h4>Combinatorial Auctions</h4> | |
| <p>Allocate goods to bidders in repeated auctions where true valuations are unknown and only total revenue is observed.</p> | |
| </div> | |
| <div class="app-card"> | |
| <div class="app-icon">📱</div> | |
| <h4>Recommender Systems</h4> | |
| <p>Partition content across user groups to maximize total engagement, with only aggregate click-through data available.</p> | |
| </div> | |
| <div class="app-card"> | |
| <div class="app-icon">📡</div> | |
| <h4>Distributed Sensing</h4> | |
| <p>Assign sensor targets to non-communicating agents to maximize total coverage with only aggregate quality feedback.</p> | |
| </div> | |
| <div class="app-card"> | |
| <div class="app-icon">🌐</div> | |
| <h4>Influence Maximization</h4> | |
| <p>Divide seed users across campaigns to maximize total influence spread in social networks.</p> | |
| </div> | |
| <div class="app-card"> | |
| <div class="app-icon">⚖️</div> | |
| <h4>Fair Division</h4> | |
| <p>Allocate indivisible goods among people with unknown preferences to maximize utilitarian social welfare.</p> | |
| </div> | |
| <div class="app-card"> | |
| <div class="app-icon">📊</div> | |
| <h4>Data Summarization</h4> | |
| <p>Partition datasets across workers to maximize total information coverage with submodular diversity objectives.</p> | |
| </div> | |
| </div> | |
| </div> | |
| </section> | |
| <!-- TAKEAWAY --> | |
| <div class="divider"></div> | |
| <section> | |
| <div class="section-inner fade-up" style="text-align: center;"> | |
| <div class="section-label">Key Takeaway</div> | |
| <h2 class="section-title" style="max-width: 800px; margin: 0 auto 1.5rem;"> | |
| The First Sublinear Regret Guarantee for<br/> | |
| <span style="background: linear-gradient(135deg, var(--accent), var(--accent3)); -webkit-background-clip: text; -webkit-text-fill-color: transparent;"> | |
| Multi-Agent Partitioned Welfare Maximization | |
| </span><br/>Under Bandit Feedback | |
| </h2> | |
| <p style="color: var(--text-dim); max-width: 600px; margin: 0 auto 2rem; line-height: 1.7;"> | |
| By bridging offline submodular optimization with online multi-agent bandit learning, this work opens the door to practical, scalable algorithms for resource allocation under real-world information constraints. | |
| </p> | |
| <div class="eq-box" style="font-size: 1.1rem; animation: glow-pulse 3s ease-in-out infinite;"> | |
| Regret → 0 per round as T → ∞ | |
| </div> | |
| </div> | |
| </section> | |
| <!-- FOOTER --> | |
| <footer> | |
| <div class="footer-inner"> | |
| <span>© 2026 Amroja, LLC</span> | |
| <a href="https://johndamask.com" target="_blank" rel="noopener">johndamask.com</a> | |
| </div> | |
| </footer> | |
| <script> | |
| // --- NAV --- | |
| const hamburger = document.getElementById('hamburger'); | |
| const navLinks = document.getElementById('nav-links'); | |
| hamburger.addEventListener('click', () => navLinks.classList.toggle('open')); | |
| document.querySelectorAll('.nav-links a').forEach(a => a.addEventListener('click', () => navLinks.classList.remove('open'))); | |
| // --- SCROLL ANIMATIONS --- | |
| const fadeEls = document.querySelectorAll('.fade-up'); | |
| const obs = new IntersectionObserver((entries) => { | |
| entries.forEach(e => { if (e.isIntersecting) { e.target.classList.add('visible'); obs.unobserve(e.target); } }); | |
| }, { threshold: 0.15 }); | |
| fadeEls.forEach(el => obs.observe(el)); | |
| // --- ALGO TIMELINE --- | |
| const steps = document.querySelectorAll('.algo-step'); | |
| let currentStep = 0; | |
| setInterval(() => { | |
| steps.forEach(s => s.classList.remove('active')); | |
| steps[currentStep].classList.add('active'); | |
| currentStep = (currentStep + 1) % steps.length; | |
| }, 2500); | |
| // --- HERO PARTICLES --- | |
| (function() { | |
| const canvas = document.getElementById('hero-canvas'); | |
| const ctx = canvas.getContext('2d'); | |
| let particles = []; | |
| function resize() { canvas.width = canvas.offsetWidth; canvas.height = canvas.offsetHeight; } | |
| resize(); | |
| window.addEventListener('resize', resize); | |
| for (let i = 0; i < 60; i++) { | |
| particles.push({ | |
| x: Math.random() * canvas.width, | |
| y: Math.random() * canvas.height, | |
| vx: (Math.random() - 0.5) * 0.3, | |
| vy: (Math.random() - 0.5) * 0.3, | |
| r: Math.random() * 2 + 1, | |
| color: ['rgba(108,99,255,','rgba(255,101,132,','rgba(67,233,123,','rgba(56,249,215,'][Math.floor(Math.random()*4)] | |
| }); | |
| } | |
| function draw() { | |
| ctx.clearRect(0, 0, canvas.width, canvas.height); | |
| particles.forEach((p, i) => { | |
| p.x += p.vx; p.y += p.vy; | |
| if (p.x < 0 || p.x > canvas.width) p.vx *= -1; | |
| if (p.y < 0 || p.y > canvas.height) p.vy *= -1; | |
| ctx.beginPath(); | |
| ctx.arc(p.x, p.y, p.r, 0, Math.PI * 2); | |
| ctx.fillStyle = p.color + '0.5)'; | |
| ctx.fill(); | |
| // Connect nearby particles | |
| for (let j = i + 1; j < particles.length; j++) { | |
| const dx = p.x - particles[j].x, dy = p.y - particles[j].y; | |
| const dist = Math.sqrt(dx*dx + dy*dy); | |
| if (dist < 120) { | |
| ctx.beginPath(); | |
| ctx.moveTo(p.x, p.y); | |
| ctx.lineTo(particles[j].x, particles[j].y); | |
| ctx.strokeStyle = p.color + (0.15 * (1 - dist/120)) + ')'; | |
| ctx.lineWidth = 0.5; | |
| ctx.stroke(); | |
| } | |
| } | |
| }); | |
| requestAnimationFrame(draw); | |
| } | |
| draw(); | |
| })(); | |
| // --- SIMULATION --- | |
| const agentColors = ['#6c63ff', '#ff6584', '#43e97b', '#38f9d7', '#ffd700']; | |
| const agentNames = ['Alice', 'Bob', 'Carol', 'Dave', 'Eve']; | |
| const itemEmojis = ['📦','💎','🎨','📚','🔧','🎵','🏀','🧪','🌸','🎯','⚡','🍕']; | |
| let simState = null; | |
| let simRunning = false; | |
| let simInterval = null; | |
| function getParams() { | |
| return { | |
| M: +document.getElementById('slider-agents').value, | |
| N: +document.getElementById('slider-items').value, | |
| T: +document.getElementById('slider-rounds').value | |
| }; | |
| } | |
| // Submodular utility: sqrt-based coverage | |
| function submodularUtil(items, agentIdx, N) { | |
| if (items.length === 0) return 0; | |
| // Each agent values items differently | |
| let val = 0; | |
| const seen = new Set(); | |
| items.forEach(item => { | |
| if (!seen.has(item)) { | |
| seen.add(item); | |
| // Weighted diminishing returns | |
| const weight = ((item + agentIdx * 3 + 1) % N + 1) / N; | |
| val += weight / Math.sqrt(seen.size); | |
| } | |
| }); | |
| return Math.min(val / Math.sqrt(N), 1); | |
| } | |
| function totalWelfare(allocation, M, N) { | |
| let total = 0; | |
| for (let i = 0; i < M; i++) { | |
| total += submodularUtil(allocation[i], i, N); | |
| } | |
| return total; | |
| } | |
| function randomPartition(M, N) { | |
| const alloc = Array.from({length: M}, () => []); | |
| const items = Array.from({length: N}, (_, i) => i); | |
| // Shuffle | |
| for (let i = items.length - 1; i > 0; i--) { | |
| const j = Math.floor(Math.random() * (i + 1)); | |
| [items[i], items[j]] = [items[j], items[i]]; | |
| } | |
| items.forEach((item, idx) => alloc[idx % M].push(item)); | |
| return alloc; | |
| } | |
| function greedyPartition(M, N) { | |
| const alloc = Array.from({length: M}, () => []); | |
| const items = Array.from({length: N}, (_, i) => i); | |
| // Greedy: for each item, assign to agent with max marginal gain | |
| items.forEach(item => { | |
| let bestAgent = 0, bestGain = -1; | |
| for (let i = 0; i < M; i++) { | |
| const gain = submodularUtil([...alloc[i], item], i, N) - submodularUtil(alloc[i], i, N); | |
| if (gain > bestGain) { bestGain = gain; bestAgent = i; } | |
| } | |
| alloc[bestAgent].push(item); | |
| }); | |
| return alloc; | |
| } | |
| function initSim() { | |
| const {M, N, T} = getParams(); | |
| const optAlloc = greedyPartition(M, N); | |
| const optWelfare = totalWelfare(optAlloc, M, N); | |
| const exploreRounds = Math.ceil(Math.pow(T, 2/3)); | |
| simState = { | |
| M, N, T, round: 0, | |
| exploreRounds, | |
| phase: 'explore', | |
| bestAlloc: null, | |
| bestWelfare: 0, | |
| currentAlloc: Array.from({length: M}, () => []), | |
| optWelfare, | |
| regretHistory: [], | |
| cumRegret: 0, | |
| triedAllocs: [], | |
| triedWelfares: [], | |
| currentWelfare: 0 | |
| }; | |
| renderAllocViz(); | |
| updateDisplay(); | |
| drawRegretChart(); | |
| } | |
| function renderAllocViz() { | |
| const {M, N} = getParams(); | |
| const viz = document.getElementById('alloc-viz'); | |
| viz.innerHTML = ''; | |
| for (let i = 0; i < M; i++) { | |
| const box = document.createElement('div'); | |
| box.className = 'agent-box'; | |
| box.id = `agent-box-${i}`; | |
| box.innerHTML = ` | |
| <div class="agent-label"> | |
| <span class="agent-dot" style="background:${agentColors[i]}"></span> | |
| ${agentNames[i]} (Agent ${i+1}) | |
| </div> | |
| <div class="agent-items" id="agent-items-${i}"></div> | |
| <div style="margin-top:0.8rem;"> | |
| <span style="font-size:0.7rem;color:var(--text-dim)">Utility:</span> | |
| <span style="font-family:'JetBrains Mono';font-size:0.85rem;color:${agentColors[i]}" id="agent-util-${i}">0.00</span> | |
| </div> | |
| `; | |
| viz.appendChild(box); | |
| } | |
| } | |
| function updateAllocViz(alloc) { | |
| const {M, N} = simState; | |
| for (let i = 0; i < M; i++) { | |
| const container = document.getElementById(`agent-items-${i}`); | |
| const box = document.getElementById(`agent-box-${i}`); | |
| if (!container) continue; | |
| container.innerHTML = ''; | |
| (alloc[i] || []).forEach(item => { | |
| const chip = document.createElement('span'); | |
| chip.className = 'item-chip'; | |
| chip.textContent = `${itemEmojis[item % itemEmojis.length]} Item ${item+1}`; | |
| container.appendChild(chip); | |
| }); | |
| const util = submodularUtil(alloc[i] || [], i, N); | |
| const utilEl = document.getElementById(`agent-util-${i}`); | |
| if (utilEl) utilEl.textContent = util.toFixed(3); | |
| box.classList.remove('highlight'); | |
| if (alloc[i] && alloc[i].length > 0) { | |
| box.classList.add('highlight'); | |
| setTimeout(() => box.classList.remove('highlight'), 600); | |
| } | |
| } | |
| } | |
| function updateDisplay() { | |
| const s = simState; | |
| if (!s) return; | |
| document.getElementById('round-counter').textContent = `${s.round} / ${s.T}`; | |
| const expPhase = document.getElementById('phase-explore'); | |
| const expltPhase = document.getElementById('phase-exploit'); | |
| expPhase.className = 'phase-seg explore-phase' + (s.phase === 'explore' ? ' active-phase' : ''); | |
| expltPhase.className = 'phase-seg exploit-phase' + (s.phase === 'exploit' ? ' exploit-active' : ''); | |
| document.getElementById('welfare-fill').style.width = (s.currentWelfare / Math.max(s.optWelfare, 0.01) * 100) + '%'; | |
| document.getElementById('welfare-value').textContent = s.currentWelfare.toFixed(3); | |
| const approxOpt = (1 - 1/Math.E) * s.optWelfare; | |
| document.getElementById('opt-fill').style.width = (approxOpt / Math.max(s.optWelfare, 0.01) * 100) + '%'; | |
| document.getElementById('opt-value').textContent = `≈ ${approxOpt.toFixed(3)}`; | |
| } | |
| function simStep() { | |
| const s = simState; | |
| if (!s || s.round >= s.T) { | |
| stopSim(); | |
| return; | |
| } | |
| s.round++; | |
| const {M, N} = s; | |
| const benchmark = (1 - 1/Math.E) * s.optWelfare; | |
| if (s.round <= s.exploreRounds) { | |
| s.phase = 'explore'; | |
| const alloc = randomPartition(M, N); | |
| const w = totalWelfare(alloc, M, N) + (Math.random() - 0.5) * 0.05; // noise | |
| s.triedAllocs.push(alloc); | |
| s.triedWelfares.push(w); | |
| if (w > s.bestWelfare) { | |
| s.bestWelfare = w; | |
| s.bestAlloc = alloc; | |
| } | |
| s.currentAlloc = alloc; | |
| s.currentWelfare = Math.max(0, w); | |
| } else { | |
| s.phase = 'exploit'; | |
| if (!s.committed) { | |
| // Run greedy on best estimates | |
| s.bestAlloc = greedyPartition(M, N); | |
| s.bestWelfare = totalWelfare(s.bestAlloc, M, N); | |
| s.committed = true; | |
| } | |
| const noise = (Math.random() - 0.5) * 0.02; | |
| s.currentAlloc = s.bestAlloc; | |
| s.currentWelfare = Math.max(0, s.bestWelfare + noise); | |
| } | |
| const instantRegret = Math.max(0, benchmark - s.currentWelfare); | |
| s.cumRegret += instantRegret; | |
| s.regretHistory.push(s.cumRegret); | |
| updateAllocViz(s.currentAlloc); | |
| updateDisplay(); | |
| drawRegretChart(); | |
| } | |
| function startSim() { | |
| if (simRunning) return; | |
| initSim(); | |
| simRunning = true; | |
| const speed = simState.T > 200 ? 20 : 40; | |
| simInterval = setInterval(simStep, speed); | |
| } | |
| function stopSim() { | |
| simRunning = false; | |
| if (simInterval) clearInterval(simInterval); | |
| simInterval = null; | |
| } | |
| function resetSim() { | |
| stopSim(); | |
| initSim(); | |
| } | |
| document.getElementById('btn-run').addEventListener('click', startSim); | |
| document.getElementById('btn-reset').addEventListener('click', resetSim); | |
| ['slider-agents','slider-items','slider-rounds'].forEach(id => { | |
| const el = document.getElementById(id); | |
| const valId = id.replace('slider-', 'val-'); | |
| el.addEventListener('input', () => { | |
| document.getElementById(valId).textContent = el.value; | |
| if (!simRunning) initSim(); | |
| }); | |
| }); | |
| // --- REGRET CHART --- | |
| function drawRegretChart() { | |
| const canvas = document.getElementById('regret-canvas'); | |
| 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); | |
| if (!simState || simState.regretHistory.length < 2) { | |
| ctx.fillStyle = '#8888a0'; | |
| ctx.font = '14px Inter'; | |
| ctx.textAlign = 'center'; | |
| ctx.fillText('Run the simulation to see regret curve', W/2, H/2); | |
| return; | |
| } | |
| const data = simState.regretHistory; | |
| const T = simState.T; | |
| const maxR = Math.max(...data, 1); | |
| const pad = {t: 30, r: 20, b: 40, l: 60}; | |
| const cW = W - pad.l - pad.r; | |
| const cH = H - pad.t - pad.b; | |
| // Grid lines | |
| ctx.strokeStyle = 'rgba(42,42,62,0.6)'; | |
| ctx.lineWidth = 0.5; | |
| for (let i = 0; i <= 4; i++) { | |
| const y = pad.t + (cH / 4) * i; | |
| ctx.beginPath(); ctx.moveTo(pad.l, y); ctx.lineTo(W - pad.r, y); ctx.stroke(); | |
| ctx.fillStyle = '#8888a0'; ctx.font = '10px JetBrains Mono'; ctx.textAlign = 'right'; | |
| ctx.fillText((maxR * (1 - i/4)).toFixed(1), pad.l - 8, y + 4); | |
| } | |
| // T^{2/3} reference curve | |
| ctx.strokeStyle = 'rgba(255,101,132,0.3)'; | |
| ctx.lineWidth = 1.5; | |
| ctx.setLineDash([4, 4]); | |
| ctx.beginPath(); | |
| const refScale = maxR / Math.pow(data.length, 2/3); | |
| for (let i = 0; i < data.length; i++) { | |
| const x = pad.l + (i / T) * cW; | |
| const y = pad.t + cH - (refScale * Math.pow(i+1, 2/3) / maxR) * cH; | |
| if (i === 0) ctx.moveTo(x, y); else ctx.lineTo(x, y); | |
| } | |
| ctx.stroke(); | |
| ctx.setLineDash([]); | |
| // Exploration region | |
| if (simState.exploreRounds > 0) { | |
| const exX = pad.l + (simState.exploreRounds / T) * cW; | |
| ctx.fillStyle = 'rgba(108,99,255,0.06)'; | |
| ctx.fillRect(pad.l, pad.t, exX - pad.l, cH); | |
| ctx.strokeStyle = 'rgba(108,99,255,0.3)'; | |
| ctx.lineWidth = 1; | |
| ctx.setLineDash([3,3]); | |
| ctx.beginPath(); ctx.moveTo(exX, pad.t); ctx.lineTo(exX, pad.t + cH); ctx.stroke(); | |
| ctx.setLineDash([]); | |
| ctx.fillStyle = 'rgba(108,99,255,0.6)'; ctx.font = '10px Inter'; ctx.textAlign = 'center'; | |
| ctx.fillText('Explore', (pad.l + exX)/2, pad.t + 15); | |
| ctx.fillStyle = 'rgba(67,233,123,0.5)'; | |
| ctx.fillText('Exploit', (exX + W - pad.r)/2, pad.t + 15); | |
| } | |
| // Main curve | |
| const grad = ctx.createLinearGradient(pad.l, 0, W - pad.r, 0); | |
| grad.addColorStop(0, '#6c63ff'); | |
| grad.addColorStop(0.5, '#43e97b'); | |
| grad.addColorStop(1, '#38f9d7'); | |
| ctx.strokeStyle = grad; | |
| ctx.lineWidth = 2.5; | |
| ctx.beginPath(); | |
| data.forEach((v, i) => { | |
| const x = pad.l + (i / T) * cW; | |
| const y = pad.t + cH - (v / maxR) * cH; | |
| if (i === 0) ctx.moveTo(x, y); else ctx.lineTo(x, y); | |
| }); | |
| ctx.stroke(); | |
| // Fill under curve | |
| ctx.lineTo(pad.l + ((data.length - 1) / T) * cW, pad.t + cH); | |
| ctx.lineTo(pad.l, pad.t + cH); | |
| ctx.closePath(); | |
| const fillGrad = ctx.createLinearGradient(0, pad.t, 0, pad.t + cH); | |
| fillGrad.addColorStop(0, 'rgba(108,99,255,0.15)'); | |
| fillGrad.addColorStop(1, 'rgba(108,99,255,0)'); | |
| ctx.fillStyle = fillGrad; | |
| ctx.fill(); | |
| // Labels | |
| ctx.fillStyle = '#8888a0'; ctx.font = '11px Inter'; ctx.textAlign = 'center'; | |
| ctx.fillText('Round', W/2, H - 8); | |
| ctx.save(); | |
| ctx.translate(14, H/2); | |
| ctx.rotate(-Math.PI/2); | |
| ctx.fillText('Cumulative Regret', 0, 0); | |
| ctx.restore(); | |
| // Legend | |
| ctx.fillStyle = '#38f9d7'; ctx.font = '10px Inter'; ctx.textAlign = 'left'; | |
| ctx.fillRect(W - pad.r - 140, pad.t + 5, 10, 3); | |
| ctx.fillText('Actual regret', W - pad.r - 125, pad.t + 10); | |
| ctx.fillStyle = 'rgba(255,101,132,0.5)'; | |
| ctx.setLineDash([4,4]); | |
| ctx.beginPath(); ctx.moveTo(W - pad.r - 140, pad.t + 25); ctx.lineTo(W - pad.r - 130, pad.t + 25); ctx.stroke(); | |
| ctx.setLineDash([]); | |
| ctx.fillStyle = 'rgba(255,101,132,0.7)'; | |
| ctx.fillText('T^(2/3) reference', W - pad.r - 125, pad.t + 28); | |
| } | |
| // Init | |
| initSim(); | |
| window.addEventListener('resize', () => { if (simState) drawRegretChart(); }); | |
| // --- RESPONSIVE ALGO LAYOUT --- | |
| const algoLayout = document.querySelector('.algo-layout'); | |
| function checkAlgoLayout() { | |
| if (window.innerWidth < 768) { | |
| algoLayout.style.gridTemplateColumns = '1fr'; | |
| } else { | |
| algoLayout.style.gridTemplateColumns = '1fr 1fr'; | |
| } | |
| } | |
| checkAlgoLayout(); | |
| window.addEventListener('resize', checkAlgoLayout); | |
| </script> | |
| </body> | |
| </html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment