# NormTab: Improving Symbolic Reasoning in LLMs Through Tabular Data
Normalization

Md Mahadi Hasan Nahid
University of Alberta
<EMAIL_ADDRESS>Davood Rafiei
University of Alberta
<EMAIL_ADDRESS>
###### Abstract

In recent years, Large Language Models (LLMs) have demonstrated remarkable
capabilities in parsing textual data and generating code. However, their
performance in tasks involving tabular data, especially those requiring
symbolic reasoning, faces challenges due to the structural variance and
inconsistency in table cell values often found in web tables. In this paper,
we introduce NormTab, a novel framework aimed at enhancing the symbolic
reasoning performance of LLMs by normalizing web tables. We study table
normalization as a stand-alone, one-time preprocessing step using LLMs to
support symbolic reasoning on tabular data. Our experimental evaluation,
conducted on challenging web table datasets such as WikiTableQuestion and
TabFact, demonstrates that leveraging NormTab significantly improves symbolic
reasoning performance, showcasing the importance and effectiveness of web
table normalization for enhancing LLM-based symbolic reasoning tasks.

NormTab: Improving Symbolic Reasoning in LLMs Through Tabular Data
Normalization

Md Mahadi Hasan Nahid University of Alberta<EMAIL_ADDRESS>Davood Rafiei
University of Alberta<EMAIL_ADDRESS>

##  1 Introduction

Tables are a fundamental format for structured data representation and are
widely used across various sources, including relational databases, web pages,
and financial documents. However, many tables within documents and web pages
are designed for direct human consumption and often lack the strict formatting
that is expected in relational tables. This discrepancy poses significant
challenges when querying them using languages such as SQL, integrating them
with relational databases, and processing them within applications.

Large Language Models (LLMs) (Brown et al., 2020) have emerged as powerful
tools for semantic parsing both textual and tabular data and performing
complex tasks such as code generation. Trained on vast amount of Internet
data, including both text and tables, and employing techniques such as Chain
of Thought (CoT) prompting (Wei et al., 2022) and self-consistency (Wang et
al., 2023), these models outperform many traditional models on various table
reasoning tasks (Gu et al., 2022; Chen et al., 2020; Herzig et al., 2020; Wang
et al., 2019). However, their performance in tasks involving tabular data,
particularly those requiring symbolic reasoning, is often hindered by the
structural variability and inconsistencies commonly found in web tables.
Symbolic reasoning over tables necessitates a clear understanding of the table
structure and values, and may involve constraining rows and columns, which can
be challenging when dealing with unstructured or noisy web tables (Pourreza
and Rafiei, 2023; Ni et al., 2023; Cheng et al., 2022; Zhang et al., 2023b).
Our hypothesis is that normalizing ill-formatted tables can address this
challenge, enabling the execution of symbolic programs (such as SQL or Python)
on the tables and making reasoning tasks involving comparison, aggregation,
and mathematical calculations more manageable. Moreover, normalization may
enhance the explainability by allowing the tracking of the intermediate steps
in reasoning.

Figure 1: An example of a Table QA task, with the original unnormalized web
table shown on the left and its normalized version on the right. Retrieve
answers using a symbolic approach from the unnormalized table poses
difficulties due to inconsistent formatting of date, result and attendance
columns. Also, direct querying with LLMs often fails for questions involving
numerical operations. Normalization enables effective text-to-SQL conversion,
as shown by the normalized table on the right.

Consider the table QA task shown in Figure 1. Retrieving answers from the
table on the left using a symbolic approach such as SQL is challenging due to
the irregular structure of the data and the limitations of SQL. While an LLM
may handle simple look-up questions, it struggles with tasks requiring complex
aggregation and arithmetic operations. However, the normalized version of the
same table, shown on the right, can be easily analyzed, allowing text-to-SQL
approaches to effectively obtain the answers to questions.

Existing models for table reasoning typically rely on a multi-step framework,
where an LLM performs a sequence of actions such as adding columns before
additional scripts are invoked to process data, retrieve cell values, or
compute answers to questions (Liu et al., 2023; Wang et al., 2024; Zhang et
al., 2023b). These models are often dependent on question and table structure
and do not address the root cause of table irregularity, making them less
scalable. An alternative is normalizing tables, often part of a larger process
known as data wrangling, which involves processing, cleaning and organizing
data into a format that is suitable for further analysis. Significant progress
has been made on data wrangling (Furche et al., 2016; Abedjan et al., 2016;
Rattenbury et al., 2017), with recent approaches employing LLMs for tasks such
as error detection and data imputation (Narayan et al., 2022). Selected
operations, such as normalizing numbers and dates, may also be introduced into
data processing pipelines to facilitate further analysis (Nahid and Rafiei,
2024). To the best of our knowledge, our work is the first to study table
normalization as an stand-alone one-time preprocessing step using LLMs.

In this paper, we introduce NormTab, a framework designed to normalize web
tables to align them with the structured format of relational database tables.
NormTab addresses challenges such as structural variance, mixed data formats,
and extraneous information, thereby facilitating accurate and efficient
symbolic reasoning and query processing using LLMs. Our work explores two key
research questions:

  * •

RQ1: How can we leverage LLMs’ textual understanding to effectively clean and
normalize web tables?

  * •

RQ2: How can web table normalization enhance table reasoning tasks,
particularly in the context of LLM-based symbolic reasoning?

Our proposed solution leverages the advanced textual understanding
capabilities of LLMs to independently process and normalize web tables,
without relying on specific questions. By normalizing tables in this manner,
we enable a robust foundation for any downstream task involving table
reasoning. This approach allows for multiple questions to be asked from a
single, normalized table, significantly enhancing reasoning and query
capabilities. Moreover, our normalization process only needs to be performed
once, unlike other models that require repeated adjustments based on different
questions, highlighting a key advantage of our approach.

Through a comprehensive experimental evaluation conducted on challenging web
table datasets such as WikiTableQuestions (Pasupat and Liang, 2015) and
TabFact (Chen et al., 2020), we assess the effectiveness of NormTab in
improving table reasoning performance. These datasets provide diverse examples
of table structures and content, allowing us to thoroughly investigate the
impact of web table normalization on LLM-based symbolic reasoning tasks. By
addressing RQ1 and RQ2, we aim to demonstrate the importance of web table
normalization and its potential to enhance the capabilities of LLMs in
handling tabular data for complex reasoning tasks.

Key Contributions of our paper are:

  * •

We introduce NormTab, a novel framework that enhances LLMs’ symbolic reasoning
on tabular data by normalizing web tables. NormTab includes structure
normalization (e.g., transposing tables, flattening rows and columns) and
value normalization (e.g., removing extraneous strings, standardizing the
formatting of dates and numbers) to ensure consistency and accuracy in
reasoning tasks.

  * •

We demonstrate how LLMs’ textual understanding can be effectively utilized for
data cleaning and transformation tasks, addressing challenges such as
structural variance, mixed values, noise, and substring extraction in web
tables

  * •

We conduct extensive experimental evaluations using challenging web table
datasets, including WikiTableQuestion and TabFact, to assess the effectiveness
of NormTab in improving table reasoning performance, particularly in the
context of LLM-based symbolic reasoning tasks.

Figure 2: Overview of NormTab. The methodology encompasses two distinct
strategies: (a) Entire Table Normalization (NormTabBasic): we provide the LLM
with the entire web table along with specific instructions for cleaning and
normalizing. The LLM reads the table and the instructions, then returns a
cleaned and normalized version of the table. (b) Targeted Normalization
(NormTabTargeted): In this approach the LLM identifies and targets only the
portions of the web table requiring normalization based on the table metadata
and a few sample rows. The original table is split into two subtables: one for
normalization and one already clean. The LLM processes the subtable that
requires normalization then returned a cleaned version. Finally, the
normalized subtable is merged with the clean portion, resulting in a fully
cleaned and normalized table.

##  2 Related Work

Our work is related to a few areas as discussed next.

General LLMs and CoT Related to our work is the line of research aimed at
improving the performance of LLMs Brown et al. (2020) on various reasoning
tasks, with capabilities spanning mathematics, common sense, and symbolic
reasoning (Chen, 2023; Ye et al., 2023; Cheng et al., 2022). These approaches
often excel using few-shot prompts without requiring fine-tuning. Their
reasoning abilities can be further enhanced by breaking complex tasks into
steps, employing methods like chain-of-thought (CoT) Wei et al. (2022)
prompting and Zero-CoT. For instance, the Table-CoT (Chen, 2023) model
utilizes in-context learning and CoT prompting to generate answers for table-
based tasks.

Several studies have utilized instruction tuning and supervised fine-tuning to
enhance the performance of LLMs on table reasoning tasks. Notable examples
include TableLLaMA (Zhang et al., 2023a) and TableGPT (Zha et al., 2023),
which have shown significant improvements in specific applications. In
contrast, the BINDER model (Cheng et al., 2022) extends the capabilities of
LLMs to programming language generation for solving commonsense problems.
Additionally, the DATER approach (Ye et al., 2023) employs LLMs to decompose
tables and questions, facilitating table-based QA and fact verification tasks.
These diverse approaches underscore the potential of LLMs in handling complex
reasoning tasks involving tabular data.

Reasoning over structured data/tables  Another line of related work is
reasoning over tabular data. Several studies leverage symbolic reasoning
through text-to-SQL or Python code for table-based reasoning tasks. However,
for effectively utilizing the symbolic code generation approach with LLMs for
table reasoning tasks, it is crucial to ensure that the table is in the proper
format (Pourreza and Rafiei, 2023; Rajkumar et al., 2022; Ni et al., 2023;
Nahid and Rafiei, 2024; Cheng et al., 2022).

Chain-of-Table (Wang et al., 2024) enhances reasoning on tabular data by
iteratively transforming and evolving table structures through a series of
reasoning steps, including row/column selection, cell splitting to refine
table representations for specific reasoning tasks. Their method employs in-
context learning to direct LLMs in iteratively generating operations and
updating the table, thus forming a chain of reasoning specific to tabular
data. Liu et al. (2023) explore the capabilities of LLMs in interpreting and
reasoning over tabular data, emphasizing robustness to structural
perturbations, comparing textual and symbolic reasoning, and examining the
potential of aggregating multiple reasoning pathways. Their findings indicate
that structural variations in tables presenting the same content can
significantly degrade performance, particularly in symbolic reasoning tasks.
They propose a method for table structure normalization through transposition
to mitigate this issue and find that while textual reasoning slightly
outperforms symbolic reasoning, each approach has distinct strengths depending
on the task.

StructGPT (Jiang et al., 2023) employs an iterative reading-then-reasoning
approach to enhance LLM reasoning for structured data, but its scalability is
constrained by token limits when processing large tables. The ReAcTable model
(Zhang et al., 2023b) adopts the ReAct paradigm, integrating step-by-step
reasoning, external tool-based code execution, intermediate table generation,
and majority voting to process tabular data. Similarly, the LEVER model Ni et
al. (2023) improves language-to-code generation by validating generated
programs based on their execution results, enhancing the accuracy and
reliability of table reasoning tasks.

Data wrangling and imputation Normalizing tables is a crucial aspect of the
broader data wrangling process, which involves processing, cleaning, and
organizing data into a format suitable for further analysis. Considerable
research has focused on data wrangling, addressing challenges such as error
detection, data imputation, and standardization of data formats (Furche et
al., 2016; Abedjan et al., 2016; Rattenbury et al., 2017). Recent approaches
have leveraged the capabilities of LLMs for these tasks. For instance, Narayan
et al. (2022) demonstrated the effectiveness of LLMs in identifying errors and
imputing missing data, showcasing how these models can enhance the data
wrangling process. By integrating LLMs, the efficiency and accuracy of
preparing data for analysis can be significantly improved, streamlining and
automating many aspects of data wrangling. Operations like normalizing numbers
and dates can be incorporated into data processing workflows to aid in
subsequent analysis (Nahid and Rafiei, 2024).

All these works highlight the importance of table normalization in improving
LLMs’ performance on tabular data, paving the way for more effective and
accurate table reasoning models.

##  3 Methodology

Our methodology encompasses several essential parts designed to ready web
tables for proficient reasoning by LLMs.

###  3.1 Normalization Operations

The normalization operations in NormTab can be divided into two groups: (1)
value normalization and (2) structural normalization. The former involves
splitting cells to add new columns, handling empty cells and value ranges,
removing extraneous strings, and normalizing data formats such as dates and
numerical values to ensure consistency and accuracy in reasoning tasks.
Structural normalization, on the other hand, aims to detect structural
variance by analyzing the first row and first column of a web table and
determining whether a transposition is needed. If transposition is required,
we address this issue by flipping the rows and columns.

Value Normalization: Our value normalization is based on the principle that
every cell in a table must contain an atomic value (e.g., string, date,
number), meaning that cell content cannot be composite or multi-valued. This
principle, known as the first normal form in database systems (Kifer et al.,
2005), ensures that cell values can be smoothly queried and updated without
introducing anomalies.

The process of value normalization involves several critical steps to ensure
data consistency and accuracy. First, we focus on value splitting and
extraction, identifying and splitting all composite columns. This may involve
adding new columns as necessary while ensuring that no existing columns are
deleted. Next, we standardize date and numerical values to a uniform format,
paying special attention to any additional strings such as currency symbols,
units or comma that may accompany numerical values. Additionally, we normalize
all “N/A” and blank values to NULL to maintain consistency throughout the
dataset. In SQL, Null values signify an attribute value that is not available
or missing, and they are treated differently than any other values. SQL
engines recognize the semantics of null values and consider this when
processing queries. For columns containing value ranges, such as “2010/11” or
“2015-2018”, we split these into two separate columns to facilitate clearer
data interpretation and processing.

An example of value normalization is shown in Figure 1. The original table
presents date columns with dates in textual format, a result column combining
match outcomes with scores, and an attendance column where numbers are written
with commas. The value representation in the original table is more readable
for humans; however, this format poses challenges for symbolic programs to
process. Our normalization process converts the date to the “YYYY-MM-DD”
format and attendance values to a pure numerical format by removing commas.
Additionally, NormTab splits the composite result column into two separate
columns: “result_type” and “result_score”, thereby organizing the data more
effectively for analysis. This standardization is crucial for maintaining data
integrity across the table.

Structural Normalization: Tables can be organized either row-oriented or
column-oriented. In a row-oriented table, each row typically represents an
entity or a relationship between entities, while each column describes an
attribute of the entity or relationship. Column-oriented tables, on the other
hand, are stored in a transposed fashion. Most traditional databases store
data in a row-oriented format, which is well-supported across relational
databases.

Our structure normalization primarily focuses on addressing structural
differences between tables to enhance their usability for reasoning tasks.
Initially, we carefully examine the table structure to determine if the first
row resembles a header, indicating the table is row-oriented and requires no
structural changes. However, if the first column appears to serve as the
header, we transpose the table to normalize its structure, ensuring that the
layout aligns with our adopted tabular format. Additionally, web tables
sometimes include aggregated rows or columns, which can pose challenges if
specific rows or columns need aggregation to answer a query. We handle these
aggregated rows by disregarding any information present in the last row that
pertains to aggregated data, such as “total”, “sum”, or “average”. This step
prevents redundant or misleading data from affecting subsequent analyses and
ensures that the table remains clean and focused on the relevant data points.

###  3.2 Normalization Approach: NormTab

As depicted in Figure 2, our methodology for normalizing web tables involves
two distinct approaches to leverage the capabilities of LLMs for enhancing
symbolic reasoning and query capabilities.

Entire Table Normalization (NormTab-Basic): In the first approach, we provide
the LLM with the entire table along with specific instructions for cleaning
and normalizing. The LLM reads the table and the instructions, then returns a
cleaned and normalized version of the table. However, we observed that many
web tables contain portions already in a well-structured form, with only a few
columns requiring normalization. To optimize this process, we developed a
modified approach.

Targeted Normalization(NormTab-Targeted): To improve efficiency, we developed
a modified approach that targets only the portions of the table requiring
normalization. Our analysis of web tables revealed that often only a few
columns need the normalization process. This realization led to a more
optimized methodology. In this more refined approach, we first ask the LLM to
identify which columns require normalization and cleaning, based on the table
metadata (such as column headers and titles) and a few sample rows. Once these
columns are identified, we split the original table into two subtables: one
that requires normalization and cleaning, and one that is already normalized
and clean. We then send only the subtable that needs normalization to the LLM
along with the instructions. The LLM processes this subtable and returns a
cleaned and normalized version. After normalization, we merge the normalized
subtable with the already clean portion of the table. This approach not only
improves the efficiency of the normalization task by reducing the amount of
data sent to the LLM but also ensures that the resulting table is in a
consistent and accurate format suitable for subsequent reasoning and querying
tasks.

Following this, we analyze the overall structure of the merged table. With the
assistance of the LLM, we determine whether the table needs to be transposed
based on its layout. If needed, table transposition is performed outside of
the LLM. Additionally, we check if the last row contains summarized or
aggregated values and if so, NormTab ignore this row. This selective column
normalization method reduces the workload on the LLM, enhances efficiency, and
ensures that only the necessary parts of the table are processed, thereby
preserving the integrity of already structured data.

##  4 Experimental Setup

###  4.1 Dataset

We conduct experimental evaluations using two challenging web table datasets:
WikiTableQuestion (WikiTQ)(Pasupat and Liang, 2015) and TabFact (Chen et al.,
2020). These datasets are specifically curated to test the reasoning
capabilities of models on complex tabular data. WikiTQ comprises tables
extracted from Wikipedia along with corresponding natural language questions,
while TabFact consists of tables sourced from Wikipedia paired with textual
facts. These datasets provide a diverse range of table structures and content,
allowing us to thoroughly evaluate the performance of NormTab in enhancing
table reasoning tasks.

The WikiTQ standard test set comprises 416 unique tables and 4,344 samples,
while the TabFact standard test set includes 298 unique tables with 2,003
samples. By utilizing these datasets, we aim to demonstrate the effectiveness
of web table normalization in improving the symbolic reasoning performance of
LLMs, thereby highlighting the importance of addressing the challenges posed
by web table irregularities.

###  4.2 Baselines and Evaluation Metrics

We compare our approach with several robust baseline methods, including
TableCoT (Chen, 2023), BINDER (Cheng et al., 2022), DATER (Ye et al., 2023),
StructGPT (Jiang et al., 2023), ReAcTable (Zhang et al., 2023b), Rethinking-
Tab-Data (Liu et al., 2023), TabSQLify (Nahid and Rafiei, 2024), and Chain-of-
Table (Wang et al., 2024).

For the WikiTQ dataset, exact match (EM) accuracy was used to check if the
predicted answers matched the correct ones. To address varying text formats, a
pre-matching check using LLMs was incorporated Cheng et al. (2022). The
accuracy for TabFact was assessed using binary classification accuracy.

###  4.3 Implementation

We utilized gpt-3.5-turbo-0125 as the Language Model which supports 16k
context window. We were inspired by the prompting style from (Liu et al.,
2023; Nahid and Rafiei, 2024) in our implementation of NormTab. To compare
performance, we employ few-shot in-context learning. This involves supplying
the LLM with the table title, table header, question, and three example rows
of the table, along with the question, to generate an SQL query. The SQL query
is then executed on the table to obtain the answer. Further details can be
found in Appendix C 111The source code for the implementation discussed in
this paper will be made publicly available upon acceptance of the paper..

##  5 Results

In this section, we analyzed the performance of NormTab. To evaluate its
impact, we conducted few-shot in-context learning experiments to generate SQL
queries for answering specific questions. First, we performed experiments on
unnormalized tables without any modifications. Then, we compared the
performance on normalized tables. Additionally, we reported the performance of
different normalization processes.

###  5.1 Results on Downstream Tasks

Table 1 and Table 2 presents a comparison between the performance of NormTab
and the other baselines on WikiTQ and TabFact datasets.

In the WikiTQ dataset, the results showed that after applying the targeted
version of NormTab, we achieved 61.2% accuracy, surpassing the performance of
other baseline models. The targeted NormTab approach performs slightly better
than the basic version, where the entire table is passed to the LLMs. This
suggests that LLMs may be more effective at normalization tasks when dealing
with targeted smaller tables. Additionally, we gained about 10% improvement
compared to the Text-to-SQL (Rajkumar et al., 2022) model and SQL
(gpt-3.5-turbo) model. Notably, Rethinking-Tab-Data Liu et al. (2023) achieved
an accuracy of 56.87% by addressing structural varience using LLMs and a
Python agent. Chain-of-Table (Wang et al., 2024) employed an iterative
sequence of operations to tailor complex tables to specific questions,
achieving 59.94% accuracy. However, these and other baseline models are
question-dependent. In contrast, our model adopts a straightforward and simple
approach: it normalizes the table only once, irrespective of the question,
enabling answers to be derived from the normalized table using program-aided
symbolic reasoning.

Model | Acc (%)
---|---
TableCoT (Chen, 2023) | 52.40
Binder | 56.74
Dater | 52.80
ReAcTable | 52.40
Rethinking-Tab-Data | 56.87
Chain-of-Table | 59.94
Text-to-SQL (Rajkumar et al., 2022) | 52.90
Text-to-SQL (gpt-3.5-turbo) | 51.30
NormTabBasic \+ SQL (ours) | 60.80
NormTabTargeted \+ SQL (ours) | 61.20
Table 1: Performance comparison of NormTab on WikiTQ dataset. The results
clearly demonstrate that NormTab significantly surpasses other models in
accuracy when employing symbolic reasoning.

In Table 2, we can observe a similar performance enhancement compared to the
original table in table-based fact verification tasks. We achieved
approximately a 6% performance improvement compared to the results of Text-to-
SQL on the original table. It is worth noting that table-based fact
verification differs from table-based question answering tasks. Generating a
SQL query to verify a fact is more complex than simply retrieving an answer
from the table. Although other models not employing program-aided symbolic
reasoning perform better in this task, these models utilize LLMs for the
verification task providing the whole table to the model. Our experimental
results show promise for utilizing symbolic reasoning in such scenarios.

Model | Acc (%)
---|---
TableCoT-chatgpt | 73.10
Binder | 79.17
Dater | 78.01
Chain-of-Table | 80.20
ReAcTable | 73.10
Text-to-SQL (Rajkumar et al., 2022) | 64.71
Text-to-SQL (gpt-3.5-turbo) | 62.32
NormTabBasic \+ SQL (ours) | 67.10
NormTabTargeted \+ SQL (ours) | 68.90
Table 2: Performance comparison of NormTab on TabFact dataset with other
models.

###  5.2 NormTab Evaluation

To assess the accuracy of various normalization operations, we evaluated the
performance on 100 tables, with 50 tables from each dataset, WikiTQ and
TabFact. Table 3 summarizes the accuracy of different normalization processes.
NormTab demonstrated strong performance in normalizing dates and numbers,
detecting transposition requirements, and handling aggregated summaries in the
last row effectively. However, NormTab faced difficulties in extracting and
cleaning values in certain critical tables where value extraction from the
original table was particularly challenging. The column selection accuracy
indicates that LLMs can be very effective in identifying columns where values
are not in the proper format. However, the accuracy of splitting columns was
low. Additional errors included managing value cleaning and handling "n/a"
values. Although these tasks are challenging, the performance in these areas
shows the potential for utilizing LLMs to address these tasks effectively.

Type | Accuracy
---|---
Columns Selection | 91.0%
Transpose Detection | 97.0%
Last Row Aggregation | 100.0%
Split Column | 87.0%
Date and Number | 100.0%
N/A value | 93.0%
Value Cleaning | 82.0%
Table 3: Accuracy of NormTab in various types of normalization.

NormTab has shown superior performance compared to several robust models,
demonstrating its efficacy in table normalization. A key advantage of NormTab
is its use of program-aided symbolic reasoning, which streamlines code
generation without requiring the entire table to be passed to the LLM. This
enhances efficiency and eliminates dependencies on table size and answer
position. With NormTab, only key elements like the title, header, and a few
example rows are needed to generate SQL queries and obtain accurate answers.
This approach reduces computational overhead while maintaining high accuracy,
highlighting its practical utility in various table-based tasks.

###  5.3 Analysis

We conducted a detailed analysis of the impact of NormTab on the WikiTQ
dataset. Table 4 shows that in 67% of cases (Category A), performance improved
after applying NormTab. In 24% of cases (Category B), performance remained
unchanged, indicating no improvement. Additionally, in 9% of cases (Category
C), performance actually decreased. The detailed experimental findings are
summarized in Table 5.

Categories | Description | % of Tables
---|---|---
A |  | Where performance
---
enhanced after
applying NormTab
67%
B |  | Where no change in
---
performance after
applying NormTab
24%
C |  | Where the performance
---
decreased after
applying NormTab
9%
Table 4: Categories of tables on WikiTQ test dataset. - | Tables (A) | Tables (B,C) | Overall (A,B,C)
---|---|---|---
Original | 46.28% | 59.62% | 51.30%
NormTab | 62.55% | 56.76% | 61.20%
Change | +16.27 | -2.86 | +9.9
Table 5: Result breakdown on WikiTQ dataset.

Table 5 demonstrates that NormTab can improve overall performance by 9.9%.
Notably, in Category A, we observed a substantial enhancement of 16.27%.
However, Categories B and C saw a slight decline in performance due to highly
complex table values and structures.

##  6 Conclusion

In conclusion, our study introduces NormTab, a framework aimed at enhancing
LLMs’ performance on tabular data by normalizing web tables. Through our
investigation, we have shown the significance of web table normalization in
overcoming challenges such as mixed values and structural variance. By
leveraging LLMs’ textual understanding in data cleaning and normalization,
NormTab improves table reasoning. Our experiments on challenging datasets
demonstrate its effectiveness. Our work contributes to advancing techniques
for LLMs in handling tabular data, emphasizing the importance of addressing
web table challenges for improved performance. Further research can explore
additional normalization strategies and extend NormTab’s applicability across
various domains. This would establish a robust foundation for a wide range of
downstream tasks involving table reasoning.

## Limitations

Despite the advancements brought by NormTab, there are several limitations.
First, while our framework significantly enhances the symbolic reasoning
capabilities of LLMs on tabular data, there remains room for improvement in
the normalization process, particularly with more complex table structures.
Additionally, for larger tables, LLMs may sometimes produce hallucinated
results, leading to inaccuracies in the normalized output, indicating a need
for better handling of extensive datasets. Furthermore, when dealing with
tables that contain extremely noisy data, LLMs struggle to effectively clean
and normalize the information. The presence of excessive noise and
inconsistencies can hinder the normalization process and negatively impact
overall performance. Addressing these limitations is crucial for further
enhancing the robustness and reliability of NormTab. As we measure the
accuracy using the results obtained from LLM based Text-to-SQL model, it is
important to note that some questions in the dataset may not directly map to
SQL queries which may affect the performance.

## Ethical Considerations

The datasets used in this study are accessible through the peer-reviewed
articles cited in the references section. Additionally, our source code is
openly available for future research under the MIT License. It is important to
mention that our framework relies on GPT-3.5-turbo, which may inherit ethical
concerns associated with GPT models. These concerns include the potential for
generating responses to toxic content or displaying biased behavior.

## References

  * Abedjan et al. (2016) Ziawasch Abedjan, Xu Chu, Dong Deng, Raul Castro Fernandez, Ihab F Ilyas, Mourad Ouzzani, Paolo Papotti, Michael Stonebraker, and Nan Tang. 2016.  Detecting data errors: Where are we and what needs to be done?  _Proceedings of the VLDB Endowment_ , 9(12):993–1004.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Chen (2023) Wenhu Chen. 2023.  Large language models are few(1)-shot table reasoners.  In _Findings of the Association for Computational Linguistics: EACL 2023_ , pages 1120–1130, Dubrovnik, Croatia. Association for Computational Linguistics.
  * Chen et al. (2020) Wenhu Chen, Hongmin Wang, Jianshu Chen, Yunkai Zhang, Hong Wang, Shiyang Li, Xiyou Zhou, and William Yang Wang. 2020.  Tabfact: A large-scale dataset for table-based fact verification.  In _International Conference on Learning Representations_.
  * Cheng et al. (2022) Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, et al. 2022.  Binding language models in symbolic languages.  In _The Eleventh International Conference on Learning Representations_.
  * Furche et al. (2016) Tim Furche, Georg Gottlob, Leonid Libkin, Giorgio Orsi, and Norman W Paton. 2016.  Data wrangling for big data: Challenges and opportunities.  In _19th International Conference on Extending Database Technology_ , pages 473–478.
  * Gu et al. (2022) Zihui Gu, Ju Fan, Nan Tang, Preslav Nakov, Xiaoman Zhao, and Xiaoyong Du. 2022.  PASTA: Table-operations aware fact verification via sentence-table cloze pre-training.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 4971–4983, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Herzig et al. (2020) Jonathan Herzig, Pawel Krzysztof Nowak, Thomas Müller, Francesco Piccinno, and Julian Eisenschlos. 2020.  TaPas: Weakly supervised table parsing via pre-training.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 4320–4333, Online. Association for Computational Linguistics.
  * Jiang et al. (2023) Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Xin Zhao, and Ji-Rong Wen. 2023.  StructGPT: A general framework for large language model to reason over structured data.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 9237–9251, Singapore. Association for Computational Linguistics.
  * Kifer et al. (2005) Michael Kifer, Arthur Bernstein, and Philip M Lewis. 2005.  _Database Systems: An Application-Oriented Approach_.  Addison-Wesley, 2005.
  * Liu et al. (2023) Tianyang Liu, Fei Wang, and Muhao Chen. 2023.  Rethinking tabular data understanding with large language models.  _arXiv preprint arXiv:2312.16702_.
  * Nahid and Rafiei (2024) Md Mahadi Hasan Nahid and Davood Rafiei. 2024.  TabSQLify: Enhancing reasoning capabilities of LLMs through table decomposition.  In _2024 Annual Conference of the North American Chapter of the Association for Computational Linguistics_.
  * Narayan et al. (2022) Avanika Narayan, Ines Chami, Laurel Orr, and Christopher Ré. 2022.  Can foundation models wrangle your data?  _Proceedings of the VLDB Endowment_ , 16(4):738–746.
  * Ni et al. (2023) Ansong Ni, Srini Iyer, Dragomir Radev, Ves Stoyanov, Wen-tau Yih, Sida I Wang, and Xi Victoria Lin. 2023.  Lever: Learning to verify language-to-code generation with execution.  In _Proceedings of the 40th International Conference on Machine Learning (ICML’23)_.
  * Pasupat and Liang (2015) Panupong Pasupat and Percy Liang. 2015.  Compositional semantic parsing on semi-structured tables.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1470–1480, Beijing, China. Association for Computational Linguistics.
  * Pourreza and Rafiei (2023) Mohammadreza Pourreza and Davood Rafiei. 2023.  DIN-SQL: Decomposed in-context learning of text-to-SQL with self-correction.  In _Thirty-seventh Conference on Neural Information Processing Systems_.
  * Rajkumar et al. (2022) Nitarshan Rajkumar, Raymond Li, and Dzmitry Bahdanau. 2022.  Evaluating the text-to-sql capabilities of large language models.  _arXiv preprint arXiv:2204.00498_.
  * Rattenbury et al. (2017) Tye Rattenbury, Joseph M Hellerstein, Jeffrey Heer, Sean Kandel, and Connor Carreras. 2017.  _Principles of data wrangling: Practical techniques for data preparation_.  " O’Reilly Media, Inc.".
  * Wang et al. (2019) Bailin Wang, Ivan Titov, and Mirella Lapata. 2019.  Learning semantic parsers from denotations with latent structured alignments and abstract programs.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3774–3785, Hong Kong, China. Association for Computational Linguistics.
  * Wang et al. (2023) Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023.  Self-consistency improves chain of thought reasoning in language models.  In _The Eleventh International Conference on Learning Representations_.
  * Wang et al. (2024) Zilong Wang, Hao Zhang, Chun-Liang Li, Julian Martin Eisenschlos, Vincent Perot, Zifeng Wang, Lesly Miculicich, Yasuhisa Fujii, Jingbo Shang, Chen-Yu Lee, et al. 2024.  Chain-of-table: Evolving tables in the reasoning chain for table understanding.  _arXiv preprint arXiv:2401.04398_.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. 2022.  Chain of thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems_.
  * Ye et al. (2023) Yunhu Ye, Binyuan Hui, Min Yang, Binhua Li, Fei Huang, and Yongbin Li. 2023.  Large language models are versatile decomposers: Decomposing evidence and questions for table-based reasoning.  In _Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’23, page 174–184, New York, NY, USA. Association for Computing Machinery.
  * Zha et al. (2023) Liangyu Zha, Junlin Zhou, Liyao Li, Rui Wang, Qingyi Huang, Saisai Yang, Jing Yuan, Changbao Su, Xiang Li, Aofeng Su, et al. 2023.  Tablegpt: Towards unifying tables, nature language and commands into one gpt.  _arXiv preprint arXiv:2307.08674_.
  * Zhang et al. (2023a) Tianshu Zhang, Xiang Yue, Yifei Li, and Huan Sun. 2023a.  Tablellama: Towards open large generalist models for tables.  _Preprint_ , arXiv:2311.09206.
  * Zhang et al. (2023b) Yunjia Zhang, Jordan Henkel, Avrilia Floratou, Joyce Cahoon, Shaleen Deep, and Jignesh M Patel. 2023b.  Reactable: Enhancing react for table question answering.  _arXiv preprint arXiv:2310.00815_.

##  Appendix A Web Tables vs Regular DB Table

There are some key differences between a web table and relational database
table. Web tables and relational database tables exhibit distinct
characteristics, each with its own advantages and challenges. Web tables,
often sourced from online sources such as websites and spreadsheets, tend to
be diverse in structure and content. They may contain varying formats,
including column-based, row-based, and aggregated summaries, with
irregularities such as mixed values and noisy data being common. Additionally,
web tables frequently present challenges in terms of structural variance, as
they may lack standardized schema and exhibit inconsistencies in data
organization. In contrast, relational database tables (RDBMS) adhere to a
structured schema. These tables are typically designed for efficient storage
and retrieval of data, with clear relationships defined between entities
through keys and constraints. Relational database tables offer advantages in
terms of data integrity, consistency, and scalability, as they enforce
normalization principles and allow for efficient querying through SQL.

However, Web Tables may lack the flexibility and adaptability required to
handle the diverse and unstructured nature of web data. While relational
database tables excel in maintaining structured data integrity, web tables
present challenges related to variability and noise, necessitating specialized
techniques for effective processing and analysis.

##  Appendix B Comparison with Other Models

Chain-of-Table (Wang et al., 2024) enhances reasoning on tabular data by
iteratively transforming and evolving table structures through a series of
reasoning steps, including row/column selection and cell splitting. Their
method uses in-context learning to guide LLMs in generating operations and
updating the table, forming a reasoning chain specific to tabular data. Liu et
al. (2023) explore LLM capabilities in interpreting and reasoning over tabular
data, emphasizing robustness to structural changes and comparing textual and
symbolic reasoning. They find that structural variations can significantly
degrade performance, especially in symbolic reasoning tasks, and propose table
structure normalization through transposition to mitigate this issue. Their
study concludes that while textual reasoning slightly outperforms symbolic
reasoning, both have distinct strengths depending on the task.

The ReAcTable model (Zhang et al., 2023b) follows the ReAct paradigm,
incorporating step-by-step reasoning, external tool-based code execution,
intermediate table generation, and majority voting to process tabular data.
Recent approaches leverage LLM capabilities for these tasks. For instance,
Narayan et al. (2022) demonstrated LLM effectiveness in identifying errors and
imputing missing data, enhancing the data wrangling process. Integrating LLMs
can significantly improve the efficiency and accuracy of preparing data for
analysis, streamlining and automating many aspects of data wrangling.
Operations like normalizing numbers and dates can be incorporated into data
processing workflows to aid subsequent analysis (Nahid and Rafiei, 2024; Cheng
et al., 2022).

Existing models and methods typically rely on multi-step frameworks where LLMs
select actions, such as adding columns, and additional scripts process values
based on specific questions (Liu et al., 2023; Wang et al., 2024; Zhang et
al., 2023b). However, these approaches are question-dependent and do not
comprehensively address the root issue of table normalization. NormTab differs
by focusing on normalizing tables once, regardless of the question, allowing
answers to be derived from the normalized table using program-aided symbolic
reasoning. This approach reduces dependencies on table size and answer
position, enhancing efficiency and versatility in table reasoning tasks.

##  Appendix C Implementation

We configured the in-context learning hyperparameters for gpt-3.5-turbo-0125
according to the specifications outlined in Table 6.

Parameter |  | Coll
---
Selection
| Transpose
---
Detection
NormTab
temperature | 0.3 | 0.3 | 0.7
top_p | 1 | 1 | 1
sample_n | 1 | 1 | 1
max_tokens | 100 | 100 | 4500
num_shots | 6 | 1 | 1
Table 6: The hyper-parameters we set in NormTab

##  Appendix D Example Prompts

The prompt used in NormTab is described in the following Figures.

Figure 3: Column Selection prompt.

Figure 4: Summarized last row detection and transpose detection prompt.

Figure 5: NormTab Instruction prompt.

Figure 6: Text-to-SQL prompt template for the Table QA Task on the WikiTQ
dataset.

Figure 7: Text-to-SQL prompt template for the Table-based Fact Verification
Task on the TabFact dataset.


# Bayesian Algorithms Learn to Stabilize Unknown Continuous-Time Systems

Mohamad Kazem Shirani Faradonbeh, Mohamad Sadegh Shirani Faradonbeh

###### Abstract

Linear dynamical systems are canonical models for learning-based control of
plants with uncertain dynamics. The setting consists of a stochastic
differential equation that captures the state evolution of the plant
understudy, while the true dynamics matrices are unknown and need to be
learned from the observed data of state trajectory. An important issue is to
ensure that the system is stabilized and destabilizing control actions due to
model uncertainties are precluded as soon as possible. A reliable
stabilization procedure for this purpose that can effectively learn from
unstable data to stabilize the system in a finite time is not currently
available. In this work, we propose a novel Bayesian learning algorithm that
stabilizes unknown continuous-time stochastic linear systems. The presented
algorithm is flexible and exposes effective stabilization performance after a
remarkably short time period of interacting with the system.

##  1 Introduction

Linear dynamical systems are ubiquitous models in the system theory for
effective control of plants [1, 2]. In a general setting, the state of the
plant understudy follows a multidimensional stochastic differential equation
depending on the state vector and control input at the time, together with the
exogenous disturbance noise. An interesting problem is that of stabilization
under uncertainty to ensure that the system can safely operate for a
reasonable time period.

In many situations, a reliable knowledge of the system matrices that determine
the differential equations of state evolution is unavailable. Such lack of
knowledges can be due to unintended internal interactions between the state
quantities of an engineered plant or naturally unknown dynamics of the
environment one desires to control, such as biological or financial systems
[3, 4, 5]. In such situations, data-driven methods are needed to learn the
underlying unknown true dynamical behaviors from the observed data.

Accordingly, design and analysis of learning-based methods for control of
unknown dynamical systems is of interest to ensure optimal system
performances. For continuous-time stochastic linear systems, study of adaptive
policies for near-optimal regulations has a rich literature. That consists of
control policies that estimate optimal actions after long-term interactions
with the system [6, 7, 8, 9] as well as those who focus on the resulting sub-
optimalities of learning-based policies [10, 11, 12, 13, 14]. However,
algorithms for learning to stabilize with provable performance are limited to
infinite time schemes for a class of controllable systems [9, 12]. So, finite-
time approaches are currently missing and is adopted as the subject of this
work, especially for the more general case of stabilizable (rather than
controlable) dynamical systems.

Importantly, stabilization procedures require to terminate in a finite time.
On one hand, the decision-maker can focus on optimality only when
instabilities are fully precluded. On the other hand, during the stabilization
period, the system can expose unstable behavior making the magnitude of the
state extremely large. Therefore, continuation of stabilization algorithms for
long periods of time defeats the purpose. For the case of discrete-times
dynamics, the problem of stabilization recently received a lot of attentions.
The existing results include performance guarantees for stabilizable [15, 16]
and controllable systems [17, 18, 19].

In the discrete-time regime, the method of applying random feedback matrices
is proposed to ensure that the resulting unknown closed-loop matrix is
learnable [20, 15]. Intuitively, if (the rates or directions of) explosions
for an unstable linear dynamical system are indistinguishable, parameter
estimates will be drastically inaccurate [21]. To avoid these pathological
cases for learning stabilizing policies, the algorithm can randomize the
inputs, which in turn renders pathological closed-loop matrices unlikely [15].
Then, once stabilized, low-regret reinforcement learning policies can be
applied to the system to learn to minimize the operating costs. The latter
trend of research includes many recent works as well, especially for the case
of quadratic cost functions [22, 23, 24, 25].

In this work, we introduce an algorithm that learns to stabilize unknown
continuous-time stochastic linear system in a short time period. The algorithm
designs control inputs that effectively excite all modes of the system, and
switches the employed feedback policies in sub-intervals of the original time
interval. Then, the resulting state vectors are utilized in a Bayesian fashion
to form a posterior belief about the unknown dynamics matrices. The
performance of the algorithm is studied and effects of different parameters
are discussed. We present numerical results showcasing that in a remarkably
short time period, the proposed algorithm successfully stabilizes the system
with high probability. Introducing a novel framework for fast stabilization,
we discuss the implications and provide multiple interesting research avenues
for future investigations.

This paper is organized as follows. In Section 2, we present the detailed
statement of the problem and discuss different aspects of stabilization under
uncertainty. Then, in Section 3, we propose a Bayesian learning-based
stabilization algorithm and outline the detailed steps it relies on. Analysis
of the algorithm and interpretations of the effects of different parameters
are provided in Section 4. Finally, we spotlight the vision this work leads
to, discuss possible extensions to other regimes such as large-scale and/or
non-linear systems, and mention different directions for future studies on
data-driven methods and algorithms for learning-to-stabilize.

Notation: The Euclidean norm of vectors is denoted by
${\left|\kern-1.29167pt\left|\cdot\right|\kern-1.29167pt\right|}$, while for
matrices, we use operator norms:
${\left|\kern-1.29167pt\left|M\right|\kern-1.29167pt\right|}=\sup\limits_{{\left|\kern-0.90417pt\left|v\right|\kern-0.90417pt\right|}=1}{\left|\kern-1.29167pt\left|Mv\right|\kern-1.29167pt\right|}$.
Further, we define normal distribution for matrices, as follows. For
$d_{1}\times d_{2}$ matrices $M,\mu$ and $d_{1}\times d_{1}$ matrix $\Sigma$,
when we say that $M$ has the distribution
$\mathcal{N}\left(\mu,\Sigma\right)$, it means that all $d_{2}$ columns of $M$
are independent from each other, and are $d_{1}$ dimensional normally
distributed random vectors such that their covariance matrix is $\Sigma$ and
their mean is the corresponding column of $\mu$. For a square matrix $M$, we
denote the largest real-part of the eigenvalues of $M$ by
$\boldsymbol{\overline{\lambda}}\left(M\right)$. Note that
$\boldsymbol{\overline{\lambda}}\left(M\right)$ can be either negative (stable
$M$) or non-negative (unstable $M$). Finally,
$\mathds{1}_{\left\\{\mathcal{S}\right\\}}$ is the indicator function that has
the value $1$ whenever $\mathcal{S}$ holds true, and is $0$ otherwise.

##  2 Problem Statement

We study stabilization of continuous-time stochastic systems under
uncertainty. In this setting, the dynamics of the plant under consideration
consist of the following _unknown_ stochastic differential equation:

$\mathrm{d}X_{t}=\left(A_{\star}X_{t}+B_{\star}U_{t}\right)\mathrm{d}t+C_{\star}\mathrm{d}\mathbb{W}_{t}.$
(1)

That is, the open-loop transition matrix $A_{\star}\in\mathbb{R}^{p\times p}$
of the system with state $X_{t}\in\mathbb{R}^{p}$, as well as the input matrix
$B_{\star}$ that reflects the effect of the control signal
$U_{t}\in\mathbb{R}^{q}$, both are _unknown_. The differential equation
describing the plant in the above model includes a white noise. That is, the
system is disturbed by the Brownian motion $\mathbb{W}_{t}$, technically
defined as a continuous-time stochastic process with independent Gaussian
increments $\mathbb{W}_{t}-\mathbb{W}_{s},s\leq t$ of mean zero,
$\mathbb{E}\left[\mathbb{W}_{t}-\mathbb{W}_{s}\right]=0_{d}$, and covariance
matrix
$\mathrm{Cov}\left(\mathbb{W}_{t}-\mathbb{W}_{s}\right)=\left(t-s\right)I_{d}$.
The $p\times d$ matrix $C_{\star}$ that rescales the noise influence is
assumed _unknown_ as well.

Note that if the physical behavior of the system is governed by a differential
equation of a higher degree, one can convert it to the state-space model in
(1). To that end, it suffices to concatenate the physical state together with
its derivatives of different orders to obtain the larger state vector $X_{t}$
[1, 2, 21]. Therefore, studying data-driven control schemes for learning to
stabilize the dynamical system in (1) captures a general class of plants.

To proceed, we assume that the system is stabilizable.

###### Assumption 1

There exists an unknown feedback matrix ${L}_{\text{stab}}$ such that
$\boldsymbol{\overline{\lambda}}\left(A_{\star}+B_{\star}{L}_{\text{stab}}\right)<0$.

The above assumption is necessary. Otherwise, stability becomes infeasible
even under full certainty about $A_{\star},B_{\star}$. Moreover, thanks to
linear dynamics in (1), Assumption 1 implies the mean-square stabilizability.
Note that due to the Brownian noise $\mathbb{W}_{t}$, fluctuations and large
state values in the trajectory of the stochastic system are unavoidable.
However, under the stabilizing linear feedback $U_{t}={L}_{\text{stab}}X_{t}$,
the state $X_{t}$ becomes a multivariate Gaussian random vector with a finite
covariance matrix [26], and we have
${\left|\kern-1.29167pt\left|X_{t}\right|\kern-1.29167pt\right|}=\mathcal{O}\left(\sqrt{-\log\delta}\right)$,
with probability at least $1-\delta$ [21].

It is well-known that stabilizability is intimately related to Riccati
equations. For this purpose, let the symmetric matrices
$Q\in\mathbb{R}^{p\times p}$ and $R\in\mathbb{R}^{q\times q}$ be positive
definite. Then, for ${A},M\in\mathbb{R}^{p\times p}$ and
${B}\in\mathbb{R}^{p\times q}$, define the mapping

$\Phi_{{A},{B}}\left(M\right)={A}^{\top}M+M{A}-M{B}R^{-1}{B}^{\top}M+Q.$ (2)

So, under Assumption 1, the algebraic continuous-time Riccati equation
$\Phi_{A_{\star},B_{\star}}\left(M\right)=0$ has a unique positive
semidefinite solution $\boldsymbol{{K}}\left(A_{\star},B_{\star}\right)$.
Conversely, existence of the solution
$\boldsymbol{{K}}\left(A_{\star},B_{\star}\right)$ is sufficient for the
stabilizability in Assumption 1 [1, 2]. Furthermore, Riccati equations can be
solved relatively fast and explicitly provide the following stabilizing linear
feedback matrix [1, 2]:

$\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)=-R^{-1}B_{\star}^{\top}\boldsymbol{{K}}\left(A_{\star},B_{\star}\right).$
(3)

###### Theorem 1

For the linear feedback in (3), we have

$\boldsymbol{\overline{\lambda}}\left(A_{\star}+B_{\star}\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)\right)<0.$

However, when the exact values of the true dynamics matrices
$A_{\star},B_{\star}$ are not available, the Riccati equation
$\Phi_{A_{\star},B_{\star}}\left(M\right)=0$ is not solvable and the problem
of stabilization is challenging. In the next section, we provide a more
general framework for stabilizing the system based on approximations of
$A_{\star},B_{\star}$.

###  2.1 Stabilization under Uncertainty

When the true dynamics matrices are unknown, data-driven methods are required
to learn from the state trajectory to stabilize the system. More precisely,
learning-based algorithms first design the control signal and observe the
resulting state trajectory, and then utilize the observed data to estimate
$A_{\star},B_{\star}$. However, learning from trajectories of limited length
can never be perfectly accurate and at best can lead to approximate estimates
of the dynamics matrices. Especially, since during the stabilization period
the system is most likely to be exponentially unstable, this period needs to
be as short as possible. In the following result, we generalize Theorem 1 and
establish an accuracy in estimating $A_{\star},B_{\star}$ that is _sufficient_
for stabilization.

###### Theorem 2

Letting
$D_{\star}=A_{\star}+B_{\star}\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)$,
assume that $\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)\leq-1$.
Then, there is a constant $c$ such that the followings are sufficient for
$\boldsymbol{\overline{\lambda}}\left(A_{\star}+B_{\star}\boldsymbol{{L}}\left({A},{B}\right)\right)<0$:

$\displaystyle{\left|\kern-1.29167pt\left|{A}-A_{\star}\right|\kern-1.29167pt\right|}$
$\displaystyle\leq$
$\displaystyle-c\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)p^{-1/2},$
(4)
$\displaystyle{\left|\kern-1.29167pt\left|{B}-B_{\star}\right|\kern-1.29167pt\right|}$
$\displaystyle\leq$
$\displaystyle-c\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)p^{-1/2}{\left|\kern-1.29167pt\left|\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)\right|\kern-1.29167pt\right|}^{-1}.$
(5)

The proof Theorem 2 is provided in the appendix. Note that according to
Theorem 1, we have $\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)<0$.
Thus, the condition $\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)<-1$
expresses that if one closes the loop by the linear feedback policy which is
designed for $A_{\star},B_{\star}$, then the stability margin is at least $1$.
However, $\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)<-1$ is not a
fundamental requirement, is adopted merely for the ease of presentation, and
extensions to the case
$-1\leq\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)<0$ is mainly the
matter of technicality.

The statement of the above result contains the following interpretations.
According to Theorem 2, a coarse-grained approximation of the unknown true
matrices suffices for stabilization. The accuracy specified by (4) and (5)
indicates that systems with larger state dimension $p$ are harder to
stabilize, as well as those with smaller stability margins
$-\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)$. The former is caused
by the larger number of parameters to learn, while the latter reflects the
extent to which the system stability is robust against uncertainty.
Furthermore, (5) shows that smaller true feedback matrices
$\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)$ help stabilization because
${\left|\kern-1.29167pt\left|\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)\right|\kern-1.29167pt\right|}$
quantifies the strength of an effective control input for altering a possibly
unstable open-loop matrix $A_{\star}$ to a stable closed-loop matrix
$D_{\star}$, through $B_{\star}$.

Note that (3) does _not_ imply that a larger matrix $R$ leads to a smaller
${\left|\kern-1.29167pt\left|\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)\right|\kern-1.29167pt\right|}$
(i.e., easier stabilization). In fact, according to the Lyapunov equation

$\boldsymbol{{K}}\left({A},{B}\right)=\int\limits_{0}^{\infty}{e^{{D}^{\top}t}\left(Q+\boldsymbol{{L}}\left({A},{B}\right)^{\top}R\boldsymbol{{L}}\left({A},{B}\right)\right)e^{{D}t}}\mathrm{d}{t},$
(6)

$\boldsymbol{{K}}\left(A_{\star},B_{\star}\right)$ grows with $R$. So, by (3),
it is challenging to select the best $Q,R$ matrices for relaxing the accuracy
in (5) for stabilizing the system. However, the numerical studies in the
sequel suggest that smaller $R$ matrices lead to slightly larger chances for
successful stabilization.

##  3 Bayesian Learning Algorithm

Next, we introduce a stabilization algorithm that leverages Bayesian learning
methods to quickly find a stabilizing feedback for the unknown system in (1).
Broadly speaking, Algorithm 1 commits to interact with the plant in the time
interval $0\leq t\leq\boldsymbol{\tau}$, and then provides a stabilizing
feedback by using the collected data. It applies randomized control inputs in
periods of length $\boldsymbol{\tau}/n$, employs a Bayesian learning method to
compute a posterior belief about the unknown truth, and then samples
$\left[{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right]^{\top}$ from the
posterior distribution. Finally, these sampled matrices are used together with
the Riccati equation to design a stabilizing feedback. The length
$\boldsymbol{\tau}$, the number of periods $n$, and the randomization scales
$\sigma_{{L}},\sigma_{V}$, are provided to the algorithm as inputs. In the
sequel, we present the detailed procedure of Algorithm 1.

Algorithm 1 : Bayesian Learning for Stabilization

Inputs: stabilization time $\boldsymbol{\tau}$, feedback variance
$\sigma_{{L}}^{2}$, randomization variance $\sigma_{V}^{2}$, number of periods
$n$

Output: posterior samples
$\left[{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right]^{\top}$

Let $\left\\{V_{t}\right\\}_{t\geq 0}$ be the randomization signal in (7)

for period $j=1,\cdots,n$ do

Sample feedback ${L}_{j}$ from
$\mathcal{N}\left(0,\sigma_{{L}}^{2}I_{p}\right)$

while in the interval $\frac{\left(j-1\right)\boldsymbol{\tau}}{n}\leq
t<\frac{j\boldsymbol{\tau}}{n}$, do

Apply input $U_{t}={L}_{j}X_{t}+\sigma_{V}V_{t}$

end while

end for

Calculate
$\boldsymbol{\mu}_{\boldsymbol{\tau}},\boldsymbol{\Sigma}_{\boldsymbol{\tau}}$,
and $\mathcal{D}_{\boldsymbol{\tau}}$ according to (8), (9), and (10)

Return sample
$\left[{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right]^{\top}$ from the
posterior $\mathcal{D}_{\boldsymbol{\tau}}$

First, fix $\epsilon>0$ and let $\left\\{V_{t}\right\\}_{t\geq 0}$ be a
continuous-time $q$ dimensional standard Gaussian signal with independent
piece-wise constant values that change after short intervals of length
$\epsilon$. Technically, suppose that
$\left\\{\xi_{k}\right\\}_{k=1}^{\infty}$ is a sequence of independent
identically distributed $\mathbb{R}^{q}$-valued vectors that share the
standard normal distribution $\mathcal{N}\left(0_{q},I_{q}\right)$, and define
the randomization signal

$V_{t}=\sum\limits_{k=1}^{\infty}\mathds{1}_{\left\\{(k-1)\epsilon\leq
t<k\epsilon\right\\}}\xi_{k}.$ (7)

That is, during the time interval $(k-1)\epsilon\leq t<k\epsilon$, we have
$V_{t}=\xi_{k}$. Note that if $\epsilon$ shrinks, $\epsilon^{1/2}V_{t}$
converges in distribution to a continuous-time Gaussian process. However, in
Algorithm 1, $\epsilon$ is a fixed value satisfying
$\epsilon<\boldsymbol{\tau}q^{-1}n^{-1}$. Indeed, it suffices for $\epsilon$
to be small enough to help the control signal $U_{t}$ randomizing the input
for ensuring that all modes of the dynamical system in (1) are properly
excited.

Algorithm 1 breaks the interval $0\leq t\leq\boldsymbol{\tau}$ to $n$ sub-
interval periods of equal lengths. Then, during period
$j\in\left\\{1,\cdots,n\right\\}$, the control input
$U_{t}={L}_{j}X_{t}+\sigma_{V}V_{t}$ is applied to the plant, where
${L}_{j}\sim\mathcal{N}\left(0,\sigma_{{L}}^{2}I_{q}\right)$ is a random
feedback matrix for period $j$. Recall from the definition of normally
distributed matrices in the notation that it is equivalent to say that all $p$
columns of ${L}_{j}$ are independently drawn from a zero-mean Gaussian
distribution with covariance matrix $\sigma_{{L}}^{2}I_{q}$. The rationale of
employing random feedbacks is to preclude the resulting true closed-loop
matrix $A_{\star}+B_{\star}{L}_{j}$ from falling on the pathological manifold
of _non-estimable_ matrices [21, 15, 16]. Further technical details about
necessity and effectiveness of random feedback matrices is beyond the scope of
this work and can be found in the aforementioned references.

After designing and applying the above control inputs, Algorithm 1 uses the
collected observations $\left\\{X_{t},U_{t}\right\\}_{0\leq
t\leq\boldsymbol{\tau}}$ to calculate a posterior distribution
$\mathcal{D}_{\boldsymbol{\tau}}$ on the set of $\left[{A},{B}\right]^{\top}$
matrices, and then samples
$\left[{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right]^{\top}$ from
$\mathcal{D}_{\boldsymbol{\tau}}$, as outlined below. Denote the observation
at time $t$ by the vector
$Y_{t}=\left[X_{t}^{\top},U_{t}^{\top}\right]^{\top}\in\mathbb{R}^{p+q}$.
Then, define the $\left(p+q\right)\times\left(p+q\right)$ precision matrix

$\boldsymbol{\Sigma}_{\boldsymbol{\tau}}=I_{p+q}+\int\limits_{0}^{\boldsymbol{\tau}}{Y_{s}Y_{s}^{\top}}\mathrm{d}{s},$
(8)

as well as the the $\left(p+q\right)\times p$ mean matrix

$\boldsymbol{\mu}_{\boldsymbol{\tau}}=\boldsymbol{\Sigma}_{\boldsymbol{\tau}}^{-1}\int\limits_{0}^{\boldsymbol{\tau}}{Y_{s}}\mathrm{d}{X_{s}^{\top}}.$
(9)

Now, Algorithm 1 forms the posterior belief

$\mathcal{D}_{\boldsymbol{\tau}}=\mathcal{N}\left(\boldsymbol{\mu}_{\boldsymbol{\tau}},\boldsymbol{\Sigma}_{\boldsymbol{\tau}}^{-1}\right),$
(10)

about the unknown true dynamics matrices $A_{\star},B_{\star}$. So, as defined
in the notation, the posterior distribution of every column $i=1,\cdots,p$ of
$\left[A_{\star},B_{\star}\right]^{\top}$ is a multivariate normal that its
mean is the column $i$ of the matrix $\boldsymbol{\mu}_{\boldsymbol{\tau}}$
and its covariance matrix is $\boldsymbol{\Sigma}_{\boldsymbol{\tau}}^{-1}$.
Next, Algorithm 1 samples from $\mathcal{D}_{\boldsymbol{\tau}}$, and returns
the resulting sample matrix
$\left[{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right]^{\top}$.

Finally, expecting that
$\left[{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right]^{\top}$ is a
sufficiently accurate approximation of $A_{\star},B_{\star}$, the feedback
matrix
$\boldsymbol{{L}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)$
is expected to stabilize the system. That is, letting
$\boldsymbol{{K}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)$
be the solution of the Riccati equation
$\Phi_{{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}}\left(M\right)=0$ in
(2) for the dynamics parameters
$\left[{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right]^{\top}$, we
define
$\boldsymbol{{L}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)=-R^{-1}{B}_{\boldsymbol{\tau}}^{\top}\boldsymbol{{K}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)$,
and expect to have
$\boldsymbol{\overline{\lambda}}\left(A_{\star}+B_{\star}\boldsymbol{{L}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)\right)<0$.
It is straightforward to see that the probabilistic belief
$\mathcal{D}_{\boldsymbol{\tau}}$ is the commonly used posterior distribution
in Bayesian learning methods, if a Gaussian prior distribution about the true
parameter is assumed. Of course, note that we did not assume availability of
such prior beliefs about $A_{\star},B_{\star}$.

##  4 Performance of Learning Algorithm

Figure 1: The above panel showcases the estimation error
${\left|\kern-1.29167pt\left|\left[{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right]^{\top}-\left[A_{\star},B_{\star}\right]^{\top}\right|\kern-1.29167pt\right|}$
of Algorithm 1, versus the stabilization time length $\boldsymbol{\tau}$. The
panel consists of $4$ graphs corresponding to different values of
$\sigma_{{L}}$. The value of $\sigma_{V}=1$ is fixed, while curves of
different colors correspond to the number of periods ($n=1$ (blue), $n=2$
(red), $n=3$ (green), and $n=4$ (black)). These plots illustrate that the
algorithm is able to quickly learn the true unknown dynamical model.

Figure 2: The above graphs show the percentage of successful stabilizations by
Algorithm 1, versus the stabilization time length $\boldsymbol{\tau}$. The
figure consists of $4$ graphs corresponding to different values of
$\sigma_{{L}}$, where $\sigma_{V}=1$. Curves of different colors represent the
number of periods ($n=1$ (blue), $n=2$ (red), $n=3$ (green), and $n=4$
(black)). The lower plots illustrate that with high probability, the algorithm
successfully learns to stabilizes the system after the significantly short
total time length of $\boldsymbol{\tau}=8$.

Figure 3: Here, we report the percentage of successful stabilizations by
Algorithm 1, versus $\sigma_{V}$ that denotes the standard deviation of the
randomization through the signal $V_{t}$. The graphs correspond to different
values of $\boldsymbol{\tau}$, while $\sigma_{{L}}=1$ is fixed. Similar to
before, colors distinguish the number of periods ($n=1$ (blue), $n=2$ (red),
$n=3$ (green), and $n=4$ (black)). This figure depicts that descent
randomization in Algorithm 1 is sufficient to stabilize the system fast.

Figure 4: The upper graph presents the percentage of successes in learning to
stabilize, versus the ratio $r$, where $R=rI_{q}$. The lower plot is
$\boldsymbol{\overline{\lambda}}\left({A}_{\boldsymbol{\tau}}+{B}_{\boldsymbol{\tau}}\boldsymbol{{L}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)\right)$
versus $r$. In both cases, $\sigma_{{L}}=\sigma_{V}=1,\boldsymbol{\tau}=10$.

In this section, we analyze the performance of Algorithm 1 by simulating a
system that evolves according to (1), where the true dynamics matrices are

$A_{\star}=\begin{bmatrix}&-0.46\;&0.06\;&0.11\\\ &-0.45\;&0.27\;&0.27\\\
&0.20\;&0.18\;&0.19\end{bmatrix},\quad
B_{\star}=\begin{bmatrix}&-0.40\;&0.44\\\ &0.08\;&-0.48\\\
&-0.43\;&-0.49\end{bmatrix}.$

These matrices are chosen randomly and are relatively similar to some
dynamical models for aerodynamic systems [27]. Importantly, the open-loop
system is explosive;
$\boldsymbol{\overline{\lambda}}\left(A_{\star}\right)>0$, such that two of
the three eigenvalues of the transition matrix $A_{\star}$ have positive real-
parts. Therefore, stabilization of the dynamical system $A_{\star},B_{\star}$
is a sufficiently challenging experiment for Algorithm 1.

Further, the coefficient matrix of the diffusion term in (1) is
$C_{\star}=I_{p}$ in the following experiments, and the continuous-time
dynamics in (1) is simulated through time-discretization steps of length
$10^{-3}$. Further, the value of $\epsilon=0.2$, that reflects the length of
the time pieces that the randomization signal $V_{t}$, is fixed in the sequel.
All simulations are repeated $100$ times, and the corresponding results are
reported based on all replicates of the dynamical system understudy. Unless
otherwise explicitly mentioned, the matrices $Q,R$ in (2) are set to be
identity matrices of proper dimensions.

The first set of graphical results showcase the performance of Algorithm 1 in
learning the unknown truth $A_{\star},B_{\star}$, in a relatively short time
period. In Fig. 1, it can be seen that as the stabilization time
$\boldsymbol{\tau}$ that the algorithm spends to interact with the system and
collect data increases, the accuracy of learning the unknown truth
$A_{\star},B_{\star}$ improves. In lights of Theorem 2, this is sufficient
(though, not necessary) for fast and successful stabilization, as indicated in
the following figures as well.

Fig. 2 illustrates the effects of $\sigma_{{L}}$ (the standard deviation of
the normal distribution for the random feedback matrices ${L}_{j}$) in
Algorithm 1, as well as the influence of the number of periods $n$ and the
stabilization length $\boldsymbol{\tau}$, while $\sigma_{V}=1$ is fixed. Note
that $5\leq\boldsymbol{\tau}\leq 10$ is a remarkably short time frame for
stabilization. Clearly, the proposed algorithm is able to stabilize the
unknown systems very fast, especially for $\sigma_{{L}}=1.0,1.25$ that are
shown in the lower two graphs. Moreover, the positive effects of
$n,\sigma_{{L}}$ on the probability of successful stabilization reflect the
role of _diverse_ random feedback matrices in both the quantitative (i.e., the
number of times they are renewed; $n$) as well as the qualitative (i.e., their
magnitudes; $\sigma_{{L}}$) senses. Note that $\sigma_{{L}}$ cannot be too
large, since otherwise, the system explodes too fast and defeats the purpose
of stabilization.

In Fig. 3, we study the role of the randomization signal $\sigma_{V}V_{t}$ on
the performance of Algorithm 1. For four different stabilization lengths
$\boldsymbol{\tau}$, different graphs are plotted for the success rates of
learning to stabilize the system versus $\sigma_{V}$. As one can expected,
larger randomizations help the algorithm to explore faster such that the
probability of stabilization grows with the coefficient $\sigma_{V}$. So, a
descent randomization suffices for quickly learning to stabilize through
Bayesian methods.

The final figure of this section illustrates the effect of positive definite
matrices $Q,R$ in Fig. 4. Recall that once Algorithm 1 provides the sample
$\left[{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right]^{\top}$, we let
$Q=I_{p}$ and $R=rI_{q}$, and use
$\boldsymbol{{K}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)$
that solves
$\Phi_{{A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}}\left(M\right)=0$ in
(2), to find
$\boldsymbol{{L}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)$.
Then, we apply the linear feedback policy
$U_{t}=\boldsymbol{{L}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)X_{t}$
to the system to stabilize it. The upper graph in Fig. 4 plots the probability
of stabilization versus the coefficient $r$, while the lower plot is
$\boldsymbol{\overline{\lambda}}\left({A}_{\boldsymbol{\tau}}+{B}_{\boldsymbol{\tau}}\boldsymbol{{L}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)\right)$
when $r$ varies.

According to these graphs, smaller $R$ matrices help stabilization. This
result can be interpreted through the role of matrices $Q,R$ in minimizing
quadratic cost cost functions $X_{t}^{\top}QX_{t}+U_{t}^{\top}RU_{t}$, subject
to the linear dynamics in (1). It is well-known that linear feedbacks
$\boldsymbol{{L}}\left({A},{B}\right)$ are optimal policies for that purpose
[1, 2]. Accordingly, for the fixed matrix $Q=I_{p}$, smaller $R$ matrices
provide the control signal more freedom for moving the positive-real
eigenvalues of $A_{\star}$ to the left half-plane in the complex plane.

In addition, the second graph in Fig. 4 illustrates a data-driven method for
optimizing the choice of $Q,R$. Indeed, since in practice
$A_{\star},B_{\star}$ are unknown, one can optimize the stabilization
procedure by selecting the matrices $Q,R$ that minimize
$\boldsymbol{\overline{\lambda}}\left({A}_{\boldsymbol{\tau}}+{B}_{\boldsymbol{\tau}}\boldsymbol{{L}}\left({A}_{\boldsymbol{\tau}},{B}_{\boldsymbol{\tau}}\right)\right)$.
This corroborate the result of Theorem 2 about the effect of stability margins
on stabilization based on approximations of the unknown true dynamical models.

##  5 Conclusion and Future Directions

This work proposes the first algorithm for fast stabilization of unknown
stochastic continuous-time linear dynamical systems. It is illustrated that
the presented algorithm, that utilizes Bayesian methods for learning to
stabilize from the observed state trajectories, performs successfully in a
relatively short time period. We establish theoretical results quantifying the
effects of larger dimensions and smaller stability margins on the difficulty
of stabilizing an unknown system. Moreover, numerical analyses are reported
showcasing the roles of different parameters on the performance, indicating
that moderately larger randomizations lead to faster stabilization.

As the first study on a canonical problem in adaptive and learning-based
control, this work introduces multiple interesting problems for future work.
First, establishment of theoretical performance guarantees for the proposed
algorithm is of interest to understand the fundamental obstacles in learning-
based stabilization policies. Besides, study of the performance in relevant
problems such as network systems, non-linear dynamics, and partially observed
state trajectories, are different directions for further investigations.
Finally, characterizations of Bayesian learning algorithms in similar tasks in
signal processing and control such as optimal output-tracking and adaptive
filter design, constitute important research problems for future work.

## References

  * [1] Goong Chen, Guanrong Chen, and Shih-Hsun Hsu.  Linear stochastic control systems, volume 3.  CRC press, 1995.
  * [2] Jiongmin Yong and Xun Yu Zhou.  Stochastic controls: Hamiltonian systems and HJB equations, volume 43.  Springer Science & Business Media, 1999.
  * [3] Daniel T Gillespie.  Stochastic simulation of chemical kinetics.  Annu. Rev. Phys. Chem., 58:35–55, 2007.
  * [4] Neil D Lawrence, Mark Girolami, Magnus Rattray, and Guido Sanguinetti.  Learning and inference in computational systems biology.  MIT press, 2010.
  * [5] Huyên Pham.  Continuous-time stochastic control and optimization with financial applications, volume 61.  Springer Science & Business Media, 2009.
  * [6] Petr Mandl.  Consistency of estimators in controlled systems.  In Stochastic Differential Systems, pages 227–234. Springer, 1989\.
  * [7] Tyrone E Duncan and Bozenna Pasik-Duncan.  Adaptive control of continuous-time linear stochastic systems.  Mathematics of Control, signals and systems, 3(1):45–60, 1990.
  * [8] Tyrone E Duncan, Petr Mandl, and Bożenna Pasik-Duncan.  On least squares estimation in continuous time linear stochastic systems.  Kybernetika, 28(3):169–180, 1992.
  * [9] Tyrone E Duncan, Lei Guo, and Bozenna Pasik-Duncan.  Adaptive continuous-time linear quadratic gaussian control.  IEEE Transactions on automatic control, 44(9):1653–1662, 1999.
  * [10] PE Caines.  Continuous time stochastic adaptive control: non-explosion, $\varepsilon$-consistency and stability.  Systems & control letters, 19(3):169–176, 1992.
  * [11] David Levanony and Peter E Caines.  On persistent excitation for linear systems with stochastic coefficients.  SIAM journal on control and optimization, 40(3):882–897, 2001.
  * [12] Peter E Caines and David Levanony.  Stochastic $\varepsilon$-optimal linear quadratic adaptation: An alternating controls policy.  SIAM Journal on Control and Optimization, 57(2):1094–1126, 2019\.
  * [13] Matteo Basei, Xin Guo, Anran Hu, and Yufei Zhang.  Logarithmic regret for episodic continuous-time linear-quadratic reinforcement learning over a finite-time horizon.  Available at SSRN 3848428, 2021.
  * [14] Mohamad Kazem Shirani Faradonbeh and Mohamad Sadegh Shirani Faradonbeh.  Efficient estimation and control of unknown stochastic differential equations.  arXiv preprint arXiv:2109.07630, 2021.
  * [15] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis.  Finite-time adaptive stabilization of linear systems.  IEEE Transactions on Automatic Control, 64(8):3498–3505, 2018.
  * [16] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis.  Randomized algorithms for data-driven stabilization of stochastic linear systems.  In 2019 IEEE Data Science Workshop (DSW), pages 170–174. IEEE, 2019\.
  * [17] Yasin Abbasi-Yadkori and Csaba Szepesvári.  Regret bounds for the adaptive control of linear quadratic systems.  In Proceedings of the 24th Annual Conference on Learning Theory, pages 1–26. JMLR Workshop and Conference Proceedings, 2011.
  * [18] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar.  Explore more and improve regret in linear quadratic regulators.  arXiv preprint arXiv:2007.12291, 2020.
  * [19] Xinyi Chen and Elad Hazan.  Black-box control for linear dynamical systems.  In Conference on Learning Theory, pages 1114–1143. PMLR, 2021.
  * [20] Mohamad Kazem Shirani Faradonbeh.  Non-Asymptotic Adaptive Control of Linear-Quadratic Systems.  PhD thesis, The University of Michigan, 2017.
  * [21] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis.  Finite time identification in unstable linear systems.  Automatica, 96:342–353, 2018.
  * [22] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis.  On applications of bootstrap in continuous space reinforcement learning.  In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 1977–1984. IEEE, 2019.
  * [23] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis.  Input perturbations for adaptive control and learning.  Automatica, 117:108950, 2020.
  * [24] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis.  On adaptive linear–quadratic regulators.  Automatica, 117:108982, 2020.
  * [25] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis.  Optimism-based adaptive regulation of linear-quadratic systems.  IEEE Transactions on Automatic Control, 66(4):1802–1808, 2020.
  * [26] Paolo Baldi.  Stochastic Calculus: An Introduction Through Theory and Exercises.  Springer, 2017.
  * [27] John T Bosworth.  Linearized aerodynamic and control law models of the X-29A airplane and comparison with flight data, volume 4356.  National Aeronautics and Space Administration, Office of Management …, 1992.

##  Appendix A Proof of Theorem 2

First, define
$\Delta_{1}={A}-A_{\star}+\left({B}-B_{\star}\right)\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)$.
So, (4) and (5) imply that

${\left|\kern-1.29167pt\left|\Delta_{1}\right|\kern-1.29167pt\right|}<-2cp^{-1/2}\boldsymbol{\overline{\lambda}}\left(D_{\star}\right).$
(11)

Now, by applying the linear feedback matrix
$\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)$ to a linear dynamical
system with dynamics matrices ${A},{B}$, we obtain the closed-loop transition
matrix

$D_{1}={A}+{B}\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)=D_{\star}+\Delta_{1}.$

Letting $\lambda_{1},\cdots,\lambda_{k}$ be the eigenvalues of $D_{\star}$,
consider the Jordan decomposition $D_{\star}=P^{-1}\Lambda P$. That is,
$\Lambda$ is a block-diagonal matrix with blocks
$\Lambda_{1},\cdots,\Lambda_{k}$, where the diagonal entries of $\Lambda_{i}$
all are $\lambda_{i}$, and

$\displaystyle\Lambda_{i}=\begin{bmatrix}\lambda_{i}&1&0&\cdots&0&0\\\
0&\lambda_{i}&1&0&\cdots&0\\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&\cdots&0&\lambda_{i}&1\\\
0&0&0&\cdots&0&\lambda_{i}\end{bmatrix}\in\mathbb{C}^{p_{i}\times p_{i}}.$

Suppose that the desired closed-loop stability does not hold. So, if $\lambda$
is an eigenvalue of $D_{1}$ that its real-part is _not_ negative,
$\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)<0$ implies that the
matrix $D_{1}-\lambda I_{p}$ is singular, while the matrix $D_{\star}-\lambda
I_{p}$ is non-singular. This implies that there exists a non-zero vector
$v\in\mathbb{R}^{p}$ for which $\left(D_{\star}+\Delta_{1}-\lambda
I_{p}\right)v=0$. The latter leads to

$v=-\left(D_{\star}-\lambda
I_{p}\right)^{-1}\Delta_{1}v=-P^{-1}\left(\Lambda-\lambda
I_{p}\right)^{-1}P\Delta_{1}v.$

The matrix $\Lambda-\lambda I_{p}$ is block-diagonal, with the blocks

$\displaystyle\Lambda_{i}-\lambda
I_{p_{i}}=\begin{bmatrix}\lambda_{i}-\lambda&1&0&\cdots&0&0\\\
0&\lambda_{i}-\lambda&1&0&\cdots&0\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\
0&0&\cdots&0&\lambda_{i}-\lambda&1\\\
0&0&0&\cdots&0&\lambda_{i}-\lambda\end{bmatrix}.$

Therefore, doing the inversion, the blocks $\left(\Lambda_{i}-\lambda
I_{p_{i}}\right)^{-1}$ of $\left(\Lambda-\lambda I_{p}\right)^{-1}$ have the
following forms [21, 14].

$\displaystyle\left(\Lambda_{i}-\lambda I_{p_{i}}\right)^{-1}=$
$\displaystyle-\begin{bmatrix}\left(\lambda-\lambda_{i}\right)^{-1}&\left(\lambda-\lambda_{i}\right)^{-2}&\cdots&\left(\lambda-\lambda_{i}\right)^{-p_{i}}\\\
0&\left(\lambda-\lambda_{i}\right)^{-1}&\cdots&\left(\lambda-\lambda_{i}\right)^{-p_{i}+1}\\\
\vdots&\vdots&\vdots&\vdots\\\
0&\cdots&0&\left(\lambda-\lambda_{i}\right)^{-1}\end{bmatrix}.$

Using the above formula together with the definition of operator norms for
matrices, we get

${\left|\kern-1.29167pt\left|\left(\Lambda_{i}-\lambda
I_{p_{i}}\right)^{-1}\right|\kern-1.29167pt\right|}^{2}\leq
p_{i}\left|\lambda_{i}-\lambda\right|^{-2},$

where we used the fact that the condition
$\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)\leq-1$ in the theorem,
together with the violation of stability $\Re(\lambda)\geq 0$, yields to
$\left|\lambda_{i}-\lambda\right|\geq 1$.

Nest, putting the recent inequality on
${\left|\kern-1.29167pt\left|\left(\Lambda_{i}-\lambda
I_{p_{i}}\right)^{-1}\right|\kern-1.29167pt\right|}$, the block-diagonal
structure of $\Lambda-\lambda I_{p}$, the definition of matrix operator norms,
and $v=-P^{-1}\left(\Lambda-\lambda I_{p}\right)^{-1}P\Delta_{1}v$, all
together, we obtain

$1\leq{\left|\kern-1.29167pt\left|P^{-1}\right|\kern-1.29167pt\right|}{\left|\kern-1.29167pt\left|P\right|\kern-1.29167pt\right|}p^{1/2}\left(\Re(\lambda)-\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)\right)^{-1}{\left|\kern-1.29167pt\left|\Delta_{1}\right|\kern-1.29167pt\right|},$

that is

$\Re(\lambda)\leq\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)+{\left|\kern-1.29167pt\left|P^{-1}\right|\kern-1.29167pt\right|}{\left|\kern-1.29167pt\left|P\right|\kern-1.29167pt\right|}p^{1/2}{\left|\kern-1.29167pt\left|\Delta_{1}\right|\kern-1.29167pt\right|}.$

According to (11), as long as
$2{\left|\kern-1.29167pt\left|P^{-1}\right|\kern-1.29167pt\right|}{\left|\kern-1.29167pt\left|P\right|\kern-1.29167pt\right|}c<1$,
it holds that $\Re(\lambda)<0$, since Theorem 1 states that
$\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)<0$.

In other words, we have

$\boldsymbol{\overline{\lambda}}\left(D_{1}\right)<0,$ (12)

i.e., $D_{1}$ is a stable closed-loop transition matrix, and we can define

$M=\int\limits_{0}^{\infty}{e^{D_{1}^{\top}t}\left[Q+\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)^{\top}R\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)\right]e^{D_{1}t}}\mathrm{d}{t}.$

Next, it is shown that applying
$\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)$ to a system of dynamics
matrices ${A},{B}$, the following Lyapunov equation holds [14]:

$M=\boldsymbol{{K}}\left({A},{B}\right)+\int\limits_{0}^{\infty}{e^{D_{1}^{\top}t}Fe^{D_{1}t}}\mathrm{d}{t},$

where

$F=\left[\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)-\boldsymbol{{L}}\left({A},{B}\right)\right]^{\top}R\left[\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)-\boldsymbol{{L}}\left({A},{B}\right)\right].$

It is straightforward to see that by writing the above integral Lyapunov
equation in the algebraic form, we have

$\displaystyle
Q+\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)^{\top}R\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)$
$\displaystyle=$ $\displaystyle-D_{1}^{\top}M-MD_{1}$ $\displaystyle=$
$\displaystyle-D_{\star}^{\top}M-MD_{\star}-\Delta_{1}^{\top}M-M\Delta_{1}.$

Leveraging stability of $D_{\star}$, we obtain an integral form of the
Lyapunov equation, as follows:

$\displaystyle M$ $\displaystyle=$
$\displaystyle{\small\int\limits_{0}^{\infty}{e^{D_{\star}^{\top}t}\left[Q+\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)^{\top}R\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)+\Delta_{1}^{\top}M+M\Delta_{1}\right]e^{D_{\star}t}}\mathrm{d}{t}}$
$\displaystyle=$
$\displaystyle\int\limits_{0}^{\infty}{e^{D_{\star}^{\top}t}\left[Q+\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)^{\top}R\boldsymbol{{L}}\left(A_{\star},B_{\star}\right)\right]e^{D_{\star}t}}\mathrm{d}{t}$
$\displaystyle+$
$\displaystyle\int\limits_{0}^{\infty}{e^{D_{\star}^{\top}t}\left[\Delta_{1}^{\top}M+M\Delta_{1}\right]e^{D_{\star}t}}\mathrm{d}{t}$
$\displaystyle=$
$\displaystyle\boldsymbol{{K}}\left(A_{\star},B_{\star}\right)+\int\limits_{0}^{\infty}{e^{D_{\star}^{\top}t}\left[\Delta_{1}^{\top}M+M\Delta_{1}\right]e^{D_{\star}t}}\mathrm{d}{t}.$

Therefore, the definition of matrix operator norm gives

${\left|\kern-1.29167pt\left|M\right|\kern-1.29167pt\right|}\leq{\left|\kern-1.29167pt\left|\boldsymbol{{K}}\left(A_{\star},B_{\star}\right)\right|\kern-1.29167pt\right|}+2{\left|\kern-1.29167pt\left|\Delta_{1}\right|\kern-1.29167pt\right|}{\left|\kern-1.29167pt\left|M\right|\kern-1.29167pt\right|}\int\limits_{0}^{\infty}{{\left|\kern-1.29167pt\left|e^{D_{\star}t}\right|\kern-1.29167pt\right|}^{2}}\mathrm{d}{t}.$

So, according to (11), if

$-20cp^{-1/2}\boldsymbol{\overline{\lambda}}\left(D_{\star}\right)\int\limits_{0}^{\infty}{{\left|\kern-1.29167pt\left|e^{D_{\star}t}\right|\kern-1.29167pt\right|}^{2}}\mathrm{d}{t}\leq
1,$

then we have

${\left|\kern-1.29167pt\left|M\right|\kern-1.29167pt\right|}\leq
1.25{\left|\kern-1.29167pt\left|\boldsymbol{{K}}\left(A_{\star},B_{\star}\right)\right|\kern-1.29167pt\right|}.$

On the other hand, since $F$ is a positive semidefinite matrix, the inequality
$\boldsymbol{{K}}\left({A},{B}\right)\leq M$ holds. Thus, we get

${\left|\kern-1.29167pt\left|\boldsymbol{{K}}\left({A},{B}\right)\right|\kern-1.29167pt\right|}\leq{\left|\kern-1.29167pt\left|M\right|\kern-1.29167pt\right|}\leq
1.25{\left|\kern-1.29167pt\left|\boldsymbol{{K}}\left(A_{\star},B_{\star}\right)\right|\kern-1.29167pt\right|}.$
(13)

To proceed, denote the closed-loop transition matrix of the system ${A},{B}$
under its own linear feedback policy by
${D}={A}+{B}\boldsymbol{{L}}\left({A},{B}\right)$. Further, in the Lyapunov
equation in (6), let $v\in\mathbb{C}^{p}$ be such that
${\left|\kern-1.29167pt\left|v\right|\kern-1.29167pt\right|}=1$ and
${D}v=\lambda v$, where
$\Re(\lambda)=\boldsymbol{\overline{\lambda}}\left({D}\right)$. Thus, letting
$v^{*}$ be the transposed complex conjugate of $v$, we have

$\displaystyle v^{*}\boldsymbol{{K}}\left({A},{B}\right)v$ $\displaystyle=$
$\displaystyle\int\limits_{0}^{\infty}{v^{*}e^{{D}^{\top}t}\left[Q+\boldsymbol{{L}}\left({A},{B}\right)^{\top}R\boldsymbol{{L}}\left({A},{B}\right)\right]e^{{D}t}v}\mathrm{d}{t}$
$\displaystyle=$
$\displaystyle\int\limits_{0}^{\infty}{{\left|\kern-1.29167pt\left|\left[Q+\boldsymbol{{L}}\left({A},{B}\right)^{\top}R\boldsymbol{{L}}\left({A},{B}\right)\right]^{\frac{1}{2}}e^{\lambda
t}v\right|\kern-1.29167pt\right|}^{2}}\mathrm{d}{t},$

So, it holds that

${\left|\kern-1.29167pt\left|\boldsymbol{{K}}\left({A},{B}\right)\right|\kern-1.29167pt\right|}\geq\boldsymbol{\lambda}_{\min}\left(Q\right)\int\limits_{0}^{\infty}{e^{2\boldsymbol{\overline{\lambda}}\left({D}\right)t}}\mathrm{d}{t}\geq\frac{\boldsymbol{\lambda}_{\min}\left(Q\right)}{-2\boldsymbol{\overline{\lambda}}\left({D}\right)}.$
(14)

By putting (13) and (14) together, we get

$\boldsymbol{\overline{\lambda}}\left({D}\right)\leq-\boldsymbol{\lambda}_{\min}\left(Q\right)\left(2.5{\left|\kern-1.29167pt\left|\boldsymbol{{K}}\left(A_{\star},B_{\star}\right)\right|\kern-1.29167pt\right|}\right)^{-1},$
(15)

which provides a stability margin for the closed-loop matrix ${D}$.

Now, according to the above result together with (13), we can ensure that all
eigenvalues of $A_{\star}+B_{\star}\boldsymbol{{L}}\left({A},{B}\right)$ are
on the left open half-plane of the complex plane if $c$ is sufficiently small.
To see that, observe that by
$\boldsymbol{{L}}\left({A},{B}\right)=-R^{-1}{B}\boldsymbol{{K}}\left({A},{B}\right)$,
(13), (4), and (5), the difference matrix

$\Delta_{\star}=A_{\star}+B_{\star}\boldsymbol{{L}}\left({A},{B}\right)-{D}$

is arbitrarily small if $c$ is sufficiently small. Then, we can show that all
eigenvalues of $A_{\star}+B_{\star}\boldsymbol{{L}}\left({A},{B}\right)$ have
negative real-parts, according to (15). Further details are exactly similar to
the procedure of establishing (12) based on (11).

$\blacksquare$