2025-11-25T11:58:17.992104

Multi Timescale Stochastic Approximation: Stability and Convergence

Deb, Ganesh, Bhatnagar
This paper presents the first sufficient conditions that guarantee the stability and almost sure convergence of multi-timescale stochastic approximation (SA) iterates. It extends the existing results on one-timescale and two-timescale SA iterates to general $N$-timescale stochastic recursions, for any $N \geq 1$, using the ordinary differential equation (ODE) method. As an application, we study SA algorithms augmented with heavy-ball momentum in the context of Gradient Temporal Difference (GTD) learning. The added momentum introduces an auxiliary state evolving on an intermediate timescale, yielding a three-timescale recursion. We show that with appropriate momentum parameters, the scheme fits within our framework and converges almost surely to the same fixed point as baseline GTD. The stability and convergence of all iterates including the momentum state follow from our main results without ad hoc bounds. We then study off-policy actor-critic algorithms with a baseline learner, actor, and critic updated on separate timescales. In contrast to prior work, we eliminate projection steps from the actor update and instead use our framework to guarantee stability and almost sure convergence of all components. Finally, we extend the analysis to constrained policy optimization in the average reward setting, where the actor, critic, and dual variables evolve on three distinct timescales, and we verify that the resulting dynamics satisfy the conditions of our general theorem. These examples show how diverse reinforcement learning algorithms covering momentum acceleration, off-policy learning, and primal-dual methods-fit naturally into the proposed multi-timescale framework.
academic

মাল্টি টাইমস্কেল স্টোকাস্টিক অ্যাপ্রক্সিমেশন: স্থিতিশীলতা এবং সংযোগ

মৌলিক তথ্য

  • পেপার আইডি: 2112.03515
  • শিরোনাম: Multi Timescale Stochastic Approximation: Stability and Convergence
  • লেখক: Rohan Deb (ইলিনয় বিশ্ববিদ্যালয়, আরবানা-চ্যাম্পেইন), Swetha Ganesh (পারডু বিশ্ববিদ্যালয়, ওয়েস্ট লাফায়েট), Shalabh Bhatnagar (ভারতীয় বিজ্ঞান প্রতিষ্ঠান, বেঙ্গালুরু)
  • শ্রেণীবিভাগ: eess.SY cs.SY
  • প্রকাশনার সময়: ১৬ অক্টোবর, ২০২৫ (arXiv সংস্করণ)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2112.03515v3

সারসংক্ষেপ

এই পেপারটি মাল্টি-টাইমস্কেল স্টোকাস্টিক অ্যাপ্রক্সিমেশন (SA) পুনরাবৃত্তির স্থিতিশীলতা এবং প্রায় নিশ্চিত সংযোগের গ্যারান্টি দেওয়ার জন্য প্রথম পর্যাপ্ত শর্ত প্রস্তাব করে। এই কাজটি বিদ্যমান একক টাইমস্কেল এবং দ্বি-টাইমস্কেল SA ফলাফলগুলিকে সাধারণ N টাইমস্কেল স্টোকাস্টিক পুনরাবৃত্তিতে প্রসারিত করে, যেকোনো N≥1 এর জন্য প্রযোজ্য, সাধারণ অবকল সমীকরণ (ODE) পদ্ধতি ব্যবহার করে। একটি প্রয়োগ হিসাবে, গ্রেডিয়েন্ট টেম্পোরাল ডিফারেন্স (GTD) শিক্ষায় বর্ধিত ভারী বল গতিবেগ সহ SA অ্যালগরিদম অধ্যয়ন করা হয়েছে। যোগ করা গতিবেগ মধ্যবর্তী টাইমস্কেলে বিকশিত সহায়ক অবস্থা প্রবর্তন করে, যা তিন-টাইমস্কেল পুনরাবৃত্তি তৈরি করে। উপযুক্ত গতিবেগ পরামিতির অধীনে, এই স্কিমটি ফ্রেমওয়ার্কের সাথে সামঞ্জস্যপূর্ণ এবং প্রায় নিশ্চিতভাবে বেসলাইন GTD এর মতো একই স্থির বিন্দুতে সংযুক্ত হয় তা প্রমাণ করা হয়েছে।

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

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

স্টোকাস্টিক অ্যাপ্রক্সিমেশন অ্যালগরিদম হল একটি পুনরাবৃত্তিমূলক প্রক্রিয়ার শ্রেণী যা ফাংশনের শূন্য খুঁজে পেতে ব্যবহৃত হয়, যখন প্রকৃত ফাংশন অজানা কিন্তু শব্দযুক্ত পর্যবেক্ষণ উপলব্ধ থাকে। অনেক অপ্টিমাইজেশন এবং অনিশ্চয়তা নিয়ন্ত্রণ সমস্যায়, তিন বা তার বেশি টাইমস্কেল পুনরাবৃত্তি জড়িত অ্যালগরিদম সম্মুখীন হয়।

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

  1. ব্যবহারিক চাহিদা: শক্তিশালী শিক্ষায়, সীমাবদ্ধ মার্কভ সিদ্ধান্ত প্রক্রিয়ার অ্যাক্টর-সমালোচক অ্যালগরিদম, শ্রেণিবদ্ধ শক্তিশালী শিক্ষা ইত্যাদি পরিস্থিতিতে মাল্টি-টাইমস্কেল অ্যালগরিদম স্বাভাবিকভাবে উপস্থিত হয়
  2. তাত্ত্বিক শূন্যতা: বিদ্যমান সাহিত্য শুধুমাত্র একক টাইমস্কেল এবং দ্বি-টাইমস্কেল SA এর স্থিতিশীলতা এবং সংযোগ শর্ত প্রদান করে, N>2 ক্ষেত্রে সাধারণ তত্ত্বের অভাব রয়েছে

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

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

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

সাধারণ N টাইমস্কেল স্টোকাস্টিক পুনরাবৃত্তির স্থিতিশীলতা এবং সংযোগ নিশ্চিত করার জন্য প্রথম সেট পর্যাপ্ত শর্ত প্রদান করা, তাত্ত্বিক শূন্যতা পূরণ করা এবং জটিল শক্তিশালী শিক্ষা অ্যালগরিদমের বিশ্লেষণ সমর্থন করা।

মূল অবদান

  1. তাত্ত্বিক অগ্রগতি: N টাইমস্কেল SA পুনরাবৃত্তির স্থিতিশীলতা এবং প্রায় নিশ্চিত সংযোগ নিশ্চিত করার জন্য প্রথম পর্যাপ্ত শর্ত প্রস্তাব করা
  2. পদ্ধতি সম্প্রসারণ: Borkar-Meyn একক টাইমস্কেল এবং Lakshminarayanan-Bhatnagar দ্বি-টাইমস্কেল ফলাফল যেকোনো N≥1 এ সাধারণীকরণ করা
  3. প্রয়োগ যাচাইকরণ: তিনটি গুরুত্বপূর্ণ শক্তিশালী শিক্ষা পরিস্থিতিতে ফ্রেমওয়ার্কের কার্যকারিতা যাচাই করা:
    • গতিবেগ সহ গ্রেডিয়েন্ট টেম্পোরাল ডিফারেন্স (GTD) শিক্ষা
    • অফ-পলিসি অ্যাক্টর-সমালোচক অ্যালগরিদম
    • সীমাবদ্ধ নীতি অপ্টিমাইজেশন
  4. প্রযুক্তিগত উদ্ভাবন: অ্যাক্টর আপডেটে প্রজেকশন ধাপ নির্মূল করা, শুধুমাত্র সংযোগ ফ্রেমওয়ার্কের উপর নির্ভর করে স্থিতিশীলতা নিশ্চিত করা

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

কাজের সংজ্ঞা

N টি সংযুক্ত স্টোকাস্টিক পুনরাবৃত্তি বিবেচনা করুন:

x^(j)_{n+1} = x^(j)_n + α^(j)_n (h^(j)(x^(1)_n, x^(2)_n, ..., x^(N)_n) + M^(j)_{n+1})

যেখানে j = 1, 2, ..., N, নিশ্চিত করতে প্রয়োজন:

  • স্থিতিশীলতা: sup_n ||x^(j)_n|| < ∞ a.s. ∀j
  • সংযোগ: x^(j)n → x^(j)* a.s. ∀j

মূল তাত্ত্বিক ফ্রেমওয়ার্ক

মৌলিক অনুমান

(A:1) h^(j) হল Lipschitz ক্রমাগত ফাংশন
(A:2) {M^(j)_{n+1}} হল মার্টিনগেল পার্থক্য ক্রম, শর্তসাপেক্ষ প্রত্যাশা সীমাবদ্ধ সন্তুষ্ট করে
(A:3) ধাপ দৈর্ঘ্য ক্রম সন্তুষ্ট করে:

  • α^(j)_n > 0, Σα^(j)_n = ∞
  • Σ(α^(j)_n)² < ∞
  • α^(j)_n/α^(j-1)_n → 0 (টাইমস্কেল বিচ্ছেদ)

স্থিতিশীলতা শর্ত (B.N.i)

স্কেলিং ফাংশনের জন্য h^(i)_c(x^(i), x^(i+1), ..., x^(N)) = h^(i)(cy^(1), cy^(2), ..., cy^(N))/c, প্রয়োজন:

  1. h^(i)c → h^(i)∞ সমানভাবে সংযুক্ত
  2. সীমাবদ্ধ ODE ẋ^(i)(t) = h^(i)_∞(x^(i)(t), x^(i+1), ..., x^(N)) অনন্য বৈশ্বিক অ্যাসিম্পটোটিকভাবে স্থিতিশীল ভারসাম্য বিন্দু আছে
  3. ভারসাম্য বিন্দু ম্যাপিং λ^(i)_∞ হল Lipschitz ক্রমাগত

সংযোগ শর্ত (C.N.i)

শ্রেণিবদ্ধ স্থির বিন্দু কাঠামোর অধীনে মূল ODE সিস্টেমের বৈশ্বিক অ্যাসিম্পটোটিক স্থিতিশীলতা।

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

উপপাদ্য 1: অনুমান (A:1)-(A:3), (B.N.i) এবং (C.N.i) এর অধীনে, N টাইমস্কেল পুনরাবৃত্তি শ্রেণিবদ্ধ স্থির বিন্দুতে সংযুক্ত হয়:

x^(j)_n → x^(j)_* = λ^(j:N-1)(x^(N)_*)

প্রমাণ কৌশল

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

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

প্রয়োগ পরিস্থিতি

1. গতিবেগ সহ GTD শিক্ষা

  • ডেটাসেট: 5-State Random Walk, 7-state Boyan Chain
  • অ্যালগরিদম: GTD2-M-3TS, TDC-M-3TS (তিন টাইমস্কেল), GTD2-M-4TS, TDC-M-4TS (চার টাইমস্কেল)
  • পরামিতি সেটিং:
    • 5-State RW: α=0.4, β=0.4, ϱ^(1)=0.5, ϱ^(2)=0.25
    • Boyan Chain: α=0.35, β=0.35, ϱ^(1)=0.45, ϱ^(2)=0.35

2. অফ-পলিসি অ্যাক্টর-সমালোচক

  • সেটিং: Gibbs নীতি প্যারামিটারাইজেশন, গুরুত্ব নমুনা অনুপাত
  • আপডেট নিয়ম: সমালোচক (দ্রুততম), অ্যাক্টর (মধ্যম), বেসলাইন (সবচেয়ে ধীর) টাইমস্কেল

3. সীমাবদ্ধ অ্যাক্টর-সমালোচক

  • সমস্যা: গড় পুরস্কার সীমাবদ্ধ অপ্টিমাইজেশন
  • টাইমস্কেল: সমালোচক (দ্রুততম), অ্যাক্টর (মধ্যম), দ্বৈত পরিবর্তনশীল (সবচেয়ে ধীর)

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

  • GTD: Root Mean Square Projected Bellman Error (RMSPBE)
  • অ্যাক্টর-সমালোচক: নীতি কর্মক্ষমতা এবং সংযোগ
  • তাত্ত্বিক যাচাইকরণ: প্রায় নিশ্চিত সংযোগ প্রমাণ

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

প্রধান ফলাফল

GTD গতিবেগ পরীক্ষা

  1. কর্মক্ষমতা উন্নতি: গতিবেগ সংস্করণ উভয় MDP তে ভ্যানিলা সংস্করণের চেয়ে উন্নত
  2. সংযোগ যাচাইকরণ: সমস্ত অ্যালগরিদম তাত্ত্বিক পূর্বাভাসিত স্থির বিন্দু θ* = -Ā^(-1)b̄ তে সংযুক্ত হয়
  3. টাইমস্কেল তুলনা:
    • GTD2: 4-TS স্কিম আরও ভাল কর্মক্ষমতা করে
    • TDC: 3-TS সংস্করণ আরও ভাল কর্মক্ষমতা করে

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

  1. স্থিতিশীলতা: তিনটি প্রয়োগই অনুমান (B.N.i) এবং (C.N.i) সন্তুষ্ট করে
  2. সংযোগ: প্রত্যাশিত শ্রেণিবদ্ধ স্থির বিন্দুতে প্রায় নিশ্চিত সংযোগ প্রমাণ করা হয়েছে
  3. কোন প্রজেকশন নেই: অ্যাক্টর আপডেটে প্রজেকশন অপারেশন সফলভাবে নির্মূল করা হয়েছে

প্রযুক্তিগত আবিষ্কার

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

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

তাত্ত্বিক ভিত্তি

  1. একক টাইমস্কেল SA: Borkar-Meyn (2000) এর ODE পদ্ধতি এবং স্থিতিশীলতা শর্ত
  2. দ্বি-টাইমস্কেল SA: Borkar (1997) এর সংযোগ, Lakshminarayanan-Bhatnagar (2017) এর স্থিতিশীলতা
  3. শক্তিশালী শিক্ষা প্রয়োগ: অ্যাক্টর-সমালোচক অ্যালগরিদম, GTD পদ্ধতি, সীমাবদ্ধ MDP

এই পেপারের সুবিধা

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

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

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

  1. N টাইমস্কেল SA এর জন্য প্রথম সম্পূর্ণ তাত্ত্বিক ফ্রেমওয়ার্ক সফলভাবে প্রতিষ্ঠা করা
  2. তিনটি গুরুত্বপূর্ণ শক্তিশালী শিক্ষা অ্যালগরিদম শ্রেণীর স্থিতিশীলতা এবং সংযোগ প্রমাণ করা
  3. টেম্পোরাল ডিফারেন্স শিক্ষায় গতিবেগ কৌশলের তাত্ত্বিক সম্ভাব্যতা প্রদর্শন করা

সীমাবদ্ধতা

  1. মার্কভ শব্দ: বর্তমান ফ্রেমওয়ার্ক মার্টিনগেল পার্থক্য শব্দের মধ্যে সীমাবদ্ধ, আরও সাধারণ মার্কভ শব্দ পরিচালনা করে না
  2. ধাপ দৈর্ঘ্য প্রয়োজনীয়তা: তাত্ত্বিক বিশ্লেষণ বর্গ-সংক্ষিপ্ত ধাপ দৈর্ঘ্য প্রয়োজন, কিন্তু পরীক্ষা দেখায় যে অ-বর্গ-সংক্ষিপ্ত ধাপ দৈর্ঘ্যও কার্যকর
  3. সীমিত সময় বিশ্লেষণ: সংযোগ গতির পরিমাণগত বিশ্লেষণের অভাব

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

  1. মার্কভ শব্দে সম্প্রসারণ: Ramaswamy-Bhatnagar এর একক টাইমস্কেল ফলাফল সাধারণীকরণ করা
  2. সেট-মূল্যবান ম্যাপিং: আংশিক পর্যবেক্ষণ/তথ্যের অধীনে RL অ্যালগরিদম পরিচালনা করা
  3. সংযোগ গতি: N টাইমস্কেলের দুর্বল সংযোগ গতি তত্ত্ব বিকাশ করা
  4. সীমিত সময় আচরণ: গতিবেগ অ্যালগরিদমের সীমিত সময় কর্মক্ষমতা লাভ পরিমাণ করা

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

শক্তি

  1. তাত্ত্বিক অগ্রগতি: মাল্টি-টাইমস্কেল SA তত্ত্বের গুরুত্বপূর্ণ শূন্যতা পূরণ করা, মাইলফলক তাৎপর্য রয়েছে
  2. পদ্ধতি কঠোরতা: পরিশীলিত প্রমাণ কৌশল, পুনরাবৃত্তিমূলক স্কেলিং যুক্তি ইত্যাদি উদ্ভাবনী কৌশল ব্যবহার করা
  3. প্রয়োগ মূল্য: তিনটি প্রয়োগ পরিস্থিতি সবই গুরুত্বপূর্ণ ব্যবহারিক তাৎপর্য রয়েছে, ফ্রেমওয়ার্কের সার্বজনীনতা প্রদর্শন করে
  4. লেখার স্পষ্টতা: ভাল কাঠামো, 3 টাইমস্কেল থেকে শুরু করে N টাইমস্কেলে সাধারণীকরণ, বোঝা সহজ করে

অপূর্ণতা

  1. অনুমান সীমাবদ্ধতা: i.i.d. নমুনা অনুমান বাস্তব RL তে অত্যন্ত সীমাবদ্ধ
  2. পরীক্ষার স্কেল: পরীক্ষা তুলনামূলকভাবে সহজ, বড় আকারের জটিল পরিবেশে যাচাইকরণের অভাব
  3. গণনা জটিলতা: তাত্ত্বিক শর্ত যাচাইকরণের গণনা জটিলতা আলোচনা করা হয়নি
  4. ব্যবহারিক নির্দেশনা: টাইমস্কেল বিচ্ছেদ পরামিতি কীভাবে নির্বাচন করতে হয় সে সম্পর্কে নির্দিষ্ট নির্দেশনার অভাব

প্রভাব

  1. তাত্ত্বিক অবদান: মাল্টি-টাইমস্কেল অ্যালগরিদম ডিজাইনের জন্য দৃঢ় তাত্ত্বিক ভিত্তি প্রদান করা
  2. ব্যবহারিক মূল্য: জটিল RL অ্যালগরিদমের সংযোগ বিশ্লেষণ সম্ভব করা
  3. অনুপ্রেরণামূলক: আরও মাল্টি-টাইমস্কেল অ্যালগরিদম গবেষণা অনুপ্রাণিত করতে পারে
  4. পুনরুৎপাদনযোগ্যতা: তাত্ত্বিক ফলাফল যাচাইযোগ্য, পরীক্ষা সেটআপ স্পষ্ট

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

  1. সীমাবদ্ধ শক্তিশালী শিক্ষা: প্রাথমিক-দ্বৈত আপডেট পরিচালনা করার প্রয়োজন এমন পরিস্থিতি
  2. শ্রেণিবদ্ধ শক্তিশালী শিক্ষা: বহু-স্তরের সিদ্ধান্ত বিভিন্ন টাইমস্কেল প্রয়োজন
  3. গতিবেগ ত্বরণ পদ্ধতি: RL তে গতিবেগ কৌশলের জন্য তাত্ত্বিক সমর্থন প্রদান করা
  4. অ্যালগরিদম ডিজাইন: নতুন মাল্টি-টাইমস্কেল অ্যালগরিদমের জন্য সংযোগ যাচাইকরণ সরঞ্জাম প্রদান করা

তথ্যসূত্র

এই পেপারটি প্রধানত নিম্নলিখিত গুরুত্বপূর্ণ কাজের উপর ভিত্তি করে:

  1. Borkar, V.S. (2008). Stochastic Approximation: A Dynamical Systems Viewpoint
  2. Lakshminarayanan, C. & Bhatnagar, S. (2017). A stability criterion for two-timescale stochastic approximation schemes
  3. Sutton, R. et al. (2009). Fast gradient-descent methods for temporal-difference learning with linear function approximation

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