Shared autonomy refers to approaches for enabling an autonomous agent to collaborate with a human with the aim of improving human performance.
However, besides improving performance, it may often also be beneficial that the agent concurrently accounts for preserving the user’s experience or satisfaction of collaboration.
In order to address this additional goal, we examine approaches for improving the user experience by constraining the number of interventions by the autonomous agent.
We propose two model-free reinforcement learning methods that can account for both hard and soft constraints on the number of interventions.
We show that not only does our method outperform the existing baseline, but also eliminates the need to manually tune a black-box hyperparameter for controlling the level of assistance.
We also provide an in-depth analysis of intervention scenarios in order to further illuminate system understanding.

§ INTRODUCTION

Human-AI collaboration forms an integral part of advancing science in domains where neither advances in independent AI nor human experts are able to fully realize the solution to a problem.
It has shown promising and practical advances in deploying synergistic systems to assist humans. With the assist of these powerful artificial systems, human can perform more safely and smoothly or even above their own ability in many complex and challenging tasks, such as aircraft operations [Matni and Oishi, 2008], semi-autonomous driving [de Winter and Dodou, 2011], flying drone control [Backman, Kulić, and Chung, 2021], teleoperation [Kofman et al., 2005, Aarno, Ekvall, and Kragic, 2005] and enabling people with disabilities to enjoy playing video games [XBOX, 2019]. A key question that we further explore is how to balance the control between a human and the assistive system in order to not only help the human in achieving a task successfully, but just as critically maintain their satisfaction of collaboration, or level of autonomy.

Shared autonomy provides a framework to allow human and autonomous agents to interact congruently to improve performance at the task, while still allowing the human to maintain control [Abbink et al., 2018].
Several prior works on shared autonomy rely on specific knowledge of the environment’s dynamics, or the ability to model them accurately [Gopinath, Jain, and Argall, 2017, Javdani et al., 2018, Backman, Kulić, and Chung, 2021], or having data a priori in order to determine the goals of the collaborating human [Reddy et al., 2020, Reddy, Dragan, and Levine, 2018, Carroll et al., 2019, Javdani, Bagnell, and Srinivasa, 2016]. However, for many tasks the computational dynamics model may be unavailable, or determining user goals accurately, in advance of system design, may not be feasible. Therefore, similar to the works by [Reddy, Dragan, and Levine, 2018], [Schaff and Walter, 2020], and [Du et al., 2020] we focus on a model-free approach and do not aim to model user’s goals explicitly.

An important aspect not addressed by the aforementioned prior works is how to allow humans to use the full depth of their expertise towards achieving their goals. Because the agents serves as assistants, a natural assumption is that the agent should only assist the human minimally or intervene only when necessary, while maintaining good performance. This consideration is especially important in domains such as assistive robotics [Javdani et al., 2018, Gopinath, Jain, and Argall, 2017, de Winter and Dodou, 2011] in reality and assistive agent in video games where users may want to feel as independent as possible while performing the task at hand [Verdonck, McCormack, and Chard, 2011, Palmer, Thursfield, and Judge, 2005], AI assisted employee training [Seo et al., 2021] where the AI agent is expected to gradually reduce assistance to ensure the user is learning the objective. Our work focuses on addressing this gap by incentivizing the agent to minimize interventions, while making sure that the human-agent collaboration achieves near-optimal performance. For many tasks, this objective is quite natural. Interventions are intuitively a reasonable proxy to capture user experience because by definition we are optimizing for human control (since more human actions need to be realized), while also achieving greater reward than they could have achieved without assistance.

We introduce two new, model-free reinforcement learning methods: one based on soft-constraints and the other based on hard-constraints on the number of interventions permitted by the user. In the cases where the user is flexible in the number of interventions acceptable, the soft constraint method provides an approach to consider an intervention penalty along with the reward function, and solves it using the dual formulation [Puterman, 2014]. On the other hand, if a user desires strict upper-bounds on the acceptable number of interventions, the hard constraint method provides a procedure to include the intervention constraint directly in the state representation ensuring that the constraint is never violated.

To benchmark our algorithms, we conduct experiments using simulated human agents in the Lunar Lander [Brockman et al., 2016] and Super Mario Bros. [Kauten, 2018] environments. Additionally, for the Lunar Lander environment, we provide an interactive demo with our assistive agents.[Demo and code used  for  experiments can be found at https://github.com/DavidKoleczek/human_marl.] We show that our method outperforms the previous baseline [Reddy, Dragan, and Levine, 2018] in terms of intervention rate and environment returns. Finally, we also provide analysis of the states where the agent takes control as an additional means of validation of the proposed methods.

§ RELATED WORK

Overview of the proposed human in the loop reinforcement learning framework.

Shared Autonomy.
In shared autonomy, the control of a system is shared by human and agent to accomplish a common goal. Earlier works [Crandall and Goodrich, 2002, Kofman et al., 2005, You and Hauser, 2012] assumed that the agent is aware of the common goal. However, this is a strong assumption in new and previously unseen applications, and as a result, more recent works have proposed agents that can infer the user's intent and predict the user's goal from the user's action and environmental dynamics. They do so by formulating this problem as a partially observable Markov decision process (POMDP). Bayesian inference [Javdani et al., 2018, Muelling et al., 2017, Sadigh et al., 2016, Sadigh et al., 2018], inverse reinforcement learning [Ng, Russell et al., 2000, Ratliff, Bagnell, and Zinkevich, 2006, Levine and Koltun, 2012] and hindsight optimization [Javdani, Srinivasa, and Bagnell, 2015]
are the most common approaches to predicting the user's goal in this formulation. These approaches are based on an assumption that the environment dynamics, the goal space, and the user’s policy are known to the agent, which is often violated in practice.
Reddy, Dragan, and Levine, 2018 proposed a model-free shared autonomy framework to relax these assumptions and formulate the problem as a Markov decision process (MDP). This method does not require prior knowledge of environment dynamics, the human's policy, the goal space, and goal representation. Instead, it uses human-in-the-loop reinforcement learning with functional approximation to formulate a policy for the agent learned only from environmental observation and user input. Based on the aforementioned work, [Bragg and Brunskill, 2020] proposed Stochastic Q Bumpers. Rather than simply focusing on improving the current performance of a human, they consider the additional objective of helping a human learn, or optimizing future performance.

Intervention optimization. In the setting of user assistance, there are only a few works that emphasise the influence of the assistive agent on the user. An agent that intervenes too often will reduce a user's advocacy and ultimately affect their experience in the system.To tackle this challenge, Reddy, Dragan, and Levine, 2018 employed deep Q-learning to train the assistive agent. Instead of taking the action with the highest q-value, they first sort the actions in terms of similarity to the user provided action, in descending order, using an action-similarity function. A final action is then selected as the one that is closest to the user's action while ensuring its q-value is not significantly worse than the optimal action. This action selection  addresses the intervention problem implicitly.

By tuning the tolerance of the system to suboptimal human suggestions, which is a black-box hyperparameter, this method can provide different levels of assistance. However, designing such an action-similarity function makes this approach an environment-dependent problem.
Broad, Murphey, and Argall, 2019 proposed to minimize the interventions in a similar way. They accept the user's action only when it is close enough to the optimal action as determined by an optimal controller. However, developing such an optimal controller may require complete knowledge of the environment dynamics and the user's goal. Similar to Broad, Murphey, and Argall, 2019,
Schaff and Walter, 2020 formulate the problem as a constrained MDP where they consider minimizing the amount of interventions an agent makes, subject to the returns of the agent's learned policy being greater than a given constant. In contrast, our work describes a method to maximize returns of the human-AI collaboration, subject to the number of interventions taken being less than a given constant. Additionally, their method only works with on-policy RL algorithms and it needs to set a target return as the constraint, which requires a deep understanding of the environment and user.  [Hoque et al., 2021] and [Hoque et al., 2021] used imitation learning and supervised learning to predict action discrepancy or the novelty and the risk of the state to decide when to intervene, which have shown promising results on robotic tasks.

§ METHOD

We first introduce the problem setup based on the shared autonomy framework [Reddy, Dragan, and Levine, 2018]. We then present our proposed methods that enable the agent to optimize the frequency of interventions, while maximizing the collaborative performance. Our method is model-free and does not assume the knowledge of the environment dynamics, the goal space, or, the user’s policy.

Shared autonomy can be formulated as a MDP, given by a tuple $\{\mathcal{S}, \mathcal{A}_h, \mathcal{A}_a, \mathcal{T}, \mathcal{R}, \gamma \}$, where $\mathcal{S}$ is the set of environment states and $\mathcal A_h$ is the set of actions that can be taken by the human. The set of actions available to the agent is denoted using $\mathcal A_a$. Dynamics, the reward function, and discount factor are represented using $\mathcal{T}$, $\mathcal{R}$ and $\gamma$, respectively. Before choosing an action according to its policy, the agent observes both the environment state $s \in \mathcal S$ and the user's action $a^h \in \mathcal A_h$. Therefore, the effective set of states for the agent is $\overline{S} = \mathcal S \times \mathcal A_h$, and, we define an instance of this set as $\overline{s} \coloneqq [s, a^h]$, a simple concatenation. The MDP that our agent acts in then can be formalized as $\mathcal{M} = \{\overline{\mathcal{S}}, \mathcal{A}_a, \overline{\mathcal{T}}, \mathcal{R}, \gamma \}$, where $\overline{\mathcal{T}}(\overline{s}, a^a, \overline{s}')=\mathcal{T}(s, a^a, s')\pi_h(s', a^{h'})$, where $a^a \in \mathcal{A}_a$, and, $\pi_h$ is the policy of the human user. The goal of the agent is to find the optimal policy $\pi_a^*$ that maximizes the expected discounted sum of rewards:
$\pi_a^* = \argmax \limits_{\pi_a} \mathbb{E}_{\pi}\bigg[\sum_{t=0}^T \gamma^t\mathcal{R}(\overline{s}_t,a_t) \bigg]$. We provide an overview of the proposed agent-human-environment interaction in Figure <ref>.

§.§ Hard Constrained Shared Autonomy

A simple way to control the level of assistance is to limit the discrete amount of instances where the assistive agent can intervene, or override user's input in an episode. Thus, we propose to set a budget, which is the maximum number of times an agent can intervene in an episode, as a hard constraint to limit the behaviour of agent. When the budget is greater than 0, the agent can take any corrective action. However when the budget is exhausted, the agent is only able to accept the user's action. Furthermore, if the agent still attempts to intervene, we add a penalty to the reward in order to reinforce the need for the agent to assist optimally while there is a residual budget.

We introduce budget as part of the environment observed by the agent. The hard constrained shared autonomy MDP can be formalized as $\mathcal{M}_b = \{\overline{\mathcal{S}}_b,  \mathcal{A}_a, \mathcal{T}_b, \mathcal{R}_b, \gamma \}$, where $s^b \in \overline{\mathcal{S}}_b \coloneqq [s, a^h, b]$, $\mathcal{T}_b(s^b, a^a, {s^b}')=\mathcal{T}(s, a^a, s')\pi_h(s', {a^h}')\mathbb{P}(b'|b, a^a, a^h)$. The reward function $\mathcal{R}_b$ is defined in the following equation:

$$\mathcal{R}_b(s^b, a^a, {s^b}') =  R(s, a^a, s') - \begin{cases}
\lambda& \text{$b = 0 $ and $a^a \neq a^h$} \\
0 & \text{else}\\
\end{cases}$$

Here, the hyperparameter $\lambda \geq 0$ refers to the penalty for intervening after the budget is exhausted. The goal of the agent is still to find the optimal policy $\pi_a^*$ that maximizes the expected discounted sum of rewards:
$\pi_a^* = \argmax \limits_{\pi_a} \mathbb{E}_{\pi}\bigg[\sum_{t=0}^T \gamma^t R(s_t^b,a_t) \bigg]$. We also define $I(a^a, a^h) = \begin{cases}
1& \text{$a^a \neq a^h$}\\
0& \text{$a^a = a^h$}
\end{cases}$ as an indicator variable for the occurrence of an intervention.
The method is summarized in Algorithm <ref>. We refer to this method as the budget method in the rest of the paper.

Initialize agent's policy: $\pi_a$, penalty: $\lambda$

not converged
Initialize budget: $b \in \mathbb{Z}^{0+}$

$t\gets0 \dots T$
$a_t^h \sim \pi_h (a_t^h|s_t)$

$s_t^b = [s_t,a_t^h,b]$

$a_t^a \sim \pi_a (a_t^a|s_t^b)$

$I(a_t^a, a_t^h) = 1$ and $b > 0$
$b \leftarrow b - 1$

$a_t^a \leftarrow a_t^h$

Execute action $a_t^a$ and observe $s_{t+1}, r_t$

$a_t^a \neq a_t^h$ and $b=0$
$r_t \leftarrow r_t - \lambda$

Update $\pi_a$ using any method

Hard Constrained Shared Autonomy

§.§ Soft Constrained Shared Autonomy

In hard constrained shared autonomy, we gave the agent an intuitive constraint of a maximum number of interventions. This introduces the problem of balancing utility of the agent and the preservation of user's experience manually using the budget. The optimal budget can be difficult to estimate depending on the environment. Hence, we now relax this hard constraint, and, instead penalize the agent for every intervention it takes, compared to the previous method where we start penalizing the agent only after the exhaustion of the budget. In certain use cases, it may be beneficial to not have a hard cap on the number of interventions. The magnitude of the penalty establishes a trade-off between the increased reward accumulated by intervening over the human action, and the penalty associated with doing so.
As with hard constrained shared autonomy, we introduce a modified reward function:

\begin{align}
\overline{\mathcal{R}}(\overline{s},a^a, \overline{s}') &= \mathcal{R}(s,a,s') + \mathcal{R}_{\texttt{penalty}}(\overline{s},a^a)
\end{align}

\begin{align}
\text{where}\quad\quad    \mathcal{R}_{\texttt{penalty}}(\overline{s},a^a) &=
\begin{cases}
0& \text{$a^h = a^a$}\\
-\lambda& \text{$a^h \neq a^a$}
\end{cases}
% \qquad \lambda > 0
\nonumber
\end{align}

where $\lambda \geq 0$ and $\mathcal{R}_\texttt{penalty}$

penalizes the agent for intervening.
Using $\overline{\mathcal{R}}$, shared autonomy can be recast into the standard reinforcement learning setup. The MDP of this penalty method can be formalized as $\mathcal{M} = \{\overline{\mathcal{S}}, \mathcal{A}_a, \overline{\mathcal{T}}, \overline{\mathcal{R}}, \gamma \}$. The goal of the agent is to find the optimal policy $\pi_a^*$ that maximizes the expected discounted sum of rewards with the modified reward function:
$\pi_a^* = \argmax \limits_{\pi_a} \mathbb{E}_{\pi_a}\bigg[\sum_{t=0}^T \gamma^t\overline{\mathcal{R}}(\overline{s}_t,a_t) \bigg]$.

Intuitively, $\lambda$ is a hyperparameter that encodes the trade-off between performance and the
user's willingness to receive assistance from the agent.

Large $\lambda$ discourages the agent from intervening, but limits the agent's capability as a consequence.

In contrast, small $\lambda$ encourages the agent to intervene more which might enable greater performance, but at the cost of potentially interrupting user's experience more often.

However, choosing an optimal value for $\lambda$ is not intuitive and also varies significantly according to the environment and the scale of rewards.
Instead of leaving the user to fine-tune this sensitive hyperparameter, we propose a method to automatically optimize $\lambda$ using a dual formulation [Haarnoja et al., 2018].

Our objective is to find a optimal policy that maximizes expected return while satisfying a minimum expected intervention constraint. Note that we do not discount rewards as it would result in discounting the intervention penalty as well. We cannot justify this approach in our use case as it is unreasonable to allow for more interventions as an episode grows longer. Formally, we want to solve the following constrained optimization problem:

\begin{equation}
\pi_a^*=\max_{\pi_a}\mathbb{E}_{\pi_a, \pi_h}\left [ \sum_{t=0}^{T} r(s_t, a_t) \right ] \text{s.t.} \; \mathbb{E}_{\pi_a, \pi_h}\left [ \sum_{t=0}^{T}I(a_t^a, a_t^h) \right ] \leq c
\end{equation}

Written as a Lagrangian, we obtain the following constrained objective:

\begin{equation}
\max_{\pi_a}\min_{\lambda \geq 0}
\mathbb{E}_{\pi_a, \pi_h}
\left ( \sum_{t=0}^{T} r(s_t, a_t) +\lambda  \left ( c - \sum_{t=0}^{T}I(a_t^a, a_t^h) \right ) \right )
\end{equation}

According to the preceding equation, we would require an entire episode to be able to evaluate the amount of interventions that occur based on our constraint c. If we wish to optimize at every timestep, we can rewrite the constraint to be a linear function of time: $c' = \frac{c}{t}$. In the case of interventions, this can be thought of as the intervention rate.

\begin{equation}
\max_{\pi_a}\min_{\lambda \geq 0}
\mathbb{E}_{\pi_a, \pi_h}
\left ( \sum_{t=0}^{T} \left ( r(s_t, a_t) +\lambda  \left ( c' - I(a_t^a, a_t^h) \right ) \right ) \right )
\end{equation}

We perform the maximization of $\pi$ using a model-free RL algorithm such as DDQN [Hasselt, Guez, and Silver, 2016] or SAC [Haarnoja et al., 2018], while we optimize $\lambda$ using the following stochastic gradient descent where the update for each time-step is written as follows. Note that the reward term does not depend on $\lambda$.

\begin{equation}
\lambda \gets \lambda - \alpha \nabla_{\lambda}\left ( r(s_t, a_t) +\lambda  \left ( c' - I(a_t^a, a_t^h) \right ) \right )
\end{equation}

\begin{equation}
\lambda \gets \lambda - \alpha ( c' - I(a_t^a, a_t^h) )
\end{equation}

The final algorithm for this method, which we refer to as the penalty adapting method, is listed in Algorithm 2. At each timestep we update the policy, and then additionally perform a single gradient step on the dual variables. This does not give us an exact solution to the dual problem which is impractical to solve in RL. However, we find that this approach works in practice to automatically tune $\lambda$ according to the constraint on interventions. This "penalty-adapting" can be considered optional if the user desires to set the penalty manually and we provide experimental results with and without it. We refer to the method without penalty-adapting as simply, the penalty method.

Initialize agent's policy: $\pi_a$, penalty: $\lambda$, learning rate: $\alpha_\lambda$, normalized constraint: $c'$

Observe $s_0$

not converged
$t\gets0$ …$T$
$a_t^h \sim \pi_h(a_t^h|s_t)$

$\overline{s}_t = [s_t, a_t^h]$

$a_{t}^a \sim \pi_a(a_{t}^a|\overline{s}_t)$

Execute action $a_t^a$ and observe $s_{t+1}, r_t$

$I(a_t^a, a_t^h) = 1$
$r_t \leftarrow r_t - \lambda$

Estimate  $L(\lambda)$ using $(\overline{s}_t, a^a_t, r_t)$

$\lambda \gets \lambda - \alpha_\lambda\nabla_{\lambda}L(\lambda)$

Update $\pi_a$ using any method

Penalty-Adapting Method

The performance of various pilots assisted by copilots trained using the baseline [Reddy, Dragan, and Levine, 2018] method and our methods on the Lunar Lander environment. The grey dashed line represents the reward achieved by the pilot without assistance from any copilot. The purple dashed line represents the overall optimal reward that we achieved on the environment.

§ EXPERIMENTS

In this section we evaluate the performance of our methods on the popular Lunar Lander and Super Mario Bros. environments using different simulated users. The goal of our experiments is to test the central hypothesis that the proposed methods can provide varying levels of assistance to improve the user's performance.

Lunar Lander: A 2D simulation game from OpenAI Gym [Brockman et al., 2016]. The goal of the game is to control the engines of a lunar lander spacecraft to land at a designated landing zone without crashing the spacecraft. Each episode lasts at most 1000 steps. It provides a choice between discrete and continuous action spaces for the pilot to control. For the two-dimensional discrete action space, it consists of six discrete actions that are combinations of the main engine {on, off} and the lateral engines {left, right, off}. For the continuous action space version, the pilot can fire each engine at any power level. The state space is 8 dimensional: position, velocity, angular position, angular velocity, and whether or not each leg is in contact with the ground. The reward function penalizes speed, tilt, fuel usage, and crashing while rewarding landing at the target location.

Super Mario Bros. World 1-1: The first stage in the first world of the classic Super Mario game is implemented by the gym-super-mario-bros library [Kauten, 2018]. The goal of the game is to control Mario and reach the target flag at the end of a map. Each episode lasts at most 1600 steps. The action space consists of 12 discrete actions made up of 7 basic actions {up, down, right, left, jump, run, noop}. {left, right} and {run, jump} can be combined into new actions. The state is clipped into 84X84X4 pixel image. The reward penalizes moving left, standing still, and death while rewarding moving right and reaching the target flag.

As our work is closely related to [Reddy, Dragan, and Levine, 2018], we use their methodology as our baseline to compare the performances of our proposed methods and adopt their terminology of referring to the human operator as the pilot and the assistive agent as the copilot. Much like our method, [Reddy, Dragan, and Levine, 2018] can also provide different levels of assistance by tuning a hyperparameter, $\alpha$, which is the tolerance of the system to suboptimal human suggestions. If q-values of the user's action is less than the threshold of the tolerance, $\alpha q*$, the copilot will intervene. Comparing the q-values of different actions limits the baseline method to value-based method and consequently making it difficult to work on the continuous action space.

§.§ Setup

Similar to [Reddy, Dragan, and Levine, 2018], we design four agents applying different strategies to simulate real human players in the Lunar Lander environment to evaluate our methods:
Noop Pilot: does not apply any action (i.e. always executes a noop action),
Laggy Pilot: the optimal agent with 80% possibility to repeat the previously executed action,
Noisy Pilot: the optimal agent with 25% possibility to take a random action), and
Sensor Pilot: simply tries to move toward the landing site by firing its left or right engine. Compared to the Lunar Lander, Super Mario is much more complex and challenging. Human players commonly fail due to jumping into a pit and failing to avoid enemies or obstacles. Hence a noisy pilot that randomly takes an incorrect action (ex. will randomly fail to avoid enemies) is the most appropriate agent to simulate a human's imperfect behavior.

For each simulated pilot, we train the copilot using the baseline method [Reddy, Dragan, and Levine, 2018] and our proposed methods: the penalty, budget, and penalty adapting methods. In order to make our method more comparable with the baseline, we use DDQN [Hasselt, Guez, and Silver, 2016] with experience replay [Lin, 1993] to train all the agents on Lunar Lander with discrete action space. Our Q-network is a multi-layer perceptron with two layers of 64 neurons in each layer. We use the same method to train the optimal agent for the simulated pilot. In Super Mario the state and the action representations have different dimensionality, so we cannot directly concatenate them into one vector as the input to the network. We first feed the pixel state into four convolutional layers with 32 3X3 filters and stride 2 and one fully-connected layer with the size of 1152 X 512. Then we concatenate the output with the user's action and feed it into three fully-connected layer with the size of 524X128, 128X64 and 64X12.
Except the last layer, every layer applies a rectifier nonlinearity.
In the appendix we show the generalization of our methods by using Soft Actor-Critic [Haarnoja et al., 2018] to train the sensor pilot on Lunar Lander with a continuous action space.

For each method, we train agents with their respective hyperparameters (tolerance, budget, penalty, and intervention rate) which determine different levels of assistance. A detailed listing of the hyperparameters used is located in the appendix. We train 10 agents with different random seeds for each parameter setting and test each over 100 episodes. Finally, we take the average performance of these 10 agents for the final results.

The performance of a noisy pilot assisted by copilots trained using the baseline [Reddy, Dragan, and Levine, 2018] method and our methods on the Mario environment.

A comparison of distributions of state features using data from evaluating a sensor pilot trained with $\lambda$ = 2 on the Lunar Lander environment. Vertical position, vertical speed, and the angle of the lander are the features that show our agent is intervening increasingly at states that are likely to lead to imminent failure, such as when vertical speed is near -0.5.

§.§ Evaluation

We evaluate the performance of our methods with respect to increasing intervention rate. Figures 2 and 3 show the trend of total return at different intervention rates for individual methods on Super Mario and Lunar Lander with discrete action space, respectively. It is evident that our methods greatly improve the performance of most simulated agents. Intuitively, as tolerance threshold $\alpha$ and penalty $\lambda$ decrease, or budget $b$ and intervention rate $c'$ increase, the copilot agent should intervene more frequently and accumulate better reward. Although the hyperparameters are not shown in the figures, the appearance of the data points are consistent with the value of the parameters. For example, data points with lower intervention rate use a lower budget or use a higher penalty.
So by tuning the hyperparameters, the copilot can assist the pilot with a different frequency of interventions, which means that both of the baseline method and our methods can provide different levels of assistance to the user.
More detailed analysis of the performance of each parameter (including standard error) can be found in the appendix. And the results of the agents trained by soft actor-critic method on lunar lander with continuous action space can be found in the appendix.

Next, we compare the performance of different methods. Since we aim to provide different levels of assistance to the user, the most practical way for comparison is setting a target return, which is the user's expectation, and assess which method achieves the target return with lower intervention rate. From the perspective of intervention rate, we can also form this comparison by setting a target intervention rate, which is the level of assistance that the user needs, and finding which method can compile higher return with this intervention rate.

Budget Method:  Compared to other methods, the budget method distributes more evenly across the intervention rate. The intervention rate is always less than or equal to the ratio of the budget and the total time steps. If we keep increasing the budget at a constant rate, the intervention rate will not change dramatically. This method performs extremely poorly when assisting the laggy pilot. This is due to the laggy pilot always taking significantly more time steps to play the game compared to other simulated pilots. As a result more budget is required to achieve better return. For the other three simulated pilots, the budget method shows almost similar performance to baseline method and worse than penalty and penalty adapting method.

Penalty Method:  This method always achieves the optimal reward with lowest intervention rate among the other methods and clearly outperforms the baseline in almost all scenarios. Most notably, the penalty method outperforms the other methods by achieving near optimal returns on the Mario environment with only 0.21 intervention rate. But compared to our other methods, the hyperparameter for this method is environment dependent as we need to have a full understanding of the reward function to determine the appropriate penalty.

Penalty Adapting Method:  This method tends to demonstrate high intervention rate and high reward regardless of the hyperparameter configuration.
Even when the copilot is trained with low intervention rate, such as 0, 0.1 and 0.2, it still accrues significantly higher reward than the unassisted pilot. Though the intervention rate serves as a constraint to limit the behaviour of the copilot, it also guides the copilot when to intervene. It encourages the copilot to intervene when the current intervention rate is less than the constraint. This is the key difference from the budget method, which does not reward intervention. When the benefit of intervening is greater than the penalty, this method will still choose to intervene regardless of the constraint (which is why we refer to it as a soft constraint). Thus, the penalty adapting method has a comparatively high lower bound, even without fine-tuning the intervention rate for the constraint. On the other hand, it exposes the limitation of this method that it cannot handle the case where the user wants very few interventions. Overall, it still has comparable performance with the baseline method, while having the massive upside of not having to tune a black-box assistance level parameter. Effectively by setting an intervention rate of 0.1, the only hyperparameter in this method, the user is directly encoding "I do not want to lose control more than 10% of the time".

Heat maps visualizing the most frequently visited parts of the state space. The plots in the first row show only the positions where interventions occurred, while the second row shows the full trajectories. The intensity represents the percentage of time spent at that position and is normalized across all trials. The parameters we use to train sensor copilots are: $\alpha = 0.7$, penalty = 5, budget = 50, and intervention rate = 0.7, respectively. The realized intervention rate of each method is within a tolerance of +/-0.05 and each method is run for 100 episodes.

§.§ Analysis of Interventions

In having reviewed performances of individual proposed methods, we discussed their efficiency i.e. how intervention rate and target reward effect their ability to assist. We must also assess whether the agents are meaningfully assisting and intervening where necessary. In this contrast, we focus on the states in which our individual methods are deciding to intervene in. In the appendix we visualize a gridworld environment to show how the penalty term in our Soft Constrained Shared Autonomy method influences the behaviour of the assistive agent.

In Figure 4 we examine the distributions of each feature in the Lunar Lander state space, recorded over 100 episodes, conditioned on if an intervention occurred or not.
We hypothesize that interventions will be more strongly distributed around states which under unassisted conditions would indicate imminent failure. These states include moments when the lander is moving too fast, its angle is too steep, or it is too far away from the objective (i.e. moving out of bounds). Conversely, distributions corresponding to where an intervention did not occur will be skewed towards values that indicate that the lander is above the goal, making steady progress, or is stable.
Figure <ref> shows kernel density estimations (KDE) of single features of state, where one KDE corresponds to the states where interventions occurred and the corresponding one represents the states where an intervention did not occur. We observe that three of the features exhibit notably different distributions of states depending on if an intervention occurred: vertical position, vertical speed, and angle. In the most straightforward case, vertical position, relatively fewer interventions tend to occur after the lander has nearly landed at positions near 0 and at the beginning of the episode at positions near 1. We also observe that when vertical speed is higher, more interventions tend to occur. Finally, the interventions tend to occur more frequently as the angle deviates further from 0. Features such as horizontal position, horizontal speed, and angular speed exhibiting similar distributions tells us that these states either are not as critical to deciding if the agent should intervene, or the system intervenes before these features would indicate imminent failure. For example, a high angular speed would indicate the lander is spinning out of control, but the agent does not let it get out of hand in the first place. Overall, this analysis gives us confidence that our system is able to intervene when conditions are certainly about to lead to failure, but also it does not intervene more frequently when it is certainly not necessary.

Figure <ref> uses heat maps to demonstrate at which (x, y) positions in the Lunar Lander environment interventions happen most frequently. For these experiments, we fixed the landing zone, or the goal location, to be at the origin of the frame. Additionally, we executed these experiments using the sensor pilot as its behavior is the most intuitive to visualize. When the x (horizontal) position of the agent is less than -0.1, the lander is to the left of the goal and the pilot fires its left engine to move right towards the goal. It does the opposite when the x position is greater than 0.1, and the pilot does nothing when it is between -0.1 and 0.1. Both the penalty and penalty adapting methods perfectly capture the strategy of the sensor pilot. Almost all the interventions happen on both sides of the helipad when the pilot is firing its left or right engine. Few interventions happen in the area when the pilot does not fire any engine (i.e. it lands via gravity) and only when the lander is close to the ground are interventions made to maintain balance. Additionally, as Figure <ref> showed, more interventions occur when the angle is steep which correlates with why there are more interventions near the ground, but outside the goal area. In this scenario, the copilot must make major adjustments to get the lander to the goal. The baseline method almost captures the strategy, but still makes unnecessary interventions in the area where the agent does nothing.

§ CONCLUSION

We proposed two frameworks for training assistive reinforcement learning agents with a focus on being able to provide different levels of assistance by controlling the amount or the frequency of the interventions taken by the autonomous agent. Our soft-constrained method allows a user to train an agent "out of the box" with minimal and explainable hyperparameter tuning. While our hard-constrained method provides a means to train under an environment where after it violates any constraint, it is not able to continue taking actions in the environment. We analyzed these methods on the Lunar Lander and Super Mario Bros. game environments and showed that it outperformed a previous baseline. We also analyzed where interventions occur with respect to the state space. We believe that shared autonomy with model-free RL is a promising direction to solving this problem because it is able to leverage the wealth of existing RL methods directly, while also giving flexibility to incorporate many other constraints outside of interventions. There is a large space of possible domains and different user experiences to consider. We could potentially try to leverage using real human data from video games and work on implementing our method on a real game. We also wish to test if our method is adaptable to a different distribution of human behavior than at training time and determine if means of goal inference are necessary.

§ ACKNOWLEDGMENTS

This work began as part of the data science industry mentorship course at the University of Massachusetts Amherst. We thank the teaching assistants Xiang (Lorraine) Li and Rico Angell and the instructors Andrew McCallum and Tom Bernardin for their helpful feedback and mentorship. This work was performed in part using high performance computing equipment obtained under a grant from the Collaborative R&D Fund managed by the Massachusetts Technology Collaborative. Finally, we thank Sam Devlin and the anonymous reviewers for their valuable feedback.

[Aarno, Ekvall, and Kragic, 2005]
Aarno, D.; Ekvall, S.; and Kragic, D. 2005.
Adaptive virtual fixtures for machine-assisted teleoperation tasks.
In Proceedings of the 2005 IEEE international conference on
robotics and automation, 1139–1144. IEEE.

[Abbink et al., 2018]
Abbink, D. A.; Carlson, T.; Mulder, M.; de Winter, J. C. F.; Aminravan, F.;
Gibo, T. L.; and Boer, E. R. 2018.
A Topology of Shared Control Systems—Finding Common Ground in
IEEE Transactions on Human-Machine Systems, 48(5): 509–525.

[Backman, Kulić, and Chung, 2021]
Backman, K.; Kulić, D.; and Chung, H. 2021.
Learning to Assist Drone Landings.
IEEE Robotics and Automation Letters, 6(2): 3192–3199.

[Bragg and Brunskill, 2020]
Bragg, J.; and Brunskill, E. 2020.
Fake it till you make it: Learning-compatible performance support.
In Uncertainty in Artificial Intelligence, 915–924. PMLR.

[Broad, Murphey, and Argall, 2019]
Broad, A.; Murphey, T.; and Argall, B. 2019.
Highly parallelized data-driven MPC for minimal intervention shared
arXiv preprint arXiv:1906.02318.

[Brockman et al., 2016]
Brockman, G.; Cheung, V.; Pettersson, L.; Schneider, J.; Schulman, J.; Tang,
J.; and Zaremba, W. 2016.
OpenAI Gym.

[Carroll et al., 2019]
Carroll, M.; Shah, R.; Ho, M. K.; Griffiths, T.; Seshia, S.; Abbeel, P.; and
Dragan, A. 2019.
On the Utility of Learning about Humans for Human-AI Coordination.
In Advances in Neural Information Processing Systems.

[Crandall and Goodrich, 2002]
Crandall, J. W.; and Goodrich, M. A. 2002.
Characterizing efficiency of human robot interaction: A case study of
shared-control teleoperation.
In IEEE/RSJ international conference on intelligent robots and
systems, volume 2, 1290–1295. IEEE.

[de Winter and Dodou, 2011]
de Winter, J.; and Dodou, D. 2011.
Preparing drivers for dangerous situations: A critical reflection on
continuous shared control.
In 2011 IEEE International Conference on Systems, Man, and
Cybernetics, 1050–1056.

[Du et al., 2020]
Du, Y.; Tiomkin, S.; Kiciman, E.; Polani, D.; Abbeel, P.; and Dragan, A. 2020.
Ave: Assistance via empowerment.
Advances in Neural Information Processing Systems, 33.

[Gopinath, Jain, and Argall, 2017]
Gopinath, D.; Jain, S.; and Argall, B. D. 2017.
Human-in-the-Loop Optimization of Shared Autonomy in Assistive
IEEE Robotics and Automation Letters, 2(1): 247–254.

[Haarnoja et al., 2018]
Haarnoja, T.; Zhou, A.; Hartikainen, K.; Tucker, G.; Ha, S.; Tan, J.; Kumar,
V.; Zhu, H.; Gupta, A.; Abbeel, P.; and Levine, S. 2018.
Soft Actor-Critic Algorithms and Applications.
CoRR, abs/1812.05905.

[Hasselt, Guez, and Silver, 2016]
Hasselt, H. V.; Guez, A.; and Silver, D. 2016.
Deep Reinforcement Learning with Double Q-Learning.
In Proceedings of the AAAI Conference on Artificial

[Hoque et al., 2021]
Hoque, R.; Balakrishna, A.; Novoseller, E.; Wilcox, A.; Brown, D. S.; and
Goldberg, K. 2021a.
ThriftyDAgger: Budget-aware novelty and risk gating for interactive
imitation learning.
arXiv preprint arXiv:2109.08273.

[Hoque et al., 2021]
Hoque, R.; Balakrishna, A.; Putterman, C.; Luo, M.; Brown, D. S.; Seita, D.;
Thananjeyan, B.; Novoseller, E.; and Goldberg, K. 2021b.
LazyDAgger: Reducing Context Switching in Interactive Imitation
arXiv preprint arXiv:2104.00053.

[Javdani et al., 2018]
Javdani, S.; Admoni, H.; Pellegrinelli, S.; Srinivasa, S. S.; and Bagnell,
J. A. 2018.
Shared autonomy via hindsight optimization for teleoperation and
The International Journal of Robotics Research, 37(7):

[Javdani, Bagnell, and Srinivasa, 2016]
Javdani, S.; Bagnell, J. A.; and Srinivasa, S. S. 2016.
Minimizing user cost for shared autonomy.
In 2016 11th ACM/IEEE International Conference on Human-Robot
Interaction (HRI), 621–622.

[Javdani, Srinivasa, and Bagnell, 2015]
Javdani, S.; Srinivasa, S. S.; and Bagnell, J. A. 2015.
Shared Autonomy via Hindsight Optimization.
Robotics science and systems: online proceedings, 2015.

[Kauten, 2018]
Kauten, C. 2018.
Super Mario Bros for OpenAI Gym.

[Kofman et al., 2005]
Kofman, J.; Wu, X.; Luu, T. J.; and Verma, S. 2005.
Teleoperation of a robot manipulator using a vision-based human-robot
IEEE transactions on industrial electronics, 52(5):

[Levine and Koltun, 2012]
Levine, S.; and Koltun, V. 2012.
Continuous inverse optimal control with locally optimal examples.
arXiv preprint arXiv:1206.4617.

[Lin, 1993]
Lin, L.-J. 1993.
Reinforcement learning for robots using neural networks.
Technical report, Carnegie-Mellon Univ Pittsburgh PA School of
Computer Science.

[Matni and Oishi, 2008]
Matni, N.; and Oishi, M. 2008.
Reachability-based abstraction for an aircraft landing under shared
In 2008 American Control Conference, 2278–2284.

[Muelling et al., 2017]
Muelling, K.; Venkatraman, A.; Valois, J.-S.; Downey, J. E.; Weiss, J.;
Javdani, S.; Hebert, M.; Schwartz, A. B.; Collinger, J. L.; and Bagnell,
J. A. 2017.
Autonomy Infused Teleoperation with Application to Brain Computer
Interface Controlled Manipulation.
Autonomous Robots, 41(6): 1401–1422.

[Ng, Russell et al., 2000]
Ng, A. Y.; Russell, S. J.; et al. 2000.
Algorithms for inverse reinforcement learning.
In Icml, volume 1, 2.

[Palmer, Thursfield, and Judge, 2005]
Palmer, P.; Thursfield, C.; and Judge, S. 2005.
An evaluation of the psychosocial impact of assistive devices scale.
In Assistive technology: from virtuality to reality, 16,
740–744. IOS Press.

[Puterman, 2014]
Puterman, M. L. 2014.
Markov decision processes: discrete stochastic dynamic
John Wiley & Sons.

[Raffin et al., 2019]
Raffin, A.; Hill, A.; Ernestus, M.; Gleave, A.; Kanervisto, A.; and Dormann, N.
Stable Baselines3.

[Ratliff, Bagnell, and Zinkevich, 2006]
Ratliff, N. D.; Bagnell, J. A.; and Zinkevich, M. A. 2006.
Maximum margin planning.
In Proceedings of the 23rd international conference on Machine
learning, 729–736.

[Reddy, Dragan, and Levine, 2018]
Reddy, S.; Dragan, A.; and Levine, S. 2018a.
Shared Autonomy via Deep Reinforcement Learning.
In Proceedings of Robotics: Science and Systems. Pittsburgh,

[Reddy, Dragan, and Levine, 2018]
Reddy, S.; Dragan, A.; and Levine, S. 2018b.
Where Do You Think You're Going?: Inferring Beliefs
about Dynamics from Behavior.
In Advances in Neural Information Processing Systems.

[Reddy et al., 2020]
Reddy, S.; Dragan, A. D.; Levine, S.; Legg, S.; and Leike, J. 2020.
Learning Human Objectives by Evaluating Hypothetical Behavior.
In International Conference on Learning Representations.

[Sadigh et al., 2018]
Sadigh, D.; Landolfi, N.; Sastry, S. S.; Seshia, S. A.; and Dragan, A. D. 2018.
Planning for cars that coordinate with people: leveraging effects on
human actions for planning and active information gathering over human
internal state.
Autonomous Robots, 42(7): 1405–1426.

[Sadigh et al., 2016]
Sadigh, D.; Sastry, S. S.; Seshia, S. A.; and Dragan, A. 2016.
Information gathering actions over human internal state.
In 2016 IEEE/RSJ International Conference on Intelligent Robots
and Systems (IROS), 66–73. IEEE.

[Schaff and Walter, 2020]
Schaff, C.; and Walter, M. 2020.
Residual Policy Learning for Shared Autonomy.
In Proceedings of Robotics: Science and Systems. Corvalis,
Oregon, USA.

[Seo et al., 2021]
Seo, S.; Kennedy-Metz, L. R.; Zenati, M. A.; Shah, J. A.; Dias, R. D.; and
Unhelkar, V. V. 2021.
Towards an AI Coach to Infer Team Mental Model Alignment in
CoRR, abs/2102.08507.

[Verdonck, McCormack, and Chard, 2011]
Verdonck, M.; McCormack, C.; and Chard, G. 2011.
Irish occupational therapists' views of electronic assistive
British Journal of Occupational Therapy, 74(4): 185–190.

[XBOX, 2019]
XBOX. 2019.
Xbox Adaptive Controller: Xbox.

[You and Hauser, 2012]
You, E.; and Hauser, K. 2012.
Assisted teleoperation strategies for aggressively controlling a
robot arm with 2d input.
In Robotics: science and systems, volume 7, 354.

§ APPENDIX

In this appendix, we first derive transition function dynamics for our custom MDPs and then provide the results trained with Soft Actor-Critic [Haarnoja et al., 2018] on Lunar Lander with continuous action space to show that different from our baseline [Reddy, Dragan, and Levine, 2018] , our method can work with both discrete and continuous action space. Finally, we demonstrate more experiment results about the performance with different hyperparameters of different methods to show how our methods provide different levels of assistance by tuning the hyperparameters on Lunar Lander with discrete action space and Super Mario environments.

§.§ Transition Function Derivations

§.§ Lunar Lander with Continuous Action Space

§.§ How Hyperparameter Influences the Performance

§.§ Learning Curve of Different Methods in Lunar Lander

§.§ Deployment

We briefly present the control loop for using an agent trained with our hard constrained method during evaluation time or a production setting. A very similar control loop can be derived for our soft constrained methods.

Evaluation Loop for a Hard Constrained Agent
Initialize agent's policy: $\pi_a$, budget: $b \in \mathbb{Z}^{0+}$;

$t\gets1$ $\infty$
$a_t^h \sim \pi_h (a_t^h|s_t)$ *get human action
$s_t^b = [s_t,a_t^h,b]$ *modify state for agent policy
$a_t^a \sim \pi_a (a_t^a|s_t^b)$ *sample agent policy
$I(a_t^a, a_t^h) = 1$ and $b > 0$
$b \leftarrow b - 1$ *if an intervention occurred, update budget

$a_t^a \leftarrow a_t^h$ *otherwise do not modify human action

Execute action $a_t^a$ and observe $s_{t+1}$ *take action and transition

§.§ Hyperparameters

Table <ref> shows the hyperparameters we use in the experiments.

The hyperparameters used to train on Lunar Lander and Super Mario. Alpha corresponds to the baseline method, budget for our budget method, penalty for our penalty method and intervention rate for our penalty adapting method.

Lunar Lander                                                                                Super Mario Bros.
Alpha                              c]@c@$[0,0.1,0.2,0.3,0.4,0.5,$
$0.6,0.7,0.8,0.9,1]$                         $[0,0.2, 0.4, 0.6, 0.8 ,1]$
Budget                                  c]@c@$[0,25,50,75,100,125,150,175,200,225,$
$250,275,300,400,500,1000]$     c]@c@$[0, 50, 100, 150, 200,$
$250,300, 350, 400]$
Penalty                                 c]@c@$[0, 0.01, 0.02, 0.05, 0.1, 0.2, 0.5,$
$1, 2, 5, 10, 20, 50]$         $[0, 0.05, 0.1, 0.2, 0.5, 1, 2, 5]$
Intervention rate                       c]@c@$[0,0.1,0.2, 0.3,0.4,0.5,$
$0.6,0.7,0.8,0.9,1]$                        $[0,0.2, 0.4, 0.6, 0.8 ,1]$
Discount factor                         0.99                                                                                0.9
Learning rate                           1e-3                                                                                1e-4
Target network update frequency         1500                                                                                1500
Final exploration rate                  0.05                                                                                0.05
Final exploration frame                 1e5                                                                                1e6
Training frame                          1e6                                                                                1e7
Replay start size                       1000                                                                                1000
Replay buffer size                      50000                                                                                10000
Prioritized experience replay alpha     $/$                                                                                0.4
Prioritized experience replay beta      $/$                                                                                0.6


# A Practical Consideration on Convex Mutual Information

Mingxi Yin, Bingli Jiao, _Senior Member_ , _IEEE_ , Dongsheng Zheng and Yuli
Yang, _Senior Member_ , _IEEE_ M. Yin and B. Jiao (corresponding author) are
with the Department of Electronics, Peking University, Beijing 100871, China
(e-mail<EMAIL_ADDRESS>jiaobl@pku.edu.cn).Y. Yang is with the School of
Engineering, University of Lincoln, Lincoln, U.K. (e-mail:
yyang@lincoln.ac.uk).

###### Abstract

In this paper, we focus on the convex mutual information, which was found at
the lowest level split in multilevel coding schemes with communications over
the additive white Gaussian noise (AWGN) channel. Theoretical analysis shows
that communication achievable rates (ARs) do not necessarily below mutual
information in the convex region. In addition, simulation results are provided
as an evidence.

###### Index Terms:

Convex, mutual information, multilevel coding.

##  I Convex Mutual Information

The study of mutual information (MI) refers to entropies of the channel input
and the noise [1]. This research refers to those involving transmissions of
the multilevel coding schemes over the memoryless additive white Gaussian
noise (AWGN) channel, whereat the overall MI is separated with respect to
split signals [2, 3, 4, 5, 6]. We restrict ourselves to work on the convex MI
which can be found in the previous works [3, 4, 6].

In multilevel coding schemes, there are several approaches to split the bit-
to-symbol mapping of one modulated symbol into different levels, each of which
constructs a coded modulation problem based on their individual MIs. The
overall achievable rate (AR) is obtained by the summation of ARs of all levels
and is limited by the MI [3]. With this constraint, In exchanging for
splitting out a higher MI of one level, those of the other levels must be
lower. Consequently, the convex MI presents with the lowest level at ow
signal-to-noise ratio (SNR).

Since the convex MI suppress the lowest level for its AR to an insignificant
contribution, it makes sense to circumvent this upper bound. Hence, we utilize
a repeated transmission method to improve the lowest level. Because that MI of
every level is approximately in straight line at low SNR [7], the negative
effect of the repetition is small.

For showing the problem explicitly, we split the Quadrature Phase-Shift Keying
(QPSK) constellation for providing an example of convex MI in the multilevel
coding scheme. The QPSK constellation is split into two levels in complex
plan: a low level and a high level. The two constellations are shown in Fig.
1, where the low level mapping is shown in Fig. 1(b) and the high level
mapping is shown in Fig. 1(c). As shown in Fig. 1(a), the alphabet for the
QPSK constellation can be denoted by ${\cal
Q}{\rm{=}}\\{{q_{1}},{q_{2}},{q_{3}},{q_{4}}\\}$, where ${q_{1}}=A+j0$,
${q_{2}}=0+jA$, ${q_{3}}=-A+j0$, ${q_{4}}=0-jA$. Denote the binary information
sequence by the $1\times 2$ vector ${\bf{v}}=[{v^{H}},{v^{L}}]$,
${v^{H}},{v^{L}}\in\\{0,1\\}$.

(a) Actual channel

(b) Equivalent channel for the low level

(c) Equivalent channel for the high level

Figure 1: Equivalent channels for multilevel coded QPSK modulation.

The design of MLC for the QPSK modulation is explained as follows. In the
first step, at the low level, the signal set ${\cal Q}$ is divided into two
parts, namely, the subsets ${\cal Q}({v^{L}}=0)=\\{{q_{1}},{q_{3}}\\}$ and
${\cal Q}({v^{L}}=1)=\\{{q_{2}},{q_{4}}\\}$. Each subset at the low level is
uniquely labeled by the path ${v^{L}}$. Then each of these two subset are
divided into two further subsets ${\cal Q}({v^{L}},{v^{H}}=0)$ and ${\cal
Q}({v^{L}},{v^{H}}=1)$ at the high level, and each subset at this level is
uniquely labeled by the path ${v^{L}}{v^{H}}$. At the high level of QPSK each
subset only contains one signal point, concretely, we have ${\cal
Q}({v^{L}}=0,{v^{H}}=0)=\\{{q_{1}}\\}$, ${\cal
Q}({v^{L}}=0,{v^{H}}=1)=\\{{q_{3}}\\}$, ${\cal
Q}({v^{L}}=1,{v^{H}}=0)=\\{{q_{2}}\\}$, ${\cal
Q}({v^{L}}=1,{v^{H}}=1)=\\{{q_{4}}\\}$. Therefore, by $[{v^{H}},{v^{L}}]$ the
transmit signal can by obtained by $x={\cal Q}({v^{L}},{v^{H}})$. Over the
AWGN channel, the receive signal is given by

$y=x+n$ (1)

which can be modelled by the separated low level and high level channel as
shown in Fig. 1. At the low level, $x\in\\{-jA,jA\\}$ for $v^{L}=1$ and
$x\in\\{-A,A\\}$ for $v^{L}=0$, respectively, where $j=\sqrt{-1}$, $x$ is the
signal in Euclidean space and $v^{L}$ is the bit in Hamming space at the low
level of the separation, $n\sim\mathcal{CN}(0,\sigma^{2})$ denotes the AWGN
and $y$ denotes the channel output.

MI of the low level, i.e., MI between the low level information bit $v^{L}$
and the receive signal $y$, is calculated by [1]

$\displaystyle\begin{aligned}
I(V^{L},Y)=&\int_{-\infty}^{\infty}\sum\limits_{x}\Bigg{[}P_{V^{L}}(V^{L})P_{Y|V^{L}}(y|v^{L})\Biggr{.}\\\
&\qquad\qquad\times\Biggl{.}{\log_{2}}\frac{P_{V^{L}Y}(v^{L},y)}{P_{V^{L}}(v^{L}){P_{Y}}(y)}\Bigg{]}{dy}\\\
=&{\log_{2}}2-\frac{1}{2}\int_{-\infty}^{\infty}\sum\limits_{d=1}^{2}\Bigg{[}P_{Y|V^{L}_{d}}(y|v^{L}_{d})\Biggr{.}\\\
&\qquad\qquad\times\Biggl{.}\log_{2}\frac{\sum\limits_{k=1}^{2}P_{Y|V^{L}_{k}}(y|{v^{L}_{k}})}{P_{Y|V^{L}_{d}}(y|{v^{L}_{d}})}\Bigg{]}{dy}\end{aligned}$
(2)

where $V^{L}$ and $Y$ are random variables for the information bit of low
level, i.e., $v^{L}$, the channel output $y$, respectively, $P(\cdot)$ is
density function of the probability, and $n$ is the AWGN with
$n\sim\mathcal{N}(0,\sigma^{2})$, respectively. The conditional probabilities
$P_{Y|V^{L}_{1}}(y|{v^{L}_{1}})$ and $P_{Y|V^{L}_{2}}(y|{v^{L}_{2}})$ used in
(2) are given by

$\displaystyle P_{Y|v^{L}_{1}}(y|{v^{L}_{1}})=P_{Y|V^{L}=0}(y|{v^{L}=0})=$ (3)
$\displaystyle\frac{1}{{2\pi\sigma^{2}}}\left({\exp\left({-\frac{{{{\left\|{{y}-{q_{1}}}\right\|}^{2}}}}{{\sigma^{2}}}}\right)+\exp\left({-\frac{{{{\left\|{{y}-{q_{3}}}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}\right)$

and

$\displaystyle P_{Y|V^{L}_{2}}(y|{v^{L}_{2}})=P_{Y|V^{L}=1}(y|{v^{L}=1})=$ (4)
$\displaystyle\frac{1}{{2\pi\sigma^{2}}}\left({\exp\left({-\frac{{{{\left\|{{y}-{q_{2}}}\right\|}^{2}}}}{{\sigma^{2}}}}\right)+\exp\left({-\frac{{{{\left\|{{y}-{q_{4}}}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}\right)$

respectively.

Then (2) can be derived as a function of the given SNR $\gamma$ as

$\begin{array}[]{l}\mathcal{I}^{L}(\gamma)=1\\\
-\frac{1}{4}{\mathbb{E}_{W}}\left[{\log\left({1+\frac{{f\left({W,-\sqrt{\gamma}+j\sqrt{\gamma}}\right)+f\left({W,-\sqrt{\gamma}-j\sqrt{\gamma}}\right)}}{{f\left({W,0}\right)+f\left({W,-2\sqrt{\gamma}}\right)}}}\right)}\right]\\\
{\rm{}}-\frac{1}{4}{\mathbb{E}_{W}}\left[{\log\left({1+\frac{{f\left({W,\sqrt{\gamma}+j\sqrt{\gamma}}\right)+f\left({W,\sqrt{\gamma}-j\sqrt{\gamma}}\right)}}{{f\left({W,2\sqrt{\gamma}}\right)+f\left({W,0}\right)}}}\right)}\right]\\\
{\rm{}}-\frac{1}{4}{\mathbb{E}_{W}}\left[{\log\left({1+\frac{{f\left({W,\sqrt{\gamma}-j\sqrt{\gamma}}\right)+f\left({W,-\sqrt{\gamma}-j\sqrt{\gamma}}\right)}}{{f\left({W,0}\right)+f\left({W,-j2\sqrt{\gamma}}\right)}}}\right)}\right]\\\
{\rm{}}-\frac{1}{4}{\mathbb{E}_{W}}\left[{\log\left({1+\frac{{f\left({W,\sqrt{\gamma}+j\sqrt{\gamma}}\right)+f\left({W,-\sqrt{\gamma}+j\sqrt{\gamma}}\right)}}{{f\left({W,j2\sqrt{\gamma}}\right)+f\left({W,0}\right)}}}\right)}\right]\end{array}$
(5)

where ${\mathbb{E}}[\cdot]$ denotes the expectation operator,
$W\sim\mathcal{CN}(0,1)$ denotes the random variable of AWGN, and the function
$f(W,a)$ in (5) is given by

$f(W,a)=e^{-{\left(W-a\right)}^{2}}$ (6)

.

By scaling SNR in the linear manner, numerical results of (5) are plotted as a
function of linear SNR in Fig. 2, where the convexity of MI for the low level
can be found in the SNR region of $\gamma$ in $[0,1.5]$.

Figure 2: MI for the low level.

To work on the convex problem mathematically, the definition of convex
function is recalled as follows.

For $x_{b}>x_{a}$, if

$f(x)<y=\frac{y_{b}-y_{a}}{x_{b}-x_{a}}x$ (7)

holds, $f(x)$ is convex with $x\in[x_{a},x_{b}]$, where $x_{b}$ and $x_{a}$
are two arguments at horizontal axis and $y$ a straight line.

We then prove that the AR of low level is higher than the MI of low level in
the convex region of MI.

##  II Theoretical Analysis and Simulation Confirmation

In this section, the theoretical work uses the definition of AR in the concept
of the transmit bit rate at “arbitrary small” error probability, and the
simulation uses bit error rate (BER) of $10^{-6}$ as the approximation of the
“arbitrary small” with the AR.

The theoretical proof is given in the following subsection and the simulation
results are presented next.

###  II-A Theoretical Proof

###### Lemma 1

For a given signal modulation, the error probability of the transmission keeps
unchanged when

$\mathcal{R}(\gamma)=\kappa\gamma$ (8)

for $\gamma=\gamma_{1}/M$, where $M$ is a positive integer,
$\mathcal{R}(\gamma)$, $\kappa$ and $\gamma$ are the transmission rate of
information bits, a constant and the SNR, and $\gamma_{1}$ is the SNR at
$M=1$, respectively.

###### Proof:

Let us work in AWGN channel model

$y=x+n$ (9)

with $y$, $x$ and $n$ are the channel output, the channel input and the AWGN
component, respectively, where $n\sim\mathcal{N}(0,{\sigma^{2}})$.

Let $x^{\prime}=x/\sqrt{M}$, repeating $x^{\prime}$ for $M$ times and input
all repeated $x^{\prime}$ into (9) changes (9) in the vector form

$\displaystyle=$ (10)
$\displaystyle\underbrace{[x^{\prime},\cdots,x^{\prime},{\rm{}}x^{\prime}]}_{M}+[n^{\prime}_{1},n^{\prime}_{2},\cdots,n^{\prime}_{m},\cdots,n^{\prime}_{M}]$

for $m=1,2,\cdots,M$, where $y^{\prime}_{m}$ and $n_{m}$ are the $m^{th}$
components of channel output and the associate Gaussian noise, respectively.
We note that $n^{\prime}_{m}$ is statistically the same noise as that in (9).

At the channel output, the receiver sums over all components and obtain the
demodulation equation as

$y^{\prime}=Mx^{\prime}+\sum_{m}{n^{\prime}_{m}}$ (11)

where $y^{\prime}$ is the result of the summation and $Mx^{\prime}$ is the
demodulated signal.

Since the SNRs in (11) and (9) are same, the error probability of the former
is exactly same as that of the latter with, however, its rate reduction of
factor $1/M$. Thus, one can find that (8) holds in general. ∎

###### Theorem 1

ARs of the repeated low level can be located in a straight line geometrically
drawn from zero to a point of MI. Thus, there must exist a AR larger than the
MI in the convex region defined by (7).

$\mathcal{R}^{L}(\gamma)=\frac{\mathcal{R}^{L}(\gamma_{1})}{\gamma_{1}}\gamma$
(12)

for $\gamma=\gamma_{1}/M$, where $M$ is a positive integer number,
$\mathcal{R}^{L}(\gamma)$ is the function for the AR of low level at SNR
$\gamma$.

###### Proof:

According to Shannon theory, there exist the capacity achieving codes that
allows the AR of the low level to approach the MI calculated in (5) at a
negligible gap, whereby we write the approximation as

$\mathcal{R}^{L}(\gamma_{1})=I(V^{L};Y)|_{\gamma=\gamma_{1}}=\mathcal{I}^{L}(\gamma_{1})$
(13)

where $I(V^{L},Y)|_{\gamma=\gamma_{1}}$ denotes the MI of low level at
$\gamma=\gamma_{1}$.

Using Lemma 1 to $\mathcal{R}^{L}$ yields

$\mathcal{R}^{L}(\gamma_{M})=\frac{\mathcal{R}^{L}(\gamma_{1})}{\gamma_{1}}\gamma_{M}=\frac{\mathcal{I}^{L}(\gamma_{1})}{\gamma_{1}}\gamma_{M}$
(14)

∎

The numerical results of (14) are plotted for $M=1,2,4,8$ in Fig. 3 to provide
an intuitive view of

$\mathcal{R}^{L}(\gamma_{M})>\mathcal{I}^{L}(\gamma_{M})$ (15)

when $\gamma_{M}$ in the convex region $[0,1.5]$, due to that Fig. 2 shows
that in this region

$\mathcal{I}^{L}(\gamma_{M})<\frac{\mathcal{I}^{L}(\gamma_{1})}{\gamma_{1}}\gamma_{M}$
(16)

Finally, since (14) holds for the relationship between the MI of a signal
modulation and the AR of the repeated modulate signal in general, there is an
insignificant difference between the MI and AR when MI curve is geometrically
close to a straight line. It is lucky that the MI of higher level agrees with
the straight line at low SNR [7, Theorem 1]. This issue would be in our future
interests.

###  II-B Practical Simulation

To confirm the theoretical proof in the above section, simulations are
performed using MATLAB.

LDPC codes with the code length of 64800 are selected from DVB-S.2 standard to
simulate the BER performance of the low level as given in (1), which is
obtained by splitting the QPSK constellation. In simulations, different code
rates are adopted for searching simulated SNR denoted by $\hat{\gamma}_{1}$
for BER at $10^{-6}$.

In decoding procedures of the low level, soft decision based on log–likelihood
ratios (LLRs) is used in the signal demodulation, given by

$\displaystyle\begin{aligned}
&{\rm{LLR}}^{L}=\ln\frac{\displaystyle{\sum\limits_{v^{L}=0}{\exp\left({-\frac{{{{\left\|{y-x}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}}}{\displaystyle{\sum\limits_{v^{L}=1}{\exp\left({-\frac{{{{\left\|{y-x}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}}}\\\
&=\ln\frac{\displaystyle{{\exp\left({-\frac{{{{\left\|{y-A}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}+{\exp\left({-\frac{{{{\left\|{y+A}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}}}{\displaystyle{\exp\left({-\frac{{{{\left\|{y-jA}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}+{\exp\left({-\frac{{{{\left\|{y+jA}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}}.\end{aligned}$
(17)

The LLR of the high level is given by

${{\rm{LLR}}^{H}}=\left\\{\begin{array}[]{l}\ln\frac{{\exp\left({-\frac{{{{\left\|{y-{A}}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}}{{\exp\left({-\frac{{{{\left\|{y+A}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}},\
{{\rm{LLR}}^{L}}>0\\\
\ln\frac{{\exp\left({-\frac{{{{\left\|{y-jA}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}}{{\exp\left({-\frac{{{{\left\|{y+jA}\right\|}^{2}}}}{{\sigma^{2}}}}\right)}},\
{{\rm{LLR}}^{L}}\leq 0\end{array}\right.$ (18)

In simulations, we first set a code rate $R_{1}=1/2$ for the low level and
find $\hat{\gamma}_{1}=2.10=3.23$dB at which the BER of the low level achieves
$10^{-6}$ as shown in Fig. 4. Then, we set $R_{M}=1/4,1/8,1/16$ (according to
$M=2,4,8$ in (14)) and obtained BER results are shown in Fig. 4 as well.

By picking up all SNRs with respect to the BER at $10^{-6}$ for the cases that
$M=1,2,4,8$, we plot these points and the responding ARs in Fig. 3, for the
comparison with theoretical results of MI. In this figure, two points of
simulated ARs, i.e., ARs for the cases that $M=4,8$, are beyond the curve of
the convex MI. SNR gains between simulated ARs and the convex MI are found at
$0.57$dB when $M=4$, and $1.62$dB when $M=8$.

Figure 3: Simulated ARs for the low level.  Figure 4: BER performance for the
low level.

##  III Conclusion

The present work shows that ARs of the low level in multilevel coding are not
necessarily limited by the convex MI with split signals. In the theoretical
work, we have proved that ARs of repeated signals of the low level can be in a
straight line when approaching zero SNR instead of along with the convex MI of
the low level. Simulation results have confirmed the straight line of the AR
and its possibility beyond the MI.

## References

  * [1] C. E. Shannon, “A mathematical theory of communication”, The Bell System Technical Journal, vol. 27, no. 3, pp. 379-423, Jul. 1948.
  * [2] H. Imai and S. Hirakawa, “A new multilevel coding method using error correcting codes”, IEEE Trans. Inf. Theory, vol. 23, pp. 371–377, May 1977.
  * [3] U. Wachsmann, R. F. H. Fischer and J. B. Huber, “Multilevel codes: theoretical concepts and practical design rules”, _IEEE Trans. Inf. Theory_ , vol. 45, no. 5, pp. 1361-1391, July 1999.
  * [4] M. Jaber Borran and B. Aazhang, “Multilevel codes and iterative multistage decoding: rate design rules and practical considerations”, _Proc. IEEE WCNC2000_ , Chicago, IL, 2000, pp. 36-41 vol.1.
  * [5] Dong-Feng Yuan, Peng Zhang, Qian Wang and W. E. Stark, “A novel multilevel codes with 16QAM”, _Proc. IEEE WCNC2002_ , Orlando, FL, USA, 2002, pp. 260-263 vol.1.
  * [6] M. Chen, T. Li and O. M. Collins, “A Computationally Efficient Multilevel Coding Scheme for ISI Channels”, _IEEE Trans. Inf. Theory_ , vol. 53, no. 12, pp. 4556-4566, Dec. 2007.
  * [7] Y. Wu, D. Guo and S. Verdú, “Derivative of Mutual Information at Zero SNR: The Gaussian-Noise Case”, _IEEE Trans. Inf. Theory_ , vol. 57, no. 11, pp. 7307-7312, Nov. 2011.