Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model

تخيل أنك كابتن سفينة فضائية تبحر في مجرة تتغير فيها قواعد الفيزياء في كل مرة ترمش فيها بعينيك. هدفك هو جمع أكبر قدر ممكن من نقاط "غبار النجوم" قبل أن ينفد وقودك. وللقيام بذلك، تحتاج إلى خريطة مثالية ومجموعة من التعليمات تخبرك بالضبط أي اتجاه يجب أن تسلكه عند كل لحظة. هذا هو جوهر "التعلم المعزز" (Reinforcement Learning)، وهو فرع من علوم الحاسوب حيث يتعلم "وكيل" اصطناعي كيفية اتخاذ قرارات ذكية من خلال التفاعل مع عالم ما، وتجربة الأشياء، ومعرفة ما يمنحه أكبر مكافأة.

غالباً ما يتم نمذجة العالم الذي يعيش فيه الوكيل كـ "عملية قرار ماركوف" (Markov Decision Process - MDP). فكر في هذا كأنه لعبة لوحية ضخمة متعددة المستويات. أنت موجود في مربع معين ("الحالة" - state)، ويمكنك الاختيار من قائمة حركات ("الأفعال" - actions). كل حركة تمنحك درجة ("المكافأة" - reward) وقد تضعك في مربع جديد، ولكن هناك خدعة: اللوحة زلقة. أنت لا تعرف بالتأكيد المربع الذي ستستقر فيه؛ أنت تعرف فقط "الاحتمالات" للوصğun إليه. التحدي هو أنه إذا كانت اللوحة ضخمة (بملايين المربعات والحركات)، فإن تحديد الاستراتيجية المثالية يصبح مستحيلاً على جهاز كمبيوتر عادي. وهذا ما يُعرف بـ "لعنة الأبعاد" (curse of dimensionality).

هنا يأتي دور "الحوسبة الكمومية" (Quantum Computing). بينما تفكر أجهزة الكمبيوتر العادية بالبتات (0 و1)، تستخدم أجهزة الكمبيوتر الكمومية "الكيوبتات" (qubits) التي يمكن أن توجد في حالات متعددة في وقت واحد، مثل عملة معدنية تدور وهي تمثل "صورة" و"كتابة" في آن واحد. هذا يسمح لها باستكشاف العديد من الاحتمالات بالتوازي، مما قد يحل الألغاز المعقدة بسرعة أكبر بكما. يحاول العلماء استخدام هذه القوة الخارقة لفك شفرة التعلم المعزز، آملين في إيجاد استراتيجية الملاحة المثالية لسفينتنا الفضائية دون الانتظار طوال العمر للحصول على الإجابة.

القفزة الكبرى للورقة البحثية: ملاحة كمومية أسرع

في هذا العمل، يقترح المؤلف، جواو ف. دوريجيلو (Joao F. Doriguello)، مجموعة جديدة من الخوارزميات الكمومية المصممة لإيجاد هذه الاستراتيجيات شبه المثالية بسرعة أكبر بك jauh من الطرق السابقة. إنهم يتناولون نوعين محددين من الألعاب اللوحية: "عمليات قرار ماركوف ذات الأفق المحدود" (Finite-Horizon MDPs) (حيث تنتهي اللعبة بعد عدد محدد من الأدوار، مثل سباق له خط نهاية)، و"عمليات قرار ماركوف ذات الأفق اللانهائي والخصم" (Infinite-Horizon Discounted MDPs) (حيث تستمر اللعبة للأبد، ولكن النقاط التي تكسبها لاحقاً تكون قيمتها أقل من النقاط التي تكسبها الآن).

اكتشاف المؤلف الرئيسي هو أنه يمكنه حساب استراتيجية "شبه مثالية" (تسمى $\epsilon$-optimal policy) بعدد أقل بكثير من "الاستفسارات" لقواعد اللعبة مما نجح أي شخص آخر في تحقيقه من قبل. بلغة علوم الحاسوب، لقد قام بتحسين "تعقيد الاستعلام" (query complexity). فكر في "الاستعلامات" كعدد المرات التي يتعين على الكمبيوتر فيها "إلقاء نظرة" على لوحة اللعبة لفهم احتمالات الحركة. وكلما قل عدد النظرات المطلوبة، كانت الحل أسرع.

كيف فعلوا ذلك: "الماسح الخارق" و"شبكة الأمان"

كانت المحاولات الكمومية السابقة تشبه محاولة إيجاد أفضل مسار عبر متاهة عن طريق فحص كل منعطف واحداً تلو الآخر، ولكن باستخدام كشاف فائق السرعة. ورغم سرعتها، إلا أنها كانت لا تزال بحاجة لفحص الكثير من المنعطفات. تجمع طريقة المؤلف الجديدة بين فكرتين قويتين لتحقيق تسريع هائل:

1. "الماسح الخارق" (تقدير المتوسط الكمومي - Quantum Mean Estimation): بدلاً من مجرد التخمين لمتوسط مكافأة حركة ما، تستخدم الخوارزمية الجديدة خدعة كمومية لتقدير المتوسط و"التباين" (variance) -أي مدى تفاوت النتائج- في آن واحد. الأمر يشبه امتلاك ماسح ضوئي لا يخبرك فقط بمتوسط سرعة السيارات على الطريق السريع، بل يخبرك أيضاً بمدى وعورة الطريق، وكل ذلك في نظرة واحدة.
2. "شبكة الأمان" (الرتابة والتباين الكلي - Monotonicity and Total-Variance): يستعير المؤلف تقنية ذكية من الرياضيات الكلاسيكية تسمى "التباين الكلي" (total-variance). تخيل أنك تسير في ممر طويل ومظلم؛ إذا تعثرت، فقد تسقط. ولكن إذا كنت تعلم أن عثراتك تميل إلى إلغاء بعضها البعض (بعض الخطوات مهتزة وبعضها ثابت)، فيمكنك المشي بشكل أسرع دون خوف. تستخدم الخوارزمية هذه الرياضيات لتثبت أنه حتى لو لم تكن التخمينات الفردية مثالية، فإن "إجمالي" الخطأ طوال اللعبة يظل صغيراً. هذا يسمح للكمبيوتر الكمومي بأن يكون أقل حذراً وأكثر جرأة في بحثه، متخطياً الفحوصات غير الضرورية.

من خلال دمج "الماسح الخارق" داخل روتين "البحث عن الحد الأقصى الكمومي" (Quantum Maximum Finding) -وهي أداة تجد فوراً أعلى رقم في قائمة ضخمة- أنشأ المؤلف نظاماً يجد أفضل حركة أسرع بمقدار تربيعي (quadratically faster) مما سبق.

النتائج: رقم قياسي جديد

تثبت الورقة رياضياً أن خواروارزميته تعمل باحتمالية عالية. وقد أظهروا أنه بالنسبة للعبة تحتوي على $S$ من الحالات، و $A$ من الأفعال، وأفق (أو أفق فعال) قدره $H$ (أو $\Gamma$)، فإن طريقتهم تتطلب تقريباً:

• للألعاب ذات الأفق المحدود: $\tilde{O}\left(\frac{H^{2.5} S \sqrt{A}}{\epsilon}\right)$ استعلامات.
• للألعاب ذات الأفق اللانهائي: $\tilde{O}\left(\frac{\Gamma^{2.5} S \sqrt{A}}{\epsilon}\right)$ استعلامات.

هنا، تمثل $\epsilon$ مدى قرب الحل من المثالية (كلما صغرت $\epsilon$، كانت الإجابة أكثر دقة). الرمز ($\tilde{O}$) يعني أنهم يتجاهلون بعض التفاصيل الصغيرة والمعقدة مثل اللوغاريثمات، ويركزون على معدلات النمو الرئيسية.

هذه الأرقام تمثل تحسناً ملموساً مقارنة بأفضل الخوارزميات الكمومية السابقة، التي كانت عالقة عند قوى أعلى مثل $H^3$ أو $\Gamma^3$. لقد تمكن المؤلف فعلياً من اختصار جزء كبير من العمل الحسابي. وبينما لم يصلوا بعد إلى الحد النظري المطلق ("الحد الأدنى" - lower bound)، إلا أنهم دفعوا الهدف بعيداً نحو الأمام، مما يثبت أن أجهزة الكمبيوتر الكمومية يمكنها بالفعل ملاحة هذه العوالم المعقدة لاتخاذ القرار بكفاءة أكبر مما كان يُعتقد سابقاً.

باختصار، هذه الورقة لا تقترح مجرد طريقة جديدة للعب، بل تقدم برهاناً رياضياً صارماً على وجود استراتيجية كمومية جديدة هي أسرع وأكثر كفاءة من الاستراتيجيات القديمة، مما يقربنا خطوة أخرى من حل "لعنة الأبعاد" في الذكاء الاصطناعي.