মার্কভ সিদ্ধান্ত প্রক্রিয়ায় মূল্য-সংরক্ষণকারী অবস্থা সমন্বয়ের জন্য সমরূপী ম্যাপিং

মৌলিক তথ্য

• পত্র আইডি: 2510.09965
• শিরোনাম: মার্কভ সিদ্ধান্ত প্রক্রিয়ায় মূল্য-সংরক্ষণকারী অবস্থা সমন্বয়ের জন্য সমরূপী ম্যাপিং
• লেখক: শুও ঝাও, ইয়ংকিয়াং লি, ইউ ফেং, ঝংশেং হাউ, ইউয়ানজিং ফেং
• শ্রেণীবিভাগ: cs.LG cs.AI stat.ML
• প্রকাশনা সময়: অক্টোবর ১৪, ২০২৫ (arXiv প্রাক-প্রিন্ট)
• পত্র লিঙ্ক: https://arxiv.org/abs/2510.09965

সারসংক্ষেপ

এই পত্রটি মার্কভ সিদ্ধান্ত প্রক্রিয়া (MDP) তে অবস্থা সমন্বয় সমস্যার জন্য সমরূপী ম্যাপিং-ভিত্তিক একটি বিমূর্ত কাঠামো প্রস্তাব করে। এই কাঠামোটি দুটি মার্কভ শৃঙ্খলের মধ্যে মূল্য ফাংশনের রৈখিক সম্পর্ক স্থাপনের মাধ্যমে সমরূপতা সংজ্ঞায়িত করে, যা গণনা জটিলতা হ্রাস করার সাথে সাথে সর্বোত্তম নীতির সমতুল্যতা বজায় রাখে। পত্রটি HPG এবং EBHPG দুটি অ্যালগরিদম প্রস্তাব করে, যা যথাক্রমে পর্যাপ্ত শর্ত পূরণ এবং অপূর্ণতার সময় তাত্ত্বিক গ্যারান্টি প্রদান করে এবং পরীক্ষামূলক ফলাফলের মাধ্যমে তাত্ত্বিক ফলাফলের কার্যকারিতা যাচাই করে।

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

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

জটিল বাস্তব সমস্যায় MDP এর ব্যাপক প্রয়োগের সাথে, বৃহৎ-স্কেল অবস্থা স্থানের কারণে গণনা জটিলতার সমস্যা ক্রমবর্ধমান হয়ে উঠছে। অবস্থা সমন্বয় একটি মূল কৌশল হিসাবে কাজ করে, যা অবস্থা স্থান সংকুচিত করার মাধ্যমে গণনা খরচ হ্রাস করার লক্ষ্য রাখে, তবে মূল চ্যালেঞ্জ হল বিমূর্ত স্থানে অপ্টিমাইজ করা নীতি মূল MDP তে সর্বোত্তম থাকে তা নিশ্চিত করা।

গবেষণার গুরুত্ব

১. গণনা দক্ষতা: বৃহৎ-স্কেল MDP এর সমাধান জটিলতা অবস্থা স্থানের সাথে সূচকীয়ভাবে বৃদ্ধি পায় २. ব্যবহারিক প্রয়োগ: বহু-এজেন্ট সমন্বয়, ভিজ্যুয়াল প্রতিনিধিত্ব শেখা, অপারেশনাল সিস্টেম ইত্যাদি ক্ষেত্রের জরুরি চাহিদা ३. তাত্ত্বিক তাৎপর্য: সর্বোত্তম নীতি সমতুল্যতার জন্য পদ্ধতিগত তাত্ত্বিক বিশ্লেষণ সরঞ্জামের অভাব

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

१. বৈশিষ্ট্য-ভিত্তিক পদ্ধতি: উল্লেখযোগ্য গণনা সম্পদ প্রয়োজন, বিশেষত উচ্চ-মাত্রিক সেটিংসে २. মূল্য-ভিত্তিক সমন্বয়: যদিও মূল্য ফাংশন ত্রুটি ন্যূনতমকরণে মনোনিবেশ করে, তবে সর্বোত্তম নীতি সমতুল্যতার জন্য তাত্ত্বিক সরঞ্জামের অভাব রয়েছে ३. সমরূপী MDP তত্ত্ব: বিমূর্ত MDP কে মূল MDP এর পুরস্কার এবং রূপান্তর গতিশীলতা সম্পূর্ণভাবে সংরক্ষণ করার প্রয়োজন, শর্তগুলি অত্যন্ত কঠোর

মূল অবদান

१. সমরূপী মার্কভ শৃঙ্খল কাঠামো প্রস্তাব: ঐতিহ্যবাহী সমরূপী MDP এর চেয়ে আরও শিথিল তাত্ত্বিক কাঠামো স্থাপন করা হয়েছে, যা শুধুমাত্র মূল্য ফাংশনের মধ্যে রৈখিক সম্পর্ক প্রয়োজন २. সর্বোত্তম নীতি সমতুল্যতার পর্যাপ্ত শর্ত স্থাপন: প্রমাণ করা হয়েছে যে যখন এনকোডিং ম্যাট্রিক্সের সারি স্থান মৌলিক রূপান্তর ভেক্টর বিস্তৃত স্থান ধারণ করে, তখন সর্বোত্তম নীতি সমতুল্যতা সত্য হয় ३. HPG অ্যালগরিদম বিকাশ: পর্যাপ্ত শর্ত পূরণের সময় সর্বোত্তম নীতি সমতুল্যতা নিশ্চিত করার নীতি গ্রেডিয়েন্ট অ্যালগরিদম ४. EBHPG অ্যালগরিদম ডিজাইন: পর্যাপ্ত শর্ত অপূর্ণ পরিস্থিতি পরিচালনা করার জন্য সম্প্রসারিত অ্যালগরিদম, কর্মক্ষমতা নিম্ন সীমা গ্যারান্টি প্রদান করে ५. ত্রুটি সীমা বিশ্লেষণ প্রদান: আনুমানিক ত্রুটি উপরের সীমা এবং উদ্দেশ্য ফাংশন কর্মক্ষমতা নিম্ন সীমা উদ্ভূত করা হয়েছে

পদ্ধতি বিবরণ

কাজের সংজ্ঞা

অসীম সময়কাল MDP $M_S = (S,A,P_{SA},\gamma,r)$ দেওয়া হয়েছে, লক্ষ্য হল এনকোডিং ম্যাট্রিক্স $P_\nu$ এবং বিমূর্ত অবস্থা স্থান $U$ খুঁজে পাওয়া, যাতে বিমূর্ত স্থানে অপ্টিমাইজ করা নীতি মূল MDP তে সর্বোত্তম থাকে।

মূল তাত্ত্বিক কাঠামো

সমরূপী মার্কভ শৃঙ্খল সংজ্ঞা

সংজ্ঞা ১: নীতি $\pi$ দ্বারা প্ররোচিত মৌলিক মার্কভ শৃঙ্খল $M^\pi_S$ এবং বিমূর্ত মার্কভ শৃঙ্খল $M^\mu_U$ দেওয়া হয়েছে, যদি নিম্নলিখিত শর্তগুলি সন্তুষ্ট হয় তবে $M^\mu_U$ কে $M^\pi_S$ এর সমরূপী মার্কভ শৃঙ্খল বলা হয়:

$P^\mu_U P_\nu = P_\nu P^\pi_S$$R^{\pi,\nu}_U = P_\nu R^\pi_S$

যেখানে $P_\nu \in \mathbb{R}^{|U| \times |S|}$ এনকোডিং ম্যাট্রিক্স।

মূল্য ফাংশন রৈখিক সম্পর্ক

উপপাদ্য ১: যদি $M^\mu_U$ হল $M^\pi_S$ এর সমরূপী মার্কভ শৃঙ্খল, তবে তাদের মূল্য ফাংশনগুলি রৈখিক সম্পর্ক সন্তুষ্ট করে: $V^\mu_U = P_\nu V^\pi_S$

সমরূপী ম্যাপিং অস্তিত্ব শর্ত

উপপাদ্য ३: মৌলিক MDP $M_S$ এবং এনকোডিং ম্যাট্রিক্স $P_\nu$ দেওয়া হয়েছে, সমরূপী ম্যাপিং $f_\nu: \Pi_S \to \Pi_U$ বিদ্যমান থাকে যদি এবং শুধুমাত্র যদি $P_\nu$ এর সারি স্থান $\text{span}(F)$ ধারণ করে, যেখানে $F$ সমস্ত মৌলিক রূপান্তর ভেক্টরের সর্বাধিক রৈখিকভাবে স্বাধীন উপসেট।

অ্যালগরিদম ডিজাইন

HPG অ্যালগরিদম (অ্যালগরিদম १)

যখন পর্যাপ্ত শর্ত সন্তুষ্ট হয়: १. $P_\nu$ এর মুর-পেনরোজ সিউডোইনভার্স $P_\nu^\dagger$ গণনা করুন २. $C^{\pi_{\theta_t}} = P^{\pi_{\theta_t}}_S P_\nu^\dagger$ এর মাধ্যমে বিমূর্ত রূপান্তর ম্যাট্রিক্স গণনা করুন ३. বিমূর্ত মূল্য ফাংশন $V^{f_\nu(\pi_{\theta_t})}_U$ মূল্যায়ন করুন ४. নীতি প্যারামিটার $\theta_{t+1}$ আপডেট করুন

গণনা জটিলতা: $O(|S||A| + |U||S|^2 + |U|^3)$, যখন $|U| \ll |S|$ হয় তখন মান নীতি মূল্যায়নের $O(|S||A| + |S|^3)$ এর চেয়ে উল্লেখযোগ্যভাবে উন্নত।

EBHPG অ্যালগরিদম (অ্যালগরিদম २)

যখন পর্যাপ্ত শর্ত অপূর্ণ হয়, কর্মক্ষমতা নিম্ন সীমা অপ্টিমাইজ করুন: $J_S(\tilde{\pi}) \geq J_U(f_\nu(\tilde{\pi})) - \frac{\|g(\tilde{\pi},\nu)\|}{1-\gamma}$

যেখানে $\frac{\|g(\pi,\nu)\|}{1-\gamma}$ কর্মক্ষমতা পার্থক্যের উপরের সীমা।

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

१. শর্ত শিথিলকরণ: ঐতিহ্যবাহী সমরূপী MDP এর সম্পূর্ণ সমান রূপান্তর সম্ভাবনার প্রয়োজনের তুলনায়, এই পত্রটি শুধুমাত্র রৈখিক নির্ভরতা সম্পর্ক প্রয়োজন २. ম্যাট্রিক্স অপারেশন অপ্টিমাইজেশন: পুনরাবৃত্তিমূলক লুপের পরিবর্তে ম্যাট্রিক্স অপারেশনের মাধ্যমে সমন্বয় বাস্তবায়ন করে, গণনা দক্ষতা উন্নত করে ३. ত্রুটি সীমা: আদর্শ শর্ত অপূর্ণ হলে তাত্ত্বিক গ্যারান্টি এবং অপ্টিমাইজেশন দিকনির্দেশনা প্রদান করে

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

ডেটাসেট

१. র্যান্ডম মডেল: $|S|=100, |A|=10$, রূপান্তর ম্যাট্রিক্স ঘনত্ব ১০%-১००% २. দুর্বল-সংযুক্ত MDP: $|S|=3600, |A|=10$, স্তরযুক্ত সিদ্ধান্ত অনুকরণ করে ३. চার-কক্ষ গ্রিড বিশ্ব: $|S|=6400, |A|=4$, ক্লাসিক নেভিগেশন কাজ ४. সিরিজ কিউ ম্যানেজমেন্ট: $|S|=6084, |A|=3$, প্রকৃত সার্ভার সিস্টেম অনুপ্রাণিত

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

• নীতি কর্মক্ষমতা: $J_S(\pi) = \mathbb{E}_{s_0 \sim \xi_S}[V^\pi_S(s_0)]$
• গণনা সময়: প্রকৃত দক্ষতা পরিমাপের জন্য ওয়াল-ক্লক সময়
• সংগ্রহ: নীতি পুনরাবৃত্তি সর্বোত্তম সমাধানে সংগ্রহ করা

তুলনা পদ্ধতি

७টি ভিত্তিরেখা পদ্ধতি অন্তর্ভুক্ত:

• মান নীতি পুনরাবৃত্তি (PolicyIter)
• ক্লাসিক সমন্বয় কৌশল (Bertsekas)
• সাম্প্রতিক পদ্ধতি: Ayoub et al., Chen, Forghieri et al., Ishfaq et al., Lee et al.

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

• শেখার হার: $1 \times 10^{-3}$
• বিমূর্ত অবস্থা সংখ্যা: $|U| = \text{int}(0.5 \times r)$
• হার্ডওয়্যার: AMD Ryzen 7 5800X CPU + NVIDIA GeForce RTX 3090 GPU

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

তাত্ত্বিক যাচাইকরণ পরীক্ষা

চিত্র २ $|S|=100$ এর ছোট-স্কেল কাজে যাচাইকরণ ফলাফল প্রদর্শন করে:

१. পর্যাপ্ত শর্ত পূরণ হলে: "१००%" হিসাবে চিহ্নিত বক্ররেখা ($|U|=r$ এর সাথে সংশ্লিষ্ট) সমস্ত কাজে সর্বোত্তম মানে সংগ্রহ করে, উপপাদ্য २ এবং ३ এর সঠিকতা যাচাই করে २. পর্যাপ্ত শর্ত অপূর্ণ হলে: "८०%", "५०%", "२०%" হিসাবে চিহ্নিত বক্ররেখাগুলি স্পষ্ট দোলন প্রদর্শন করে, সর্বোত্তম সমাধানে সংগ্রহের গ্যারান্টি দিতে পারে না ३. EBHPG কর্মক্ষমতা: কঠিন লাইন (প্রকৃত কর্মক্ষমতা) ড্যাশড লাইন (কর্মক্ষমতা নিম্ন সীমা) উন্নতির সাথে উন্নত হয়, উপপাদ্য ५ এবং ६ যাচাই করে

বৃহৎ-স্কেল কর্মক্ষমতা তুলনা

চিত্র ३ বৃহৎ-স্কেল কাজে কর্মক্ষমতা তুলনা প্রদর্শন করে:

१. গণনা দক্ষতা: এই পত্রের পদ্ধতি চার-কক্ষ পরিবেশ ছাড়া সমস্ত কাজে ভিত্তিরেখা পদ্ধতির চেয়ে উল্লেখযোগ্যভাবে উন্নত २. মডেল-ভিত্তিক বনাম মডেল-মুক্ত: মডেল-ভিত্তিক পদ্ধতিগুলি সাধারণত মডেল-মুক্ত পদ্ধতির চেয়ে উন্নত, কারণ তারা নমুনা গ্রহণের পরিবর্তে নির্ভুল পরিকল্পনা ব্যবহার করে ३. ম্যাট্রিক্স অপারেশন সুবিধা: ভিত্তিরেখা পদ্ধতির নেস্টেড লুপ বাস্তবায়নের তুলনায়, ম্যাট্রিক্স অপারেশন উল্লেখযোগ্য দক্ষতা উন্নতি আনে

বিশেষ ক্ষেত্র বিশ্লেষণ

চার-কক্ষ পরিবেশে সমস্ত পদ্ধতি ভিত্তিরেখা অতিক্রম করতে অসুবিধা পায়, সম্ভাব্য কারণ:

• পুরস্কার কাঠামো অত্যন্ত বিরল
• বৃহৎ অবস্থা স্থান এবং বিরল পুরস্কারের সমন্বয় অন্বেষণ কঠিন করে তোলে
• পুরস্কার ফাংশন বিরলতা নীতি পুনরাবৃত্তি দক্ষতা হ্রাস করতে পারে

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

অবস্থা বিমূর্তকরণ পদ্ধতি শ্রেণীবিভাগ

१. বৈশিষ্ট্য-ভিত্তিক পদ্ধতি: হাতে তৈরি বা শেখা বৈশিষ্ট্য ফাংশন ব্যবহার করে, যেমন গতিশীল বেয়েসিয়ান নেটওয়ার্ক, বর্ণালী বিশ্লেষণ २. মূল্য-ভিত্তিক সমন্বয়: মূল্য ফাংশন আনুমানিক ত্রুটি ন্যূনতমকরণে মনোনিবেশ করে, যেমন অভিযোজিত পুনরাবৃত্তিমূলক সমন্বয় অ্যালগরিদম

তাত্ত্বিক কাঠামো উন্নয়ন

१. সমরূপী MDP তত্ত্ব: রবিন্দ্রন দ্বারা প্রস্তাবিত কাঠামো-সংরক্ষণকারী ম্যাপিং কাঠামো २. দ্বি-সিমুলেশন তত্ত্ব: MDP তে ক্লাসিক আচরণগত সমতুল্যতা ধারণার সম্প্রসারণ ३. ক্রমাগত স্থান সম্প্রসারণ: ফার্নস এবং অন্যরা দ্বি-সিমুলেশন মেট্রিক ক্রমাগত অবস্থা স্থানে সম্প্রসারিত করেছেন

এই পত্রের আপেক্ষিক সুবিধা

বিদ্যমান পদ্ধতির তুলনায়, এই পত্রটি আরও শিথিল পর্যাপ্ত শর্ত এবং আরও দক্ষ গণনা বাস্তবায়ন প্রদান করে।

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

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

१. সমরূপী ম্যাপিং-ভিত্তিক অবস্থা সমন্বয় তাত্ত্বিক কাঠামো স্থাপন করা হয়েছে २. সর্বোত্তম নীতি সমতুল্যতার পর্যাপ্ত শর্ত প্রদান করা হয়েছে, যা ঐতিহ্যবাহী সমরূপী MDP শর্তের চেয়ে আরও শিথিল ३. HPG এবং EBHPG দুটি ব্যবহারিক অ্যালগরিদম বিকশিত করা হয়েছে, যা তাত্ত্বিক এবং পরীক্ষামূলক উভয় ক্ষেত্রেই যাচাই করা হয়েছে

সীমাবদ্ধতা

१. পর্যাপ্ত শর্ত সীমাবদ্ধতা: কিছু ক্ষেত্রে, পর্যাপ্ত শর্ত পূরণের গণনা খরচ এখনও বেশি হতে পারে २. সংগ্রহ গ্যারান্টি: আনুমানিক ত্রুটি বিদ্যমান থাকলে, সর্বোত্তম নীতিতে সংগ্রহের গ্যারান্টি দিতে পারে না ३. ক্রমাগত স্থান: বিশ্লেষণ ক্রমাগত অবস্থা স্থানে সম্প্রসারিত হয়নি

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

१. সর্বোত্তম নীতি সমতুল্যতার পর্যাপ্ত শর্ত শিথিল করা २. ক্রমাগত অবস্থা স্থানে সম্প্রসারণ ३. আনুমানিক পরিস্থিতিতে সংগ্রহ কর্মক্ষমতা উন্নত করা

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

সুবিধা

१. তাত্ত্বিক অবদান: বিদ্যমান পদ্ধতির চেয়ে আরও সাধারণ তাত্ত্বিক কাঠামো প্রস্তাব করা হয়েছে २. ব্যবহারিকতা: অ্যালগরিদম ডিজাইন গণনা দক্ষতা বিবেচনা করে, বৃহৎ-স্কেল প্রয়োগের জন্য উপযুক্ত ३. সম্পূর্ণতা: তাত্ত্বিক বিশ্লেষণ থেকে অ্যালগরিদম ডিজাইন থেকে পরীক্ষামূলক যাচাইকরণ পর্যন্ত, সম্পূর্ণ গবেষণা শৃঙ্খল গঠন করে ४. কঠোরতা: গাণিতিক উদ্ভাবন কঠোর, পরীক্ষামূলক ডিজাইন যুক্তিসঙ্গত

অপূর্ণতা

१. প্রযোজ্য পরিসীমা: পর্যাপ্ত শর্ত কিছু ক্ষেত্রে এখনও অত্যন্ত কঠোর হতে পারে २. পরীক্ষামূলক কভারেজ: চার-কক্ষ পরিবেশের অস্বাভাবিক ফলাফল গভীর বিশ্লেষণের প্রয়োজন ३. তুলনা ভিত্তিরেখা: কিছু তুলনা পদ্ধতি সর্বশেষ SOTA পদ্ধতি নাও হতে পারে

প্রভাব

१. তাত্ত্বিক মূল্য: MDP অবস্থা সমন্বয়ের জন্য নতুন তাত্ত্বিক সরঞ্জাম প্রদান করে २. ব্যবহারিক মূল্য: অ্যালগরিদম একাধিক ব্যবহারিক কাজে সুবিধা প্রদর্শন করে ३. সম্প্রসারণযোগ্যতা: কাঠামো অন্যান্য সমস্যায় সম্প্রসারণের সম্ভাবনা রয়েছে

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

१. বৃহৎ-স্কেল MDP সমাধান २. স্তরযুক্ত শক্তিশালী শেখা ३. বহু-এজেন্ট সিস্টেম ४. কাঠামোগত অবস্থা স্থান সহ সিদ্ধান্ত সমস্যা

রেফারেন্স

পত্রটি ৫০টি সম্পর্কিত সাহিত্য উদ্ধৃত করে, যা MDP তত্ত্ব, অবস্থা বিমূর্তকরণ, শক্তিশালী শেখা ইত্যাদি একাধিক ক্ষেত্রের গুরুত্বপূর্ণ কাজ অন্তর্ভুক্ত করে, গবেষণার জন্য একটি দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করে।

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