ملخص تقني: القليل من الحرية يقطع شوطاً طويلاً: خوارزميات كلاسيكية وكمومية للتعلم المعزز تحت نموذج توليدي

بيان المشكلة

تتناول الورقة مشكلة تعلم عمليات ماركوف لاتخاذ القرار (MDPs) في إطار عبر الإنترنت (online setting)، مع التركيز بشكل خاص على تقليل الندم (regret) (الفرق بين المكافأة المتراكمة للوكيل ومكافأة السياسة المثلى). يتناول المؤلفون ثلاثة إعدادات متميزة لعمليات ماركوف لاتخاذ القرار (MDPs):

1. عمليات ماركوف ذات الأفق المحدود: تحدث التفاعلات على مدى عدد ثابت من الخطوات $H$.
2. عمليات ماركوف ذات الأفق اللانهائي والخصم: تستمر التفاعلات إلى ما لا نهاية مع خصم المكافآت بعامل $\gamma \in [0, 1)$.
3. عمليات ماركوف ذات الأفق اللانهائي وغير المخصومة: تستمر التفاعلات إلى ما لا نهاية وفق معايير المكافأة المتوسطة، وتحديداً التركيز على عمليات ماركوف ذات الاتصال الضعيف.

يعد التوازن بين الاستكشاف والاستغلال (exploration-exploitation trade-off) تحدياً مركزياً في التعلم المعزز (RL). في الإعداد الكلاسيكي، يجب على الوكلاء تعلم احتمالات الانتقال $p(\cdot|s, a)$ أثناء التفاعل مع البيئة. أما في الإعداد الكمومي، فتنشأ مشكلة جوهرية: تسمح الأورات (oracles) الكمومية القياسية بالتركيب (superposition) والعمليات العكسية، مما قد يؤدي إلى مقاييس ندم غير محددة إذا تفاعل الوكيل مع البيئة بطريقة كمومية طوال عملية التعلم. علاوة على ذلك، اعتمدت أعمال التعلم المعزز الكمومي السابقة التي حاولت تحقيق ندم لوغاريتمي متعدد (polylogarithmic regret) في الزمن $T$ على افتراضات معيبة تتعلق بالتطبيق المتماسك لتقدير السعة الكمومية (quantum amplitude estimation).

المنهجية

نموذج التعلم المعزز الهجين (متصل عبر الإنترنت-خارج الإنترنت)

لحل المشكلات التعريفية للندم في التعلم المعزز الكمومي وللاستفادة من التسريع الكمومي، يقترح المؤلفون نموذج تعلم معزز هجين (متصل عبر الإنترنت-خارج الإنترنت). يفصل هذا النموذج عملية التعلم إلى مرحلتين متميزتين:

1. المرحلة عبر الإنترنت (الاستكشاف): يتفاعل الوكيل مع البيئة كلاسيكياً. يختار الأفعال، ويتلقى المكافآت، ويلاحظ انتقالات الحالة. ومن الأهمية بمكان أن الندم يتراكم خلال هذه المرحلة. لا يملك الوكيل وصولاً إلى الأورات الكمومية هنا.
2. المرحلة خارج الإنترنت (التعلم التوليدي): يُمنح الوكيل "الحرية" للتفاعل مع البيئة عبر نموذج توليدي.
   • في المرحلة الكلاسيكية خارج الإنترنت، يصل الوكيل إلى أورات أخذ العينات $C_p$ التي تعيد الحالات التالية $s'$ بناءً على $(s, a)$.
   • في المرحلة الكمومية خارج الإنترنت، يصل الوكيل إلى أورات كمومية $Q_p$ (ومعكوسها) التي تجهز تراكبات الحالات التالية.
   • القيد: عدد استدعاءات الأورات في المرحلة خارج الإنترنت مقيد بدالة لطول المرحلة عبر الإنترنت السابقة $\tau$، وتحديداً $O(\tau^\beta)$، حيث $\beta \in [0, \infty)$ هو معامل "الميزانية"، وهذا يمنع الوكيل من الحصول على سياسة قريبة من المثالية بندم صفري بمجرد استعلام الأورات بشكل مفرط.

النهج الخوارزمي

تتقدم الخوارزميات المقترحة (الخوارزمية 1) عبر حقبات (epochs). في كل حقبة $\ell$:

1. الحساب خارج الإنترنت: باستخدام البيانات التي تم جمعها في المرحلة عبر الإنترنت السابقة (طول $\tau_{\ell-1}$)، يحسب الوكيل سياسة مثالية بمقدار $\epsilon_\ell$.
   • كلاسيكياً: يستخدم خوارزميات مثالية للعينات (مثل Sidford et al.) لحساب السياسات.
   • كمومياً: يقدم المؤلفون خوارزميات كمومية جديدة لحساب السياسات المثلى تحت نموذج توليدي. تستخدم هذه الخوارزميات تقدير المتوسط الكمومي (Kothari and O'Donnell) والبحث عن الحد الأدنى/الأقصى الكمومي (Dürr and Høyer) لتسريع تكرار القيمة (value iteration).
2. التنفيذ عبر الإنترنت: يتم تنفيذ السياسة المحسوبة $\pi^{(\ell)}$ في البيئة لمدة يتم تحديدها بواسطة خدعة المضاعفة (doubling trick) (زيادة الأفق بمعامل 2 أو $2H$).
3. تحليل الندم: يتم حصر إجمالي الندم عن طريق جمع دون المثالية للسياسات المستخدمة في كل مرحلة عبر الإنترنت.

المساهمات التقنية الرئيسية

1. خوارزميات كمومية مبتكرة للنماذج التوليدية:

   • الأفق المحدود: يصمم المؤلفون خوارزميات كمومية تحسن من تعقيد الاستعلام الكلاسيكي. يجمعون بين تكرار القيمة المكمم وتقنيات تقليل التباين. تعقيد الاستعلام هو $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$، مما يحسن الاعتماد على $H$ و $A$ مقارنة بالحدود الكلاسيكية.
   • الأفق اللانهائي المخصوم: يتم تحقيق تحسينات مماثلة، بتعقيد استعلام $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$.
   • الأفق اللانهائي غير المخصوم: هذه مساهمة جديدة. يقترح المؤلفون خوارزمية كمومية لعمليات ماركوف ذات الاتصال الضعيف تحت افتراض أن مؤثر بلمان الأمثل هو $J$-stage $\nu$-span contraction. التعقيد هو $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$.

2. تصحيح أعمال التعلم المعزز الكمومي السابقة:
   تنقد الورقة الأعمال السابقة (مثل Ganguly et al., Zhong et al.) التي ادعت تحقيق ندم لوغاريتمي متعدد. يجادل المؤلفون بأن هذه الأعمال افترضت بشكل خاطئ إمكانية إجراء تقدير السعة الكمومية على مجموعة من الحالات المخزنة بدلاً من اشتراط تطبيقات متسلسلة ومتماسكة للأورات ومعكوسها. يصحح النموذج الهجين المقترح هذا من خلال فرض مرحلة منفصلة خارج الإنترنت حيث يمكن إجراء مثل هذه العمليات المتماسكة دون تكبد ندم.

3. حدود الندم تحت النموذج الهجين:
   يستنتج المؤلفون حدود الندم لكل من الإعدادات الكلاسيكية والكمومية كدالة لمعامل الميزانية $\beta$:

   • الأفق المحدود:
     • كلاسيكياً: $\tilde{O}(\sqrt{HSAT})$ (مطابق لأحدث ما توصل إليه العلم) عندما تكون $\beta \ge 2$.
     • كمومياً: $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ عندما تكون $\beta < 1$، ولوغاريتمي متعدد في $T$ عندما تكون $\beta \ge 1$.
   • الأفق اللانهائي المخصوم:
     • كمومياً: يحقق $\tilde{O}(\text{polylog}(T))$ من الندم عندما تكون $\beta \ge 1$، كاسراً حاجز $\Omega(\sqrt{T})$ الكلاسيكي.
   • الأفق اللانهائي غير المخصوم:
     • كمومياً: يحقق $\tilde{O}(\Lambda S \sqrt{A} \cdot \text{polylog}(T))$ من الندم لـ $\beta \ge 1$، مما يحسن بشكل كبير حد $\tilde{O}(\Lambda S^5 A^4)$ للأعمال الكمومية السابقة.

النتائج والأهمية

تدعي الورقة أن "القليل من الحرية" الذي توفره المرحلة التوليدية خارج الإنترنت يسمح بتحسن كبير في كفاءة التعلم.

• التفوق الكمومي: النتيجة الأكثر أهمية هي إثبات أن الحواسيب الكمومية يمكنها تحقيق ندم لوغاريتمي متعدد في أفق الزمن $T$ (تحديداً عندما يكون $\beta \in [1, 2)$)، في حين أن الخوارزميات الكلاسيكية محدودة جوهرياً بندم $\Omega(\sqrt{T})$. يمثل هذا تحسناً أسياً في الاعتماد على $T$.
• الاعتماد على المعاملات: تحسن الخوارزميات الكمومية الاعتماد على حجم فضاء الحالة $S$، وفضاء الفعل $A$، والأفق $H$ (أو الأفق الفعال $\Gamma$) مقارنة بكل من الخوارزميات الكلاسيكية وأعمال الكم السابقة.
• صلاحية النموذج: تثبت الورقة أن نموذج التعلم المعزز الهجين (متصل عبر الإنترنت-خارج الإنترنت) هو إطار ضروري وذي معنى للتعلم المعزز الكمومي. فهو يحل الغموض في تعريف الندم في التفاعلات الكمومية ويصحح العيوب النظرية في الأدبيات السابقة التي افترضت استكشافاً كمومياً خالياً من الندم دون هذا الفصل.

يخلص المؤلفون إلى أنه بينما يتلاشى التفوق الكمومي الأسسي في $T$ عندما تكون الميزانية $\beta$ كبيرة جداً ($\beta \ge 2$، حيث تحقق الخوارزميات الكلاسيكية أيضاً ندماً لوغاريتمياً متعددًا)، إلا أن هناك نطاقاً حرجاً ($\beta \in [1, 2)$) حيث توفر الحواسيب الكمومية ميزة كبيرة. تحدد الورقة هذا النطاق باعتباره المنطقة الأساسية التي يكون فيها التسريع الكمومي في التعلم المعزز أكثر تأثيراً تحت النموذج المقترح.