# Paper Summary
## An Efficient Hardware Implementation of Reinforcement Learning: The Q-Learning Algorithm
### Garis Besar
* Bagian 1
survei singkat terhadap RL dan aplikasinya. Algoritma Q-Learning, dan menghadirkan literatur terkait
* Bagian 2
mendeskripsikan hardware arsitektur yang diusulkan oleh penulis yang menjelaskan blok fungsional. Teknik untuk mengurangi kompleksitas hardware dari operasi aritmetik juga diusulkan
* Bagian 3
menghadirkan hasil implementasi dan perbandingan dengan referensi yang dihadirkan oleh paper ini
* Bagian 4
menghadirkan konsiderasi terakhir dan perkembangan di masa depan
* Lampiran
menunjukkan bagaimana arsitektur dapat dieksploitasi untuk mengimplementasikan SARSA (State-Action-Reward-State-Action) algoritma RL dengan modifikasi minor
### Latar Belakang
RL merupakan pendekatan machine learning untuk melatih entity yg disebut agent untuk menyelesaikan suatu tugas dan tidak seperti pendekatan ML lainnya RL tidak memerlukan fasa training dan interference karena berdasarkan pendekatan trial dan error. Konsep ini sangat dekat dengan cara manusia belajar.

Agent berada di environment untuk melakukan suatu action. Action tersebut bisa mempengaruhi environment yang time-variant dan bisa dimodelkan dengan Markovian Decision Process. Suatu interpreter mengamati skenario yang memberikan state dari environment ke agent. Reward adalah sebuah penggambaran baiknya action terakhir yang dilakukan oleh agent dan direpresentasikan sebagai angka positif atau negatif. Dari proses iterasi ini, agent mempelajari pemilihan action policy yang optimal untuk menyelesaikan tugasnya. Policy ini mengindikasikan yang mana yang menjadi action terbaik yang bisa dilakukan oleh agent ketika environmentnya berada di state tertentu. Hingga akhirnya, interpreter bisa diintegrasikan ke agent yang membenarkan dirinya sendiri.

Berkat pendekatan ini, RL merepresentasikan suatu tool yang kuat untuk menyelesaikan masalah yang skenario keberjalanannya tidak diketahui atau berubah terhadap waktu.

Baru-baru ini, aplikasi dari RL telah populer di berbagai bidang seperti robotik, IoT, power management, financial trading, dan telekomunikasi. Bidang penelitian lain di RL adalah sistem multi agent dan swarm sistem.

Aplikasi jenis ini membutuhkan platform komputasi yang kuat untuk bisa memproses data yang sangat banyak secepat mungkin dan dengan konsumsi daya yang sedikit. Untuk alasan ini, performa implementasi software sekarang menjadi batasan utama pada pengembangan lanjutan seperti sistem dan penggunaan hardware accelerator dengan FPGA atau ASIC yang bisa merepresentasikan suatu solusi efisien untuk implementasi algoritma RL.

Kontribusi utama dalam pekerjaan ini adalah sebuah hardware accelerator yang fleksibel dan efisien untuk algoritma Q-Learning. Sistem tersebut tidak terikat ke aplikasi spesifik, RL policy atau environment. Terlebih lagi, untuk devais khusus IoT, sebuah arsitektur versi daya rendah pada approximated multiplier dipresentasikan

### Algoritma Q-Learning
Q-Learning adalah satu dari algoritma RL yang paling umum digunakan dan termasuk ke kelas metode off-policy karena kekonvergenannya dipastikan oleh policy agent apapun. Itu berdasarkan konsep Quality Matrix (Q-Matrix). Besar dari matriks ini adalah NxZ dengan N adalah jumlah state agent untuk merasakan environment dan Z adalah jumlah action yang agent mungkin lakukan. Ini berarti Q-Learning beroperasi di ruang state-action diskrit SxA. Mempertimbangkan sebuah baris pada Q-Matrix yang merepresentasikan sebuah state tertentu, action yang paling baik yang akan dilakukan dipilih dari mengkomputasikan value maksimmum pada baris.

Pada awal proses training, Q-Matrix diinisialisasi dengan value nol atau acak, dan diperbarui dengan menggunakan persamaan 

Pada referensi lainnya dibuktikan bahwa pengetahuan tentang Q-Matrix cukup untuk diambil action-selection policy optimal untuk agent RL.

### Penelitian Terkait
Meskipun ketertarikan terhadap RL meningkat dan kebutuhan terhadap sistem yang mampu untuk memproses banyak data dalam waktu singkat, hanya sedikit literatur penelitian yang bisa ditemukan terkait implementasi hardware dari algoritma RL. Terlebih lagi, perbandingan yang sangat sulit karena kurangnya detil implementasi dan tolak ukur homogen. Pada bagian ini paper menunjukkan penelitian terkemuka di bidang ini.

### Arsitektur yang Diusulkan
Q-Learning agent terdiri dari dua blok utama yaitu: Policy Generator (PG) dan Q-Learning accelerator.
agent menerima state berikutnya dan reward berikutnya dari observer, ketika action berikutnya di generasikan dengan PG berdasarkan value dari Q-Matrix yang tersimpan ke Q-Learning accelerator.

Perlu dicatat bahwa state, action, dan reward saat ini didapat dengan mendelay state, action, dan reward yang akan datang. State dan Action direpresentasikan dengan indeks dari baris dan kolom Q-Matrix, berturut-turut. Delay tersebut tidak mempengaruhi kekonvergenan dari algoritma Q-Learning.

Dengan tujuan untuk mendesain suatu hardware accelerator umum, paper tidak memberikan implementasi spesifik untuk PG. PG hanya pada eksperiman untuk perbandingan dengan referensi lainnya.


Q-Matrix disimpan pada Z Dual-Port RAMs yang bernama Action RAMs. Alhasil, paper hanya memiliki sebuah blok memori per action. Setiap RAM mengandung seluruh kolom dari Q-Matrix dan jumlah memory location sesuai dengan jumlah state N. read address adalah state berikutnya, sedangkan write address adalah state saat ini. Sinyal enable untuk Action RAMs, digenerasikan dengan suatu decoder yang diatur oleh action saat ini, memilih value Q(s,a) untuk diperbarui. Output Action RAMs sesuai dengan baris dari Q-Matrix Q(S+1, A).

Sinyal Q(s,a) diperoleh dengan mendelay output dari blok memori kemudian memilih action RAM melalui multiplexer yang diatur oleh a. Sebuah blok MAX diberikan input oleh output dari Action RAMs yang menggenerasikan Q(s+1,a)

Blok Q-Updater mengimplementasikan persamaan perbaruan Q-Matrix yang menggenerasikan Qbaru(s,a) untuk disimpan ke Action RAM yang sesuai.

Accelerator tersebut bisa digunakan untuk aplikasi Deep Q-Learning jika Action RAMs diganti dengan Neural Network-based approximator.

### Blok Max

Pada paper, penulis membuktikan bahwa delay propagasi blok ini adalah batasan utama untuk kecepatan Q-Learning accelerator ketika banyak action dibutuhkan. Alhasil diusulkan implementasi berdasarkan tree of binary komparator yang merupakan trade-off baik di besar dan kecepatan.

Terlebih lagi, pipelining digunakan untuk mempercepat blok mAx, latensi tidak berpengaruh terhadap kekonvergenan dari algoritma Q-Learning. Oleh karena itu, ketika aplikasi membutuhkan keluaran yang sangat tinggi sehingga mungkin untuk menggunakan pipelining.

### Blok Q-updater

Persamaan berikut
diperoleh untuk mendapatkan implementasi efisien. Persamaan tersebut dikomputasikan dengan 2 multiplier, sedangkan persamaan sebelumnya menggunakan 3 multiplier.

Critical path meliputi 2 multiplier dan 2 adder yang bisa dioptiimalisasikan lebih lanjut dengan metode selanjutnya.

### Multiplier Aproksimasi
Batasan utama kecepatan pada blok updater adalah propagasi delay dari multiplier. multiplier dapat digantikan dengan multiplier aproksimasi berdasarkan barrel shifter. Dengan cara ini, kita mengaproksimasikan alpha dan gamma dengan angka yang sama dengan pangkat dua terdekat (single shifter), atau dengan jumlah pangkat dua terdekat (dua atau lebih shifter). Karena alpha, gamma diantara 0 dan 1, hanya right shift yang digunakan.

Mempertimbangkan sebuah angka x kurang dari sama dengan 1, representasi binernya menggunakan M bit untuk bagian fraksional adalah:
Lalu diaproksimasikan x dengan n pangakat dua tertinggi pada representasi bit M+1 yang merupakan
dengan aproksimasi dengan satu, dua, dan tiga pangkat dari dua. Konsep dapat diekstensi hingga lebih dari dua pangkat.

Multiplier aproksimasi diimplementasikan dengan satu atau lebih barrel shifter di blok Q-Updater tergantung dari aproksimasi.

Posisi dari i dan j yang mendahului di representasi alpha dan gamma dapat diberikan sebagai input jika konstanta untuk komputasi seluruhnya atau ditentukan oleh Leading-One-Detector jika value diubah ketika runtime

Galat diperkenalkan dengan aproksimasi ini tidak mempengaruhi kekonvergenan dari algoritma Q-learning dan sebagai efek samping didapatkan critical path yang lebih pendek dan yang lebih irit daya. Lalu, sistem diuji di aplikasi yang berbeda yang membuktikan hampir tidak sensitif terhadap galat aproksimasi karena kondisi kekonvergenan dari Q-learning masih dipenuhi (alpha, gamma <= 1)

Dengan mengguanakan multiplier aproksimasi, dapat dihindari penggunaan FPGA dengan blok DSP dan dapat diimplementasikan accelerator pada ultra low power FPGA kecil yang cocok untuk aplikasi IoT.

### Eksperimen Implementasi

Pada eksperimen digunakan Xilinx Zynq UltraScale+ MPSoC ZCU106 kit evaluasi dengan XCZU7EV-2FFVC1156 FPGA. Seluruh hasil dari bagian ini didapatkan dengan Vivado 2019.1 EDA tool dengan parameter implementasi bawaan dan mengatur timing constraint menjadi 2 ns. Sistemnya diprogram di VHDL.

Eksplorasi desain diimplementasikan dengan mengikuti parameter berikut:
* Jumlah bit dari Q-Matrix values : 8, 16, 32 bit
* Jumlah state N : 8, 16, 32, 64, 128, dan 256
* Jumlah action Z : 4, 8, dan 16

Fokus analisis implementasi menggunakan resource berikut:
* Look Up Tables
* Look Up TAbles used as RAM
* Flip-Flop
* Digital Signal Processing slices

Untuk setiap resource dari devais, diberikan usage persen yang mengikuti total tersedia.

Performa dapat diukur dengan CLK maksimum dan konsumsi daya dinamis yang dievaluasi dengan menggunakan Vivado setelah Place&Route memerhatikan maksimum CLK dan skenario terburuk dengan 0.5 faktor aktivitas pada simpul rangkaian.

Seluruh contoh implementasi tidak menggunakan pipelining pada blok MAX. Kecuali dinyatakan, tanpa menggunakan aproksimasi multiplier.


Arsitektur yang diusulkan dalam paper ini telah dibandingkan dengan salah satu accelerator hardware Q-Learning berkinerja terbaik saat ini

Pendekatan paper menghasilkan arsitektur yang lebih kecil. Perbedaan penting terdiri dari pemilihan nilai matriks-Q sebelumnya yang akan diperbarui. Hal ini memungkinkan untuk mengimplementasikan satu blok untuk perhitungan Qnew = (st, at), sedangkan di paper lainnya blok N × Z diperlukan. Lebih-lebih lagi, dalam hal implementasi FPGA, arsitektur ini memungkinkan untuk menggunakan distributed RAM atau Embedded block RAM. Ini memberikan tingkat kebebasan tambahan dibandingkan dengan paper lainnya di mana hanya register yang dipertimbangkan untuk menyimpan nilai Q-Matrix.

Untuk mendapatkan perbandingan yang sesuai:
* Diterapkan environment RL yang sama dari dan menyimpan value reward dalam Tabel Pencarian.
* Diterapkan PG acak seperti yang dijelaskan dalam.
* Dipertimbangkan v Q-Matrix 16-bit.
* Diimplementasikan arsitektur pada Virtex-6 yang sama Kit Evaluasi FPGA ML605 (menggunakan ISE 14.7 Xilinx rangkaian).


### Kesimpulan
Pada paper tsb diusulkan sebuah hardware implementasi efisien untuk algoritma RL yang disebut dengan Q-Learning. Arsitektur tersebut menggunakan persamaan pembelajaran dengan a-priori memilih elemen yang dibutuhkan agar Q-matrix diperbarui. Pendekatan ini bisa didapatkan untuk meminimalisir kebutuhan hardware.

Metode alternatif dapat diusulkan untuk mengurangi kompleksitas komputasi dari algoritma dengan menggunakan multiplier aproksimasi. Teknik ini merupakan solusi efektif untuk mengimplementasikan accelerator pada ultra low power FPGA kecil untuk aplikasi IoT.

Arsitektur ini telah dibandingkan dengan referensi lain pada literatur, yang menunjukkan bahwa solusi membutuhkan kebutuhan hardware yang lebih sedikit, lebih cepat dan mendisipasikan daya rendah. lalu, sistemnya bisa digunakan sebagai hardware accelerator umum untuk algoritma Q-Learning, tidak berhubungan dengan environment RL khusus atau policy dari agent.

Dengan effort kecil, pendekatan yang diusulkan dapat digunakan untuk mengimplementasikan versi on-policy untuk algoritma Q-Learning: SARSA.

Untuk alasan diatas, arsitektur ini cocok untuk keluaran tinggi dan aplikasi irit daya. Karena resource yang dibutuhkan sedikit memungkinkan untuk mengimplementasikan banyak Q-Learning agent pada devais yang sama, pada FPGA atau ASIC.

## Parallel Implementation of Reinforcement Learning Q-Learning Technique for FPGA
### Garis Besar
Q-learning merupakan teknik off-policy reinforcement learning, yang memiliki kelebihan utama dengan memperoleh policy optimal yang berinteraksi dengan environment model yang tidak diketahui. Paper mengusulkan sebuah pararel fixed-point algoritma Q-learning arsitektur yang diimplementasikan pada FPGA yang berfokus pada optimisasi waktu proses sistem. Hasil kekonvergenan ditunjukkan dan waktu proses dan luas okupasi dianalisis untuk state yang berbea dan besar action skenario dan berbagai format fixed-point. Studi terkait akurasi teknik Q-learning respon dan galat resolusi terkait dengan berkurangnya jumlah bit yang juga dibawa keluar untuk implementasi hardware. Arsitektur implementasi detil juga ditampilkan. Seluruh proyek dikembangkan menggunakan sistem generator platform (Xilinx), dengan Virtex-6 xc6vcx240t-1ff1156 sebagai target FPGA.

### Latar Belakang
RL merupakan AI formalitas yang mempersilahkan agent untuk mempelajari interaksi dengan environment ketika dimasukkan. Pendekatan ini mengindikasikan situasi dengan tanpa informasi yang cukup tentang perilaku agent yang harus dilakukan untuk mencapai objective, yaitu agent tanpa pengetahuan sebelumnya mempelajari interaksi dengan environment, dengan menerima reward untuk action dan penemuan policy yang optimal.

Perkembangan Q-Learning pada teknik RL pada hardware membiarkan mendesain sistem yang lebih cepat dibanding software yang ekivalen, sehingga membuka kesempatan penggunaanya pada masalah konstrain waktu singkat dan/atau memproses data yang banyak. Dimungkinkan untuk mengurangi konsumsi daya dengan mengurangi clock cycle pada aplikasi dengan kecepatan proses tidak relevan atau kurang membatasi dibandingkan kebutuhan konsumsi daya rendah. Algoritma navigasi pada aplikasi robotika mobile, secara umum, respons pada ratusan milisekon dan properti ini memungkinkan solusi pada hardware yang terdedikasi pada suatu proyek dengan clock frekuensi rendah mempertimbangkan solusi software lain yang tertanam pada micro-controller dan microprocessor.

### Kontribusi Utama
Penelitian ini menghadirkan kontribusi hardware dengan arsitektur pararel di FPGA dengan teknik Q-Learning RL. Ide utama adalah berdasarkan perkembangan sebuah arsitektur yang modular dan pararel untuk memungkinkan bertambahnya kecepatan algoritma eksekusi atau mengurangi konsumsi daya dengan mengurangi frekuensi clock. Properti intrinsik dari FPGA seperti fleksibilitas dan pemrosesan pararel yang merupakan dasar dalam meraih tujuan ini. Pararelisasi dari aliran data pada FPGA memungkinkan teknik Q-Learning untuk digunakan pada aplikasi dengan aliran data signifikan dan batasan waktu pemrosesan yang ketat. Aplikasi lain dengan arsitektur ini adalah sistem konsumsi rendah, dengan clock sistem yang dikurangi dengan cara mengurangi konsumsi daya

### Implementasi
Arsitektur ini terdiri dari 5 modul utama yaitu, modul GA yang berfungsi untuk memilih action secara acak, modul EN yang berfungsi untuk menyimpan nilai reward, modul S yang berfungsi untuk menghitung nilai dari Q value function, lalu modul SEL yang merupakan tempat state yang akan datang dipilih dan penyimpanan dari fungsi Q value dibuat.
* GA - Pengambilan Action
Agar algoritma menuju sifat yang konvergen diperlukan setiap pasangan state dan action dicoba dengan jumlah yang banyak. Oleh karena itu diperlukan generator angka acak yang pada implementasi ini digunakan Pseudo Random Number Generator (PRNG) dengan persamaan 
dengan nilai P1 dan P2 adalah konstanta, ak merupakan bilangan bulat dari 0 hingga Z-1 dan ak-1 adalah nilai dari ak sebelumnya (dari PRNGnya). Arsitekturnya digambarkan oleh
operasi modulo dilakukan dengan fungsi multiplier intrinsik overflow, wrap-around. Namun masalah dapat muncul jika jumlah action yang mungkin bukan kelipatan dua. Untuk menghadapi ini digunakan
dengan Nomax (jumlah kombinasi yang mungkin) jauh lebih banyak dari jumlah action yang diinginkan. Jika angka yang didapat diantara 0 dan C1 action ak akan menjadi ak0. Pada kasus angka diantara C1 dan C2 action ak1 dan seterusnya hingga nilai lebih dari Cz-1 yaitu ketika action akz-1. Pembagian ini dibuat dengan mengguanakn komparator dan logika kombinasional.
Setelah setiap pasangan action-state ditentukan di tiap iterasi diketahui elemen fungsi matrix Qk yang mana yang harus diperbarui. Karena action dipilih secara acak arsitektur melakukan hanya eksplorasi dari environment dengan agent untuk memperoleh policy optimal dan tidak peduli dengan eksploitasi
* EN - Modul Perbaruan
modul perbaruan yang disebut dengan EN berfungsi untuk memilih pasangan state-action yang mana yang akan diperbarui. Nilai dari setiap value function Qk pasangan action-state disimpan di register NxZ dengan input enable mereka terhubung dengan output dari modul EN. Oleh karena itu, fungsi value diperbarui hanya ketika salah satu elemen dari vektor uk pada level logika yang tinggi
* RS - Modul Fungsi dari Reward
modul N tempat penyimpanan reward atau reinforcement secara langsung yang direpresentasikan oleh matriks rn yang merupakan vektor dari elemen sebanyak Z
Setiap modul RS ke n memiliki konstanta Z, rn,z yang merupakan action Z dari setiap state ke n. Setiap rn,z ke z mengandung sebuah word dari bit B. Action yang menuju pada state target memiliki reward positif dan action yang tidak diinginkan memperoleh reward negatif. Action yang mengarah pada state lain mendapatkan reward 0
* S- Modul Perhitungan Fungsi dari Value
Berdasarkan gambar dibawah (arsitektur hardware Q-Learning) dipararelkan berdasarkan statenya. modul state ke n, Sn, dibagi menjadi dua modul fungsi yang berbeda.
Pada modul SFn, state yang akan datang, sk+1n ditentukan secara lokal dari informasi penentuan action saja yatu akz. Pada modul Qn perhitungan elemen Qkn dilakukan dan fungsi value yang bersesuaian dengan action dengan nilai tertinggi maxQn ditentukan untuk state ke-n
* SEL - State yang akan Datang
Pada modul ini ditentukan informasi pararel yang dikomputasi sebelumnya yang akan menjadi state selanjutnya yang akan dieksplorasi oleh arsitekturnya.
untuk menentukan Sk+1 seluruh state yang akan datang dari modul N Sn diletakkan di MUX2 multiplexer yang memilih state sekarang. State yang akan datang akan diberikan kembali ke awal arsitektur dan menjadi state untuk iterasi selanjutnya.
Sk+1 digunakan sebagai selector pada MUX3 yang memiliki input sebanyak action N dengan nilai tertinggi dari state N dari amaxQn dikali dengan time discount factor gamma dan dikembalikan ke input dari modul Sn untuk perhitungan dari vektor Qn.

### Hasil Simulasi
Skenario yang digunakan adalah sebuah robot bergerak di suatu arena, memiliki tujuan untuk mencapai daerah tertentu. Jumlah statenya adalah detil lengkap dari arenanya, action adalah kemungkinan gerakan robot. Arena terbagi menjadi 6 daerah (s1, s2, s3, s4, s5, dan s6) dan robot memiliki 4 kemungkinan action (atas, bawah, kiri, kanan) yang diilustrasikan oleh gambar di bawah
Dibuat S6 sebagai tujuan atau goal dari algoritma sehingga action yang langsung menunjukkan pada S6 akan mendapatkan reward 100. Lalu action yang menyebabkan robot keluar dari arena menyebabkan reward -500. Matriks reward direpresentasikan dengan
Lalu matriks fungsi value dengan nilai floating-point IEEE 754 standard ditunjukkan berikut
Lalu hasil dari simulasi arsitektur hardware ditunjukkan sebagai berikut
Simulasi dengan digital fixed-point representation pada 4 skenario yang berbeda, yang pertama 24 bit digunakan, 14 bit untuk biner, yang kedua 20 bit 10 bit untuk biner, yang ketiga 16 bit 6 bit untuk biner, dan 12 bit 2 bit untuk biner. Dengan simulasi dapat ditentukan policy optimal dengan bit yang digunakan semakin sedikit galat semakin besar (galat resolusi). Namun jika policy optimal didefinisikan maka tidak penting resolusi Qmatrixnya.

9 Skenario lain juga dianalisis dengan jumlah state dan action yang berbeda. Skenario juga digambarkan dengan masalah robot yang bergerak di arena. Semakin besar detil arenasemakin banyak juga statenya. Hasilnya didapatkan untuk Xilinx Virtex-6 FPGA.

Berikut adalah parameter sintesis

9 kasus skenario dijelaskan pada tabel berikut

Berikut tabel yang menggambarkan hasil yang didapatkan berdasarkan rate occupancy dan throughput dalam Mega sample per second atau mega iteration per second. Kolum pertama adalah resolusi bi yang dihasilkan untuk variabel r dan Q sedangkan variabel lainnya tetap.




Daya dinamis sebagai fungsi dari jumlah bit untuk setiap skenario ditunjukkan pada grafik berikut

Konsumsi daya sebagai fungsi dari besar matrix Q (NxZ) dan throughput (grafik bar disamping) dan jumlah bit (besar dari lingkaran) ditunjukkan pada grafik berikut

Hasil komparatif

### Kesimpulan
Meskipun digunakan resource yang cukup banyak (untuk setiap elemen pada matriks) diperlukan tambahan resource, jika dibandingkan dengan paper 1 tetap masih lebih lambat. Hal ini karena, hal yang perlu dipercepat hanyalah critical path, yaitu blok perkalian dll. Terlebih lagi, karena resource yang digunakan banyak dan secara pararel maka daya yang dibutuhan juga sangat tinggi. Namun, pada implementasi ini tidak digunakan memory karena data dialirkan secara langsung.