2025-11-15T02:07:10.757818

Nearly Minimax Optimal Regret for Multinomial Logistic Bandit

Lee, Oh
In this paper, we study the contextual multinomial logit (MNL) bandit problem in which a learning agent sequentially selects an assortment based on contextual information, and user feedback follows an MNL choice model. There has been a significant discrepancy between lower and upper regret bounds, particularly regarding the maximum assortment size $K$. Additionally, the variation in reward structures between these bounds complicates the quest for optimality. Under uniform rewards, where all items have the same expected reward, we establish a regret lower bound of $Ω(d\sqrt{T/K})$ and propose a constant-time algorithm, OFU-MNL+, that achieves a matching upper bound of $\tilde{O}(d\sqrt{T/K})$. We also provide instance-dependent minimax regret bounds under uniform rewards. Under non-uniform rewards, we prove a lower bound of $Ω(d\sqrt{T})$ and an upper bound of $\tilde{O}(d\sqrt{T})$, also achievable by OFU-MNL+. Our empirical studies support these theoretical findings. To the best of our knowledge, this is the first work in the contextual MNL bandit literature to prove minimax optimality -- for either uniform or non-uniform reward setting -- and to propose a computationally efficient algorithm that achieves this optimality up to logarithmic factors.
academic

বহুপদী লজিস্টিক ব্যান্ডিটের জন্য প্রায় মিনিম্যাক্স সর্বোত্তম অনুশোচনা

মৌলিক তথ্য

  • পেপার আইডি: 2405.09831
  • শিরোনাম: Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
  • লেখক: Joongkyu Lee (সিউল জাতীয় বিশ্ববিদ্যালয়), Min-hwan Oh (সিউল জাতীয় বিশ্ববিদ্যালয়)
  • শ্রেণীবিভাগ: stat.ML cs.LG
  • প্রকাশনার সময়/সম্মেলন: NeurIPS 2024 (38তম নিউরাল ইনফরমেশন প্রসেসিং সিস্টেম সম্মেলন)
  • পেপার লিংক: https://arxiv.org/abs/2405.09831

সারসংক্ষেপ

এই পেপারটি প্রসঙ্গ-সচেতন বহুপদী লজিস্টিক (MNL) ব্যান্ডিট সমস্যা অধ্যয়ন করে, যেখানে একটি শিক্ষণ এজেন্ট প্রসঙ্গ তথ্যের উপর ভিত্তি করে ক্রমানুসারে পণ্য সমন্বয় নির্বাচন করে এবং ব্যবহারকারীর প্রতিক্রিয়া MNL নির্বাচন মডেল অনুসরণ করে। বিদ্যমান কাজে নিম্ন এবং উপরের সীমানার মধ্যে উল্লেখযোগ্য ব্যবধান রয়েছে, বিশেষত সর্বাধিক পণ্য সমন্বয় আকার K এর ক্ষেত্রে। একীভূত পুরস্কার সেটিংয়ে, এই পেপারটি Ω(d√T/K) এর অনুশোচনা নিম্ন সীমা প্রতিষ্ঠা করে এবং একটি ধ্রুবক-সময় অ্যালগরিদম OFU-MNL+ প্রস্তাব করে যা মিলিত উপরের সীমা Õ(d√T/K) অর্জন করে। অ-একীভূত পুরস্কার সেটিংয়ে, Ω(d√T) এর নিম্ন সীমা এবং Õ(d√T) এর উপরের সীমা প্রমাণ করা হয়েছে। এটি প্রসঙ্গ-সচেতন MNL ব্যান্ডিট সাহিত্যে মিনিম্যাক্স সর্বোত্তমতা প্রমাণকারী প্রথম কাজ।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

  1. MNL ব্যান্ডিট সমস্যা: সুপারিশ ব্যবস্থা এবং অনলাইন খুচরা বিক্রয় ইত্যাদি প্রয়োগে, একটি এজেন্টকে ব্যবহারকারীদের পণ্যের একটি সেট প্রদান করতে হয়, যেখানে ব্যবহারকারীর নির্বাচন আচরণ বহুপদী লজিস্টিক (MNL) মডেল অনুসরণ করে
  2. প্রসঙ্গ তথ্য: প্রতিটি রাউন্ডে এজেন্ট পণ্য বৈশিষ্ট্য এবং সম্ভাব্য ব্যবহারকারী প্রসঙ্গ তথ্য পর্যবেক্ষণ করতে পারে
  3. তাত্ত্বিক ফাঁক: বিদ্যমান কাজে অনুশোচনা সীমানার উপরের এবং নিম্ন সীমানার মধ্যে উল্লেখযোগ্য ব্যবধান রয়েছে, বিশেষত পণ্য সমন্বয় আকার K এর উপর নির্ভরতার ক্ষেত্রে

গবেষণা প্রেরণা

  1. তাত্ত্বিক সম্পূর্ণতা: MNL ব্যান্ডিট তাত্ত্বিক বিশ্লেষণে ফাঁক পূরণ করা এবং কঠোর অনুশোচনা সীমানা প্রতিষ্ঠা করা
  2. অ্যালগরিদম দক্ষতা: গণনামূলকভাবে দক্ষ অ্যালগরিদম ডিজাইন করা, বিদ্যমান পদ্ধতির সূচকীয় সময় জটিলতা এড়ানো
  3. ব্যবহারিক প্রয়োগ: সুপারিশ ব্যবস্থা ইত্যাদি ব্যবহারিক প্রয়োগের জন্য তাত্ত্বিক গ্যারান্টি এবং দক্ষ অ্যালগরিদম প্রদান করা

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

  1. তাত্ত্বিক ব্যবধান: নিম্ন সীমা Ω(d√T/K) এবং উপরের সীমা Õ(d√T) এর মধ্যে √K এর ব্যবধান রয়েছে
  2. গণনা জটিলতা: বিদ্যমান অ্যালগরিদমগুলিকে সমস্ত সম্ভাব্য পণ্য সমন্বয় গণনা করতে হয়, যা সূচকীয় সময় জটিলতার দিকে পরিচালিত করে
  3. প্যারামিটার নির্ভরতা: সমস্যা-সম্পর্কিত ধ্রুবক κ এর উপর খারাপ নির্ভরতা, যেখানে 1/κ = O(K²)

মূল অবদান

  1. কঠোর অনুশোচনা সীমানা প্রতিষ্ঠা:
    • একীভূত পুরস্কার: নিম্ন সীমা Ω(√(v₀K/(v₀+K))d√T), উপরের সীমা Õ(√(v₀K/(v₀+K))d√T)
    • অ-একীভূত পুরস্কার: নিম্ন সীমা Ω(d√T), উপরের সীমা Õ(d√T)
  2. দক্ষ অ্যালগরিদম OFU-MNL+ প্রস্তাব:
    • ধ্রুবক সময় জটিলতা O(1), রাউন্ড সংখ্যা t এর সাথে স্বাধীন
    • MNL ব্যান্ডিটে প্রথম অ্যালগরিদম যা K বৃদ্ধির সাথে অনুশোচনা হ্রাস প্রমাণ করে
  3. তাত্ত্বিক উদ্ভাবন:
    • বাহ্যিক বিকল্প আকর্ষণ প্যারামিটার v₀ এর অনুশোচনার উপর প্রভাব স্পষ্টভাবে প্রদর্শন করা
    • উদাহরণ-সম্পর্কিত মিনিম্যাক্স অনুশোচনা সীমানা প্রদান করা
  4. প্রযুক্তিগত উন্নতি:
    • উন্নত উপবৃত্তাকার সম্ভাব্যতা লেম্মা, K এর উপর নির্ভরতা দূর করা
    • ধ্রুবক স্ব-সামঞ্জস্যপূর্ণ ক্ষতি ফাংশন বিশ্লেষণ

পদ্ধতির বিস্তারিত বর্ণনা

কাজের সংজ্ঞা

ইনপুট:

  • প্রতিটি রাউন্ড t তে, N টি পণ্যের বৈশিষ্ট্য ভেক্টর x_ ∈ ℝᵈ পর্যবেক্ষণ করা
  • সর্বাধিক পণ্য সমন্বয় আকার K
  • বাহ্যিক বিকল্প আকর্ষণ প্যারামিটার v₀

আউটপুট:

  • পণ্য সমন্বয় S_t ⊆ {1,...,N}, |S_t| ≤ K নির্বাচন করা
  • ব্যবহারকারী নির্বাচন c_t ∈ S_t ∪ {0} পর্যবেক্ষণ করা, MNL মডেল অনুসরণ করে

লক্ষ্য: সংযুক্ত অনুশোচনা Reg_T(w*) = Σ_^T R_t(S_t, w) - R_t(S_t, w*) ন্যূনতম করা

মডেল স্থাপত্য

MNL নির্বাচন মডেল

ব্যবহারকারী পণ্য i ∈ S_t নির্বাচনের সম্ভাবনা:

p_t(i|S_t, w*) = exp(x_{ti}^T w*) / (v₀ + Σ_{j∈S_t} exp(x_{tj}^T w*))

বাহ্যিক বিকল্প (কোনো পণ্য নির্বাচন না করা) এর সম্ভাবনা:

p_t(0|S_t, w*) = v₀ / (v₀ + Σ_{j∈S_t} exp(x_{tj}^T w*))

OFU-MNL+ অ্যালগরিদম মূল উপাদান

  1. অনলাইন প্যারামিটার অনুমান:
    w_{t+1} = argmin_{w∈W} ⟨∇ℓ_t(w_t), w⟩ + (1/2η)||w - w_t||²_{H̃_t}

    যেখানে H̃_t = H_t + ηG_t(w_t), G_t(w) হল MNL ক্ষতির হেসিয়ান ম্যাট্রিক্স
  2. আস্থা সেট নির্মাণ:
    C_t(δ) = {w ∈ W : ||w_t - w||_{H_t} ≤ β_t(δ)}

    যেখানে β_t(δ) = O(√(d log t log K))
  3. আশাবাদী উপযোগিতা গণনা:
    α_{ti} = x_{ti}^T w_t + β_t(δ)||x_{ti}||_{H_t^{-1}}
  4. পণ্য সমন্বয় নির্বাচন:
    • একীভূত পুরস্কার: সর্বোচ্চ α_ সহ K টি পণ্য নির্বাচন করা
    • অ-একীভূত পুরস্কার: বহুপদী সময়ের সমন্বয় অপ্টিমাইজেশন সমস্যা সমাধান করা

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

  1. উন্নত স্ব-সামঞ্জস্যপূর্ণ বিশ্লেষণ: MNL ক্ষতি ফাংশন 3√2-স্ব-সামঞ্জস্যপূর্ণ বৈশিষ্ট্য প্রমাণ করা, যা পূর্ববর্তী √(6K) থেকে √K ফ্যাক্টর দ্বারা উন্নত
  2. K-স্বাধীন উপবৃত্তাকার সম্ভাব্যতা লেম্মা:
    Σ_{t=1}^T Σ_{i∈S_t} p_t(i|S_t,w_{t+1})p_t(0|S_t,w_{t+1})||x_{ti}||²_{H_t^{-1}} ≤ 2d log(1 + T/(dλ))
  3. কঠোর KL বিচ্যুতি সীমানা: আরও কঠোর KL বিচ্যুতি উপরের সীমানা প্রতিষ্ঠা করা, Chen ইত্যাদির ফলাফল উন্নত করা

পরীক্ষামূলক সেটআপ

ডেটাসেট

  • সংশ্লেষিত ডেটাসেট, প্যারামিটার w* ∈ ℝᵈ -1/√d, 1/√dᵈ থেকে সমানভাবে নমুনা করা
  • প্রসঙ্গ বৈশিষ্ট্য x_ বহুপরিবর্তনশীল গাউসিয়ান বিতরণ N(0_d, I_d) থেকে নমুনা করা এবং -1/√d, 1/√dᵈ এ ছাঁটাই করা
  • কনফিগারেশন: N=100, K∈{5,10,15}, d=5, T=3000

মূল্যায়ন মেট্রিক্স

  • সংযুক্ত অনুশোচনা: Σ_^T R_t(S_t, w) - R_t(S_t, w*)
  • প্রতি রাউন্ড গণনা সময়

তুলনা পদ্ধতি

  • UCB-MNL: আস্থা উপরের সীমানা-ভিত্তিক পদ্ধতি
  • TS-MNL: Thompson নমুনা-ভিত্তিক পদ্ধতি

বাস্তবায়ন বিবরণ

  • নিয়মিতকরণ প্যারামিটার λ = 84√(2d)η
  • ধাপ আকার η = (1/2)log(K+1) + 2
  • আস্থা ব্যাসার্ধ β_t(δ) = O(√(d log t log K))

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

  1. অনুশোচনা কর্মক্ষমতা:
    • একীভূত পুরস্কারে, K বৃদ্ধির সাথে সমস্ত অ্যালগরিদমের সংযুক্ত অনুশোচনা হ্রাস পায়
    • অ-একীভূত পুরস্কারে, K এর বৃদ্ধি অনুশোচনা উন্নতির গ্যারান্টি দিতে পারে না
    • OFU-MNL+ সমস্ত সেটিংয়ে বেসলাইন পদ্ধতির চেয়ে উল্লেখযোগ্যভাবে ভাল
  2. গণনা দক্ষতা:
    • OFU-MNL+ ধ্রুবক গণনা খরচ বজায় রাখে, রাউন্ড সংখ্যা t এর সাথে স্বাধীন
    • বেসলাইন পদ্ধতির গণনা সময় t এর সাথে রৈখিকভাবে বৃদ্ধি পায়
    • একীভূত পুরস্কার সেটিংয়ের চলমান সময় অ-একীভূত সেটিংয়ের প্রায় 1/10

তাত্ত্বিক যাচাইকরণ

পরীক্ষামূলক ফলাফল তাত্ত্বিক বিশ্লেষণ যাচাই করে:

  • v₀ = Θ(1) এর সময়, অনুশোচনা K এর সাথে হ্রাস পায়
  • v₀ = Θ(K) এর সময়, অনুশোচনা K এর সাথে স্বাধীন
  • অ-একীভূত পুরস্কারে অনুশোচনা K এর সাথে স্বাধীন

সম্পর্কিত কাজ

MNL ব্যান্ডিট গবেষণা

  1. অ-প্রসঙ্গ সেটিং: Agrawal ইত্যাদি Ω(√(NT/K)) নিম্ন সীমানা প্রতিষ্ঠা করেছেন
  2. প্রসঙ্গ সেটিং: Chen ইত্যাদি Ω(d√T/K) নিম্ন সীমানা প্রস্তাব করেছেন, কিন্তু অ্যালগরিদম জটিলতা সূচকীয়
  3. গণনা দক্ষতা: Oh এবং Iyengar বহুপদী সময় অ্যালগরিদম প্রস্তাব করেছেন, কিন্তু অনুশোচনা সীমানা 1/κ নির্ভরতা রয়েছে

লজিস্টিক ব্যান্ডিট

  • বাইনারি লজিস্টিক ব্যান্ডিটের জন্য সর্বোত্তম অ্যালগরিদম ইতিমধ্যে রয়েছে
  • MNL ব্যান্ডিট হল লজিস্টিক ব্যান্ডিটের বহু-নির্বাচন সম্প্রসারণ

সমন্বয় ব্যান্ডিট

  • শীর্ষ-k সমন্বয় ব্যান্ডিটের সাথে সম্পর্কিত কিন্তু পুরস্কার কাঠামো ভিন্ন
  • MNL মডেলে একক পণ্য পুরস্কার সম্পূর্ণ সমন্বয়ের উপর নির্ভর করে

উপসংহার এবং আলোচনা

প্রধান উপসংহার

  1. তাত্ত্বিক সম্পূর্ণতা: MNL ব্যান্ডিটে প্রথমবারের মতো মিনিম্যাক্স সর্বোত্তমতা অর্জন করা
  2. অ্যালগরিদম দক্ষতা: প্রথম ধ্রুবক সময় জটিলতার সর্বোত্তম অ্যালগরিদম প্রস্তাব করা
  3. প্যারামিটার প্রভাব: v₀ এবং K এর অনুশোচনার উপর প্রভাব স্পষ্টভাবে পরিমাপ করা

সীমাবদ্ধতা

  1. সীমাবদ্ধ অনুমান: প্যারামিটার ||w*||₂ ≤ 1 প্রয়োজন, শিথিল করার পরে অনুশোচনা সীমানা অতিরিক্ত সূচকীয় ফ্যাক্টর থাকবে
  2. উদাহরণ-সম্পর্কিত সীমানা: অ-একীভূত পুরস্কারে উদাহরণ-সম্পর্কিত সীমানা প্রতিষ্ঠা করতে পারা যায় না
  3. ধ্রুবক ফ্যাক্টর: তাত্ত্বিক সীমানায় লগারিদম ফ্যাক্টর ব্যবহারিকভাবে বড় হতে পারে

ভবিষ্যত দিকনির্দেশনা

  1. অনুমান শিথিলকরণ: অসীম প্যারামিটার ক্ষেত্রে সর্বোত্তম অ্যালগরিদম গবেষণা করা
  2. উদাহরণ অভিযোজন: অ-একীভূত পুরস্কারের জন্য উদাহরণ-সম্পর্কিত সীমানা প্রতিষ্ঠা করা
  3. ব্যবহারিক প্রয়োগ: প্রকৃত সুপারিশ ব্যবস্থায় অ্যালগরিদম কর্মক্ষমতা যাচাই করা

গভীর মূল্যায়ন

শক্তি

  1. উল্লেখযোগ্য তাত্ত্বিক অবদান: MNL ব্যান্ডিটে প্রথমবারের মতো সর্বোত্তমতা সমস্যা সমাধান করা, গুরুত্বপূর্ণ তাত্ত্বিক ফাঁক পূরণ করা
  2. উল্লেখযোগ্য প্রযুক্তিগত উদ্ভাবন: উন্নত স্ব-সামঞ্জস্যপূর্ণ বিশ্লেষণ এবং উপবৃত্তাকার সম্ভাব্যতা লেম্মা স্বাধীন মূল্য রাখে
  3. উচ্চ ব্যবহারিক মূল্য: ধ্রুবক সময় জটিলতা অ্যালগরিদমকে ব্যবহারিক প্রয়োগের জন্য উপযুক্ত করে তোলে
  4. ব্যাপক বিশ্লেষণ: একীভূত এবং অ-একীভূত পুরস্কার উভয়ই বিবেচনা করা, সম্পূর্ণ তাত্ত্বিক চিত্র প্রদান করা

অপূর্ণতা

  1. অনুমান সীমাবদ্ধতা: সীমাবদ্ধ প্যারামিটার অনুমান ব্যবহারিকভাবে অত্যন্ত কঠোর হতে পারে
  2. ধ্রুবক অপ্টিমাইজেশন: তাত্ত্বিক সীমানায় ধ্রুবক ফ্যাক্টর যথেষ্ট কঠোর নাও হতে পারে
  3. পরীক্ষার স্কেল: পরীক্ষা শুধুমাত্র সংশ্লেষিত ডেটায় পরিচালিত, প্রকৃত ডেটা যাচাইকরণের অভাব

প্রভাব

  1. একাডেমিক মূল্য: MNL ব্যান্ডিট তত্ত্বের জন্য দৃঢ় ভিত্তি স্থাপন করা, উচ্চ উদ্ধৃতি প্রত্যাশিত
  2. ব্যবহারিক মূল্য: সুপারিশ ব্যবস্থা, অনলাইন বিজ্ঞাপন ইত্যাদি প্রয়োগের জন্য তাত্ত্বিক নির্দেশনা প্রদান করা
  3. পদ্ধতিগত অবদান: প্রযুক্তিগত পদ্ধতি অন্যান্য সম্পর্কিত সমস্যায় প্রসারিত করা যায়

প্রযোজ্য পরিস্থিতি

  1. সুপারিশ ব্যবস্থা: অনলাইন পণ্য সুপারিশ, বিষয়বস্তু সুপারিশ
  2. অনলাইন বিজ্ঞাপন: বিজ্ঞাপন সমন্বয় নির্বাচন এবং স্থাপনা অপ্টিমাইজেশন
  3. ই-কমার্স: পণ্য প্রদর্শন এবং প্রচার কৌশল অপ্টিমাইজেশন

তথ্যসূত্র

পেপারটি 52টি সম্পর্কিত সাহিত্য উদ্ধৃত করে, প্রধানত অন্তর্ভুক্ত:

  • MNL ব্যান্ডিট মৌলিক কাজ: Agrawal et al., Chen et al.
  • লজিস্টিক ব্যান্ডিট তত্ত্ব: Faury et al., Abeille et al.
  • অনলাইন শিক্ষার ভিত্তি: Lattimore & Szepesvári
  • স্ব-সামঞ্জস্যপূর্ণ ফাংশন তত্ত্ব: Tran-Dinh et al.

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ মানের পেপার যার তাত্ত্বিক অবদান উল্লেখযোগ্য, যা MNL ব্যান্ডিট ক্ষেত্রের মূল উন্মুক্ত সমস্যা সফলভাবে সমাধান করে, উল্লেখযোগ্য প্রযুক্তিগত উদ্ভাবন রয়েছে, পরীক্ষামূলক যাচাইকরণ পর্যাপ্ত, এবং সম্পর্কিত ক্ষেত্রে গুরুত্বপূর্ণ প্রচারমূলক প্রভাব রয়েছে।