Α reinforcement learning approach on matrix triangularization using rotations

Abstract

Σε αυτήν τη διπλωματική εργασία θα μελετήσουμε λεπτομερώς τον μετασχηματισμό Householder, τις περιστροφές Givens, τις περιστροφές Cordic Givens, τον αλγόριθμο Gram-Schmidt και την τροποποιημένη έκδοσή του. ́Ολες αυτές οι μέθοδοι στις οποίες αναφερθήκαμε μέχρι στιγμής είναι μέθοδοι για την παραγοντοποίηση QR με διαφορές σε πολυπλοκότητα και σφάλμα. Επίσης θα συζητήσουμε για την βασική θεωρία της ενισχυτικής μάθησης και θα εξερευνήσουμε τις διαφορές μεταξύ αλγορίθμων όπως ο SARSA και ο Q-Learning. Στο κεφάλαιο των πειραματισμών θα σχεδιάσουμε την παραγοντοποίηση QR σαν ένα επιτραπέζιο. Με τη χρήση ενισχυτικής μάθησης και συγκεκριμένα του Q-Learning αλγορίθμου θα οδηγήσουμε τις περιστροφές Givens σε εναλλακτικά μονοπάτια για τον αλγόριθμό μας, όπου για συγκεκριμένες εισόδους πινάκων θα οδηγηθούν στη παραγοντοποίηση QR σε λιγότερες επαναλήψεις.

In this thesis, we will discuss in detail about Householder transformation, Givens rotations, Cordic Givens rotations and Gram-Schmidt, along with its modified variant. All of the mentioned methods are QR decomposition methods with differences in complexity and error. Furthermore, we will discuss about the basic theory of Reinforcement Learning and explore the differences between algorithms such as SARSA and Q-Learning. In the experimentation section we will design the QR decomposition as a board game. With the use of Reinforcement Learning and specifically the Q-Learning algorithm we will guide the Givens rotation into alternative paths for our algorithms, that in specific matrix input cases can reach the QR decomposition state in less iterations.