2025-11-20T13:28:14.804433

Towards Blackwell Optimality: Bellman Optimality Is All You Can Get

Boone, Tuynman
Although average gain optimality is a commonly adopted performance measure in Markov Decision Processes (MDPs), it is often too asymptotic. Further incorporating measures of immediate losses leads to the hierarchy of bias optimalities, all the way up to Blackwell optimality. In this paper, we investigate the problem of identifying policies of such optimality orders. To that end, for each order, we construct a learning algorithm with vanishing probability of error. Furthermore, we characterize the class of MDPs for which identification algorithms can stop in finite time. That class corresponds to the MDPs with a unique Bellman optimal policy, and does not depend on the optimality order considered. Lastly, we provide a tractable stopping rule that when coupled to our learning algorithm triggers in finite time whenever it is possible to do so.
academic

ব্ল্যাকওয়েল সর্বোত্তমতার দিকে: বেলম্যান সর্বোত্তমতা আপনি যা পেতে পারেন তাই

মৌলিক তথ্য

  • পেপার আইডি: 2510.13476
  • শিরোনাম: Towards Blackwell Optimality: Bellman Optimality Is All You Can Get
  • লেখক: Victor Boone (Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG & IRIT, Université de Toulouse), Adrienne Tuynman (Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL)
  • শ্রেণীবিভাগ: cs.LG (মেশিন লার্নিং)
  • প্রকাশনার সময়: ২০২৫ সালের অক্টোবর ১৫ তারিখ (arXiv প্রি-প্রিন্ট)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2510.13476v1

সারসংক্ষেপ

যদিও গড় লাভ সর্বোত্তমতা মার্কোভ সিদ্ধান্ত প্রক্রিয়া (MDPs) এ একটি সাধারণ কর্মক্ষমতা পরিমাপ, এটি প্রায়শই অত্যন্ত অ্যাসিম্পটোটিক। তাৎক্ষণিক ক্ষতির পরিমাপের সাথে আরও সংমিশ্রণ পক্ষপাত সর্বোত্তমতার একটি শ্রেণিবিন্যাস দিকে পরিচালিত করে, ব্ল্যাকওয়েল সর্বোত্তমতা পর্যন্ত। এই পেপারটি এই ধরনের সর্বোত্তমতা ক্রম নীতি সনাক্ত করার সমস্যা অধ্যয়ন করে। এই উদ্দেশ্যে, প্রতিটি ক্রমের জন্য, আমরা অদৃশ্য ত্রুটি সম্ভাবনা সহ একটি শেখার অ্যালগরিদম তৈরি করি। অধিকন্তু, আমরা সনাক্তকরণ অ্যালগরিদম সীমিত সময়ে থামতে পারে এমন MDP শ্রেণীগুলি চিহ্নিত করি। এই শ্রেণীটি অনন্য বেলম্যান সর্বোত্তম নীতি সহ MDPs এর সাথে সামঞ্জস্যপূর্ণ এবং বিবেচিত সর্বোত্তমতা ক্রমের উপর নির্ভর করে না। অবশেষে, আমরা একটি সহজবোধ্য থামার নিয়ম প্রদান করি যা আমাদের শেখার অ্যালগরিদমের সাথে যুক্ত হলে, যখনই সম্ভব সীমিত সময়ে ট্রিগার হয়।

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

সমস্যা সংজ্ঞা

এই পেপারের মূল গবেষণা সমস্যা হল মার্কোভ সিদ্ধান্ত প্রক্রিয়ায় উচ্চ-ক্রম সর্বোত্তম নীতি শেখার সনাক্তকরণযোগ্যতা সমস্যা। নির্দিষ্টভাবে:

  1. ঐতিহ্যবাহী গড় লাভ সর্বোত্তমতার সীমাবদ্ধতা: MDP-তে, ঐতিহ্যবাহী গড় লাভ সর্বোত্তমতা শুধুমাত্র দীর্ঘমেয়াদী অ্যাসিম্পটোটিক কর্মক্ষমতার উপর দৃষ্টি নিবদ্ধ করে, স্বল্পমেয়াদী তাৎক্ষণিক পুরস্কারের গুরুত্ব উপেক্ষা করে।
  2. উচ্চ-ক্রম সর্বোত্তমতার শ্রেণিবিন্যাস: লাভ সর্বোত্তমতা থেকে পক্ষপাত সর্বোত্তমতা পর্যন্ত, এবং ব্ল্যাকওয়েল সর্বোত্তমতা পর্যন্ত, একটি সম্পূর্ণ সর্বোত্তমতা শ্রেণিবিন্যাস গঠন করে, প্রতিটি স্তর আরও সূক্ষ্ম কর্মক্ষমতা পার্থক্য বিবেচনা করে।
  3. শেখার চ্যালেঞ্জ: পেপারটি একটি সহজ কিন্তু গভীর উদাহরণের মাধ্যমে (চিত্র ১) প্রদর্শন করে যে এমনকি সবচেয়ে সহজ পরিস্থিতিতেও, উচ্চ-ক্রম সর্বোত্তম নীতি শেখা মৌলিক কঠিনতার সম্মুখীন হয়।

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

পেপারের মূল প্রেরণা একটি গুরুত্বপূর্ণ পর্যবেক্ষণ থেকে উদ্ভূত: এমনকি শুধুমাত্র একটি অজানা প্যারামিটার সহ সহজ MDP-তেও, উচ্চ-ক্রম সর্বোত্তম নীতি শেখা অসম্ভব হতে পারে। এই আপাতদৃষ্টিতে বিরোধপূর্ণ ঘটনা উচ্চ-ক্রম সর্বোত্তমতা শেখার অন্তর্নিহিত কঠিনতা প্রকাশ করে।

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

  1. মান শেখার পদ্ধতি ব্যর্থ: ঐতিহ্যবাহী অভিজ্ঞতামূলক সর্বোত্তম নীতি নির্বাচন উচ্চ-ক্রম সর্বোত্তমতার অধীনে আর প্রযোজ্য নয়
  2. পরিসংখ্যানগত পরীক্ষার সীমাবদ্ধতা: প্যারামিটারের সঠিক মান নির্ধারণ করা যায় না (যেমন θ=0)
  3. অসংযোগ সমস্যা: প্যারামিটার স্থানে সর্বোত্তম নীতি সেটের অসংযোগ শেখার কঠিনতা সৃষ্টি করে

মূল অবদান

  1. সামঞ্জস্যপূর্ণ অ্যালগরিদম HOPE তৈরি করা: প্রতিটি সর্বোত্তমতা ক্রম n≥-1 এর জন্য, Higher Order Policy iteration Epsilonized (HOPE) অ্যালগরিদম প্রস্তাব করা হয়েছে, যা অদৃশ্য ত্রুটি সম্ভাবনা সহ।
  2. অ-অবক্ষয়িত MDP শ্রেণীর সম্পূর্ণ চিহ্নিতকরণ: প্রমাণ করা হয়েছে যে একটি MDP অ-অবক্ষয়িত (অর্থাৎ সনাক্তকরণ অ্যালগরিদম সীমিত সময়ে থামতে পারে) যদি এবং শুধুমাত্র যদি এটির অনন্য বেলম্যান সর্বোত্তম নীতি থাকে।
  3. অবক্ষয়তা সংহতকরণ উপপাদ্য: প্রমাণ করা হয়েছে যে সমস্ত সর্বোত্তমতা ক্রমের (লাভ সর্বোত্তম থেকে ব্ল্যাকওয়েল সর্বোত্তম পর্যন্ত) অ-অবক্ষয়িত MDP শ্রেণী সম্পূর্ণভাবে একই, যা একটি আশ্চর্যজনক ফলাফল।
  4. গণনাযোগ্য থামার নিয়ম প্রদান করা: একটি সহজবোধ্য থামার নিয়ম দেওয়া হয়েছে যা HOPE অ্যালগরিদমকে সম্ভব হলে সীমিত সময়ে থামতে সক্ষম করে।

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

কাজের সংজ্ঞা

ইনপুট: অজানা যোগাযোগ MDP M = (Z, ν, p), যেখানে Z হল অবস্থা-কর্ম জোড়ার স্থান, ν হল পুরস্কার ফাংশন, p হল রূপান্তর কার্নেল আউটপুট: n-ক্রম সর্বোত্তম নীতি π ∈ Π*_n(M) লক্ষ্য: সনাক্তকরণ অ্যালগরিদম তৈরি করা যাতে সুপারিশকৃত নীতির ত্রুটি সম্ভাবনা 0 এর দিকে প্রবণ হয়

মূল অ্যালগরিদম আর্কিটেকচার

HOPE অ্যালগরিদম (অ্যালগরিদম ১)

ইনপুট: পছন্দসই সর্বোত্তমতা ক্রম n ≥ -1
শুরু করা: t ← 0
লুপ:
    1. অভিজ্ঞতামূলক MDP M̂_t তৈরি করুন
    2. সেট করুন ε ← t^(-1/4)
    3. গণনা করুন ∏_s A_n(s) ← HOPI_{n,ε}(M̂_t)
    4. ∏_s A_n(s) এ যেকোনো নীতি সুপারিশ করুন
    5. সমানভাবে কর্ম নমুনা করুন, পুরস্কার এবং পরবর্তী অবস্থা পর্যবেক্ষণ করুন
    6. t ← t + 1

HOPI অ্যালগরিদমের মূল ধারণা

HOPI হল উচ্চ-ক্রম নীতি পুনরাবৃত্তির "এপসিলন-করা" সংস্করণ, মূল উদ্ভাবন হল:

  1. নরম argmax অপারেশন: নির্ভুল বেলম্যান সমীকরণ সীমাবদ্ধতা Δ^π_m(s,a) = 0 কে Δ^π_m(s,a) ≤ ε এ শিথিল করা
  2. দুই-পর্যায়ের নীতি উন্নতি:
    • প্রথম পর্যায়: ইতিমধ্যে পরিচিত m-1 ক্রম সর্বোত্তম কর্মের মধ্যে m+1 ক্রম উন্নতি খুঁজে পাওয়া
    • দ্বিতীয় পর্যায়: m+2 ক্রম সর্বোত্তমতায় আরও পরিমার্জন করা
  3. ক্রমবর্ধমান নির্ভুলতা নিয়ন্ত্রণ: ε_t = t^(-1/4) নির্বাচন করা অ্যালগরিদমের সামঞ্জস্য নিশ্চিত করে

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

১. শব্দের অধীনে নীতি পুনরাবৃত্তি

ঐতিহ্যবাহী নীতি পুনরাবৃত্তি বেলম্যান সমীকরণ সঠিকভাবে সন্তুষ্ট করার প্রয়োজন, কিন্তু শেখার পরিবেশে এটি অসম্ভব। HOPI একটি শিথিলকরণ প্যারামিটার ε প্রবর্তন করে, যা অ্যালগরিদমকে শব্দ পরিবেশে সঠিকভাবে কাজ করতে সক্ষম করে।

২. ভাঙা প্রযুক্তি (Shattering)

প্রস্তাব ৫: যেকোনো একক-শৃঙ্খল বেলম্যান সর্বোত্তম নীতি π এবং নির্ভুলতা ε > 0 এর জন্য, M' ∈ M বিদ্যমান যাতে d_∞(M,M') < ε এবং π হল M' এর অনন্য লাভ সর্বোত্তম নীতি।

এই প্রযুক্তি দুটি ধাপে বাস্তবায়িত হয়:

  • প্রথমে অ-সর্বোত্তম কর্মকে শাস্তি দিয়ে π কে অনন্য বেলম্যান সর্বোত্তম নীতি করা
  • তারপর ট্রাভার্সাল রূপান্তরের মাধ্যমে π কে অনন্য লাভ সর্বোত্তম নীতি করা

৩. থামার নিয়ম ডিজাইন

থ্রেশহোল্ড ফাংশন সংজ্ঞায়িত করা:

β(M) := min{d_min(Δ*)/((1+4α)(2+sp(b*))), 1/α}

যেখানে α হল সর্বোচ্চ পৌঁছানোর সময়, এই থ্রেশহোল্ড প্রতিবেশী ব্যাসার্ধের নির্ভুলতার সঠিক পরিমাপ প্রদান করে।

তাত্ত্বিক ফলাফল

প্রধান উপপাদ্য

উপপাদ্য ১ (সামঞ্জস্য)

সমস্ত n ≥ -1 এর জন্য, HOPE(n) অ্যালগরিদম Π*_n এর জন্য সামঞ্জস্যপূর্ণ।

উপপাদ্য ২ (অ-অবক্ষয়তা চিহ্নিতকরণ)

n ≥ -1 সেট করুন। MDP M Π*_n(M) এর সাপেক্ষে অ-অবক্ষয়িত যদি এবং শুধুমাত্র যদি M এর অনন্য বেলম্যান সর্বোত্তম নীতি থাকে।

অনুসিদ্ধান্ত ৩ (অবক্ষয়তা সংহতকরণ)

Π_{-1}, Π0, Π_1, ..., Π∞ এর সাপেক্ষে অবক্ষয়িত মডেল সেট সম্পূর্ণভাবে একই।

প্রমাণ কৌশল

অ-অবক্ষয়তার প্রয়োজনীয়তা (উপপাদ্য ৪)

যদি M অ-অবক্ষয়িত হয়, তবে একটি নীতি π ∈ Π*(M) বিদ্যমান যা M এর প্রতিবেশে সর্বোত্তম থাকে। প্রমাণ অ্যালগরিদম সিদ্ধান্তের ধারাবাহিকতা ব্যবহার করে।

যথেষ্টতা (উপপাদ্য ১০-১১)

স্পষ্ট থামার নিয়ম এবং আস্থা ব্যবধান তৈরি করে, প্রমাণ করা হয় যে অনন্য বেলম্যান সর্বোত্তম নীতি সহ MDPs সত্যিই অ-অবক্ষয়িত।

পরীক্ষামূলক সেটআপ এবং ফলাফল

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

পেপারটি প্রধানত একটি তাত্ত্বিক কাজ, কঠোর গাণিতিক প্রমাণের মাধ্যমে সমস্ত প্রধান ফলাফল যাচাই করে। মূল যাচাইকরণ অন্তর্ভুক্ত:

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

জটিলতা বিশ্লেষণ

  • সময় জটিলতা: বেলম্যান সর্বোত্তম নীতির অনন্যতা নির্ধারণের সময় জটিলতা O(|Z| + |S|^4)
  • নমুনা জটিলতা: যদিও পেপারটি নির্ভুল নমুনা জটিলতা সীমানা প্রদান করে না, তবে প্রমাণ করে যে অ-অবক্ষয়িত পরিস্থিতিতে অ্যালগরিদম অবশ্যই সংগ্রহ করে

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

সর্বোত্তম বাহু সনাক্তকরণ

বহু-বাহু ডাকাতি সমস্যায় সর্বোত্তম বাহু সনাক্তকরণ সমস্যার সাথে সম্পর্কিত, কিন্তু MDP সেটিংয়ে অবস্থা নির্ভরতা সমস্যাটিকে আরও জটিল করে তোলে।

গড় পুরস্কার শক্তিশালী শেখা

সম্প্রতি (ε,δ)-PAC সেটিংয়ে লাভ সর্বোত্তম নীতি সনাক্তকরণে কাজ, কিন্তু এই কাজগুলি প্রধানত আনুমানিক সর্বোত্তমতার উপর দৃষ্টি নিবদ্ধ করে যা সঠিক সর্বোত্তমতা নয়।

ব্ল্যাকওয়েল সর্বোত্তমতা গণনা

Grand-Clément এবং Petrik (2023) এবং অন্যরা ছাড় ফ্যাক্টরের ঐতিহাসিক সংজ্ঞার উপর ভিত্তি করে ব্ল্যাকওয়েল সর্বোত্তম নীতির গণনা জটিলতা অধ্যয়ন করেছেন।

নির্ধারক MDP-তে সম্পর্কিত ফলাফল

Boone এবং Gaujal (2023) নির্ধারক রূপান্তর MDP-তে ব্ল্যাকওয়েল সর্বোত্তম নীতির শেখাযোগ্যতা অধ্যয়ন করেছেন, এই পেপারটি এটিকে স্টোকাস্টিক পরিস্থিতিতে সাধারণীকরণ করে।

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

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

  1. বেলম্যান সর্বোত্তমতা মৌলিক সীমাবদ্ধতা: সমস্ত উচ্চ-ক্রম সর্বোত্তমতার শেখাযোগ্যতা বেলম্যান সর্বোত্তমতার অনন্যতায় হ্রাস পায়
  2. অবক্ষয়তার সর্বজনীনতা: বিভিন্ন সর্বোত্তমতা ক্রমের অবক্ষয়িত MDP শ্রেণী সম্পূর্ণভাবে একই
  3. অ্যালগরিদমের অস্তিত্ব: চ্যালেঞ্জ সত্ত্বেও, সামঞ্জস্যপূর্ণ অ্যালগরিদম সত্যিই বিদ্যমান

সীমাবদ্ধতা

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

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

  1. PAC ফ্রেমওয়ার্ক সম্প্রসারণ: আনুমানিক সর্বোত্তম নীতির শেখা অধ্যয়ন করা
  2. নমুনা জটিলতা বিশ্লেষণ: নির্ভুল নমুনা জটিলতা সীমানা স্থাপন করা
  3. অ্যালগরিদম অপ্টিমাইজেশন: HOPE অ্যালগরিদমের ব্যবহারিক কর্মক্ষমতা উন্নত করা

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

শক্তি

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

অসুবিধা

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

প্রভাব

  1. তাত্ত্বিক অবদান: শক্তিশালী শেখার তত্ত্বে গুরুত্বপূর্ণ নেতিবাচক ফলাফল প্রদান করে
  2. পদ্ধতি অনুপ্রেরণা: ভাঙা প্রযুক্তি অন্যান্য সমস্যায় প্রয়োগ হতে পারে
  3. গবেষণা দিকনির্দেশনা: পরবর্তী গবেষণার জন্য PAC সেটিংয়ের গুরুত্ব নির্দেশ করে

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

  1. তাত্ত্বিক গবেষণা: শক্তিশালী শেখার তাত্ত্বিক গবেষণার জন্য গুরুত্বপূর্ণ রেফারেন্স প্রদান করে
  2. অ্যালগরিদম ডিজাইন: ব্যবহারিক নীতি শেখার অ্যালগরিদম ডিজাইনের জন্য তাত্ত্বিক নির্দেশনা প্রদান করে
  3. সমস্যা বিশ্লেষণ: MDP কাঠামো শেখার কঠিনতায় প্রভাব বুঝতে সাহায্য করে

তথ্যসূত্র

পেপারটি শক্তিশালী শেখা এবং মার্কোভ সিদ্ধান্ত প্রক্রিয়া ক্ষেত্রের গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যার মধ্যে রয়েছে:

  • Puterman (1994): মার্কোভ সিদ্ধান্ত প্রক্রিয়ার ক্লাসিক পাঠ্যপুস্তক
  • Blackwell (1962): ব্ল্যাকওয়েল সর্বোত্তমতার মূল সংজ্ঞা
  • Kaufmann et al. (2016): সর্বোত্তম বাহু সনাক্তকরণের জটিলতা তত্ত্ব
  • Boone and Gaujal (2023): নির্ধারক MDP-তে ব্ল্যাকওয়েল সর্বোত্তমতার শেখাযোগ্যতা

এই পেপারটি কঠোর তাত্ত্বিক বিশ্লেষণের মাধ্যমে শক্তিশালী শেখায় একটি মৌলিক এবং গভীর ঘটনা প্রকাশ করে: উচ্চ-ক্রম সর্বোত্তমতার শেখার কঠিনতা সম্পূর্ণভাবে বেলম্যান সর্বোত্তমতার কাঠামো দ্বারা নির্ধারিত হয়। এই ফলাফল শুধুমাত্র গুরুত্বপূর্ণ তাত্ত্বিক তাৎপর্য নয়, বরং ব্যবহারিক অ্যালগরিদম ডিজাইনের জন্য গুরুত্বপূর্ণ নির্দেশনা প্রদান করে।