Christos Dimitrakakis
email: christos.dimitrakakis@a3.epfl.ch

Firas Jarboui
email: firasjarboui@gmail.com

David C Parkes
email: parkes@eecs.harvard.edu

Lior Seeman
email: lseeman@cs.cornell.edu

Multi-view Sequential Games: The Helper-Agent Problem

Keywords: CCS Concepts, Human-centered computing → Collaborative interaction, •Computing methodologies → Multi-agent systems, stochastic games, Human-AI co-operation, human-in-theloop, Markov decision process, backwards induction

Problems where agents wish to cooperate for a common goal, but disagree on their view of reality are frequent. Of particular interest are settings where one agent is an AI "helper agent" and the other is a human. The AI wants to help the human to complete a task but the AI and human may disagree about the world model. This may come about for example because of the limited rationality and biases of the human or because of misaligned reward models. In this paper, we formalize this as the multi-view sequential game, and show that even when the human's model is far from correct, an AI can still steer their behavior to more beneficial outcomes. In particular, we develop a number of algorithms, based on dynamic programming to discover helper policies for the AI, under different assumptions about the AI's knowledge. Experimentally, we show that the AI's beliefs about human model are not required to be accurate in order to act as a useful helper agent.

INTRODUCTION

Situated in the general area of value-aligned AI, we introduce a model of sequential multi-agent decision making for agents whose views of the world disagree. This can occur when agents have simply different utilities, beliefs, or computational bounds. It can lead agents to different conclusions about what the optimal joint policy is, even when they in principle agree on the objectives. Of main interest to us is the case where agents have the same utility function, but their models or utility estimates differ due to bounded rationality or information. This is particularly the case in scenarios where humans and artificially intelligent agents interact. The problem for the AI agent is to design a policy that takes into account human behaviour in order to help the human achieve its actual goal. This is the focus of the present paper.

As an example, consider humans trying to rescue people from a fire, with the aid of robotic agents. The robots may have accurate information about the layout of the building and so may be better equipped to make decisions about where to search. They should, however, take into account the limited knowledge of the human agents. Another example is a doctor trying to plan diagnostic tests for a patient. A diagnostic aid AI may provide a list of recommended tests for the doctor to perform, in order for the doctor to arrive at an accurate diagnosis with a small number of tests.

Formalising this setting leads to a class of sequential multiagent decision problems, extending stochastic games. In particular, while in a stochastic game there is an underlying transition kernel to which all the agents agree, the same is not necessarily true in our setting. Each agent may have a different transition model. In particular, we assume that humans are incorrect about reality, and so the AI must plan taking this into account.

This framework that we develop is applicable to many scenarios involving human-AI collaboration, where there is agreement about the utility function, but disagreement about the optimal plan due to bounded human rationality. In this paper we model this bounded rationality through allowing the human to have an incorrect world model.

We focus on collaborative policies, where the AI takes actions directly in the environment together with the human. The human is assumed to observe the policy of the AI and to best respond to this policy, but for a potentially incorrect model of the world. We consider variations where in addition to the human having an incorrect model of the world, this (incorrect) model is not known by the AI.

In this paper, we examine the helper agent problem from the perspective of an AI trying to help a human. In particular, we model the problem as a generalized stochastic game, and study the power of the helper-AI intervention as the human's model of the world becomes more noisy and also considering that the AI may not completely understand the human's viewpoint. We investigate computational solutions to this problem and demonstrate that the AI can indeed be helpful, even when it misunderstands humans.

In particular, we show that these types of games are significantly different from standard sequential games, as they are not efficiently solveable via backwards induction, even when players take alternating moves with full information and with a finite time horizon. In this paper, we study the effect of a dynamic programming algorithm for finding a policy for the AI, when the human's model is known. In particular, we develop a backwards induction algorithm, which maintains separate transition matrices and values for both players, to find approximately optimal policies for the AI. We provide a number of experimental results for applying this framework to the problem of AI-helper agents. We show that the helper-AI will improve the human's performance unless the human's model is extremely noisy, and as long as the AI understands the human's world model well enough. However, blithely assuming that human model is correct and identical to the planner's can lead to a moderate performance loss. We tested our algorithms on three types of environments. Firstly, hand-crafted environments with small numbers of states, designed to maximise the discrepancy between the views of the human and AI. Secondly, randomly generated environments. Finally, an environment corresponding to a problem in sequential experiment design.

Related work

A related problem is how to use internal rewards to improve the performance of computationally-bounded, reinforcement learning agents [START_REF] Sorg | Internal rewards mitigate agent boundedness[END_REF]. For example, even a myopic agent can maximize expected utility over a long time horizon if augmented with appropriately designed internal rewards. This model can be cast into our framework by allowing the helper agent actions to directly provide rewards to the human. However, unlike AI, it is less natural to consider a reward deliver from the robot to the person. Consequently, we focus on the AI taking actions in the same environment as the human.

Another related problem is how people can be used to train an AI agent [START_REF] Amir | Interactive teaching strategies for agent training[END_REF]. This essentially allows the teacher to demonstrate how to perform a given task. The problem is how to make the best use of opportunities for demonstration. This setting naturally falls within our framework, where the teacher takes the role of our AI and the learner the role of our human. We would need to specify an appropriate advice-giving set of actions for the teacher agent. But previous work assumes that agents have a consistent environment model. More precisely, if the learner plays action a at state s, and the teacher's optimal policy plays a , that doesn't necessarily mean that the learner's assumed optimal continuation matches that of the teacher. Consequently, the learner may perform even worse under if he changes his actions.

The work most closely related to ours is that of environment design [START_REF] Zhang | Policy teaching through reward function learning[END_REF][START_REF] Zhang | Value-based policy teaching with active indirect elicitation[END_REF] and cooperative inverse reinforcement learning [START_REF] Hadfield-Menell | Cooperative inverse reinforcement learning[END_REF]. In these problems, an AI observes a human agent performing a task, and uses inverse reinforcement learning [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF] to estimate the utility function of the human. In environment design, the AI is assumed to associated a limited supply of rewards with different states, and makes multiple interventions in order to modulate the policy selected by the person. In cooperative iRL, the problem is that the AI wants to co-operate with the human in a task, but does not know what the task is. In particular [START_REF] Hadfield-Menell | Cooperative inverse reinforcement learning[END_REF] applies this framework to a set of two-stage game problems where the human demonstrates in the first stage and the AI imitates in the second stage. In particular, they show that the human must take into account the AI's best response when providing demonstrations and they develop a feature-matching algorithm for computing an appropriate demonstration policy for the human. Experimentally, they show that this has a significantly improved performance to uninformed demonstrations. However, it is not at all clear how the human would be able to compute or implement this demonstration policy. The focus of our work is entirely different. Firstly, in our formal model, we do not assume the human and AI have the same environment model. Furthermore our goal is not to infer the rewards of the human agent, but rather to compute a plan so as to optimally guide a human agent with an incorrect model.

Our work also relates to methods for computing optimal strategies in stochastic games [START_REF] Bošanský | Computation of Stackelberg Equilibria of Finite Sequential Games[END_REF][START_REF] Zinkevich | Cyclic equilibria in markov games[END_REF], but differs in that the agents (here an AI and a human) have different models of the transitions between states. Gal and Pfeffer [START_REF] Gal | Networks of influence diagrams: A formalism for representing agentsâ ȂŹ beliefs and decision-making processes[END_REF] have also introduced a general formalism for representing agent beliefs, which could be used to model non-aligned beliefs. However, our focus is specifically on the dynamic, cooperative (multi-view) setting and the question of how to solve the AI's planning problem.

Finally, our methodology for computing AI policies when there is uncertainty about the human's model builds upon the minimax methods developed in [START_REF] Jay | Markovian decision processes with uncertain transition probabilities[END_REF] for Markov decision processes with uncertain transition probabilities.

THE MULTI-VIEW SEQUENTIAL GAME

We model a setting with two players, where we refer to the first player as the AI and the second player as the human. The agents act in a shared world, with the AI and then the human taking an action in each state (the human having observed the action of the AI), leading to rewards and state transitions. Thus, the state dynamic is defined on action pairs-an action of agent 1, and one of agent 2. The way the game is structured is that the AI selects a policy, this policy observed by the human, who then selects a policy.

Each player holds a specific model for the transition law of the dynamic environment, and the players may not agree on what the law is. We assume the AI has the correct world model, and thus when there is disagreement it is the human's model that is incorrect. The AI also forms a belief about the model of the human (either a point belief, or a set-based belief.) We also allow disagreement about the reward function, and in general we allow neither reward function to be correct. To keep the set-up simple, and because we prefer to focus in this first paper on issues involving disagreement in the model rather than reward, we will assume here that if there is disagreement the AI has the correct knowledge of the reward function of the human. Definition 1. (Multi-view stochastic game) A multi-view stochastic game µ is a 2-player game with µ = S, A, ρ, β, B , where

• S is a state space.

• A = A1 × A2.

• ρ = (ρ1, ρ2) is a pair of reward functions ρi : S → R.

• β = {β1, β2} is a set of probability laws, which represent each agent's world model.

• B is the belief agent 1 has about agent's 2 model. (B is either a point model, or a set of possible models of agent 2 ).

• If ρ1 = ρ2, then agent 1 knows the reward function of agent 2. Moreover, in this case we also define ρ * , which we view as the correct reward function for the human.

At time t, both players observe the state st, and player 1 selects an action at,1 ∈ A1(st) ⊆ A1. Player 2 observes at,1 and selects an action at,2 ∈ A2(st, at,1) ⊆ A2. The joint action is denoted by at = (at,1, at,2).

The model of an agent about the world is encapsulated by the probability law βi, such that:

st+1 | s t , a t ∼ βi(st+1 | s t , a t ), (2.1)
where s t = s1, . . . , st and a t = a1, . . . , at. The AI agent also has a belief B about the human agent's model. In particular, agent 1 has a set B = β

(k) 2
k of probability laws, each one of which represents a possible model for the second agent.

Each agent is interested in maximising utility at t with respect to its own reward:

ui,t(s T ) T k=t γ t-1 ρi(s k ), (2.2)
given a sequence of future states s t . We also use ui ui,1 to denote the utility starting from the first step.

For the rest of the paper, unless otherwise state, we assume that ρ * = ρ1. We also make the following, stronger assumption.

Assumption 1. Agent 1's model is correct.
This assumption is natural in our setting, where the AI is helping the human in decision making and especially helping the human to overcome some bounded reasoning patterns or mistaken models. Hence, the actual world model used in all of our experimental results will correspond to Agent 1's transition model. Because of this assumption, then if in addition the AI's reward function is correct in that it reflects what the human's reward "should be" (perhaps distinct from the reward function ρ2 adopted by the human), then the AI's expected utility reflects that of a benevolent and correct planner.

In most of the specific problems that we consider, we further assume ρ1 = ρ2, and assume this is the correct reward function for the human. The only exception is the experiment design problem (Example 1). There the reward implicitly depends on an agent's model (since it is induced from information states), and so the utilities of the two agents differ when their world models differ. In this particular scenario, we assume that Agent 1 knows Agent 2's reward (this follows from agent 1 knowing agent 2's world model.) Assumption 2. All players in this game have Markov policies. The first player's policy being πi(at,1 | st) and the second player's being πi(at,2 | st, at,1). We denote joint policies by π = (π1, π2). This second assumption is w.l.o.g. when the state is the complete observation history.

Properties

While in Markov decision processes (MDPs) it's possible to find policies that are optimal for any starting state, this is not the case here, as we shall see later. For this reason we consider the following solution concept. Definition 2. (Optimal policy) Let σ be a distribution over starting states s1. Then a joint policy π is optimal under σ, β1 iff

u(π) E π β 1 ,σ u1 ≥ E π β 1 ,σ u1 ∀π ,
where

E π β 1 ,σ u1 = T t=1 γ t-1 s∈S ρ * (s)β1(st = s | π, σ).
The optimal policy is defined under the model of agent 1, which we assume to be the correct world model. The reward function adopted is the optimal reward function, and may differ from ρ1 or ρ2.

If player 1 fixes their policy, this creates an MDP for player 2, who can then easily compute their best response policy. In our setting, player 1 announces its policy to player 2. Then player 1 can take into account the reaction of player 2 to his policy. In Markov decision processes, it is traditional to use the concept of a value function. This is the expected utility of a policy from a given starting state. The same concept can be used in our setting. More precisely, for a given decision process µ, the value function V , defined as:

V π i,t (s) E π β i (ui,t | st = s) (2.3)
is the expected utility according to i's model, if we start from state s and follow joint policy π. This policy can be found with a number of dynamic programming algorithms such as backwards induction (for the finite horizon case) and the numerous variants of policy and value iteration for the infinite horizon case [START_REF] Puterman | Markov Decision Processes : Discrete Stochastic Dynamic Programming[END_REF].

In MDPs there is always a uniformly optimal policy that satisfies V π t (s) ≥ V π t (s) ∀s. However, in our setting this is not necessarily the case. When the first player selects a policy, they other player follows by selecting a response. The analogy in the MDP setting would be that the dynamics of the problem change depending on the policy. Thus, it is entirely possible that there is no uniformly optimal policy for the first player. This can be seen by the following counterexample. In this example, the players agree on all rewards. They also agree on all actions in state 2, and about the action (2,2) in state 1. However, they think (1,1) and (2,1) have opposite effects in state 1. They only partially agree about (1,2), which player 1 thinks has only 2/3 probability of staying in state 1.

Unlike MDPs, in Example 1, there is no optimal stationary policy for the infinite horizon discounted case. Moreover, there is a non-stationary policy that outperforms all stationary policies. These policies are generally cyclic, i.e. they obey π(a t+k | s t+k ) = π(at | st) for some k > 1. It is, however, possible to determine them using dynamic programming. In fact, [START_REF] Zinkevich | Cyclic equilibria in markov games[END_REF] describes a backwards induction method for discovering cyclic equilibria in Markov games. Table 1 shows the state values of different policies of the two players for this example, when player 2 plays the optimal response to player 1. 1 There is no stationary policy for player 1 that is optimal from all starting states. However, there is a cyclic policy that achieves this.

π1 π2 V1 V2 1,1 1,1 2
Finally, there are also problems which induce a cyclic behaviour, even if there is a uniformly optimal policy for them. Example 2 shows a particularly simple such problem.

1 See Section 3 for a precise definition.

IN this example, the players agree on all rewards.

There are three states, and two actions for each player.

For the left-most state, the two agents disagree on the effect of pair (1,2), with the first player's model corresponding to the solid blue arrows and the second player's to the dashed red arrows. The agents agree everywhere else. In the middle state, the action pair (1,2) remains there and leads to the rightmost state with equal probability.

ALGORITHMS

When player 1 fixes a policy π1, player 2 needs to solve a maximisation problem. From player 2's perspective, this is an MDP, and so a uniformly optimal policy can be found. Thus, there is always a well-defined best-response policy:

π * 2 (β2, π1) = arg max π 2 E σ,β 2 [u2 | π1, π2]. (3.1)
Consequently, given that player 2 computes a β2-best response, player 1 can always compute the value of any policy π1:

E σ,β 1 [u1 | π1, β2] = E σ,β 1 [u1 | π1, π * 2 (β2, π1)]. (3.2)
Then player 1 needs to find a policy

π * 1 (β1, β2) ∈ arg max π 1 E σ,β 1 [u1 | π1, β2]. (3.3)
In the case where player 1 has the correct reward, and the correct world model, then this will is optimizing the expected utility created by the joint policy induced by the two players. Unfortunately this is not a zero-sum problem. This can be seen by writing it in standard form: Lemma 1. A multiview stochastic game µ can be written as a game Gq(µ) = π, v with joint strategies π and values v, such as the value of the k-th policy tuple π (k) = (π

(k) 1 , π (k) 2 )
for player i is:

v k,i = E σ(s),β i [ui | π (k) 1 , π (k) 2 ]. (3.4)
a subgame perfect Nash equilibrium must exist, the policy space is rather large. For example, for infinite horizon undiscounted problems, we must at least consider all stationary policies, which are O(|S| |A ). For that reason, we develop an approximate algorithm based on dynamic programming.

Dynamic programming approximation

We now describe a dynamic programming approximation. First, we show how to formulate it as a backwards induction algorithm for the case where the AI knows the model of the human. We remind the reader that that player 1 communicates its policy π1 to player 2 and that player 2 can see player 1's action before he chooses his own. At stage t of the program, player 2 has observed the current state st and the action at,1 of the first player, and also knows the future policy of player 1. He now chooses his action

a * t,2 (a1) ∈ arg max a 2 ρ(st)+γ s t+1
β2(st+1|st, a1, a2)V2,t+1(st+1).

For every state and player-1-action, there is a well-defined continuation for player 2. Now, player 1 needs to define his action. This can be done easily, since we know player 2's continuation, and so we can define a value for each stateaction pair for player 1:

Q1,t(st, at,1) = ρ(s)+γ s t+1 β1(st+1|st, at,1, a * 2 (at,1))V1,t+1(st+1).
Action a * t,1 can now be defined as maximizing Q2,1. What remains is to define the values of the current state for both players, which is

Vi,t(st) = Qi,t(st, a * t,i ). (3.5)
Optimality.

Contrary to the MDP setting, this algorithm may not obtain the optimal policy. In addition, for the discounted infinite horizon case, it may not converge to a stationary policy. This is because of the dependency between the future policy of player 1 affects the current action of player 2, and so the effective transition matrix for player 1. More precisely, the transition actually depends on the future joint policy π n+1:T , because this determines the value Q2,t and so the policy of the second player. In practice, this results in a cyclic behavior for infinite-horizon discounted games. Similar cycles have been observed before in non-zero sum Markov games [START_REF] Zinkevich | Cyclic equilibria in markov games[END_REF]. To handle cycles for infinite-horizon problems in the experiments, we simply test each of the instantaneous policies π1 in the cycle, find the best response of player 2, and then select the best policy among those.

To assess the optimality of the algorithm, we compared it with a simple local search algorithm2 for stochastic policies. The table below shows a sample of results for a number of environments. The first method is the dynamic programming algorithm described. As in Section 2, we compared this against the stationary policies extracted from one of the cycles of the algorithm. We also considered stationary stochastic policies found by local search, which could frequently improve over the dynamic program.

It is also interesting to note that if we assume that the human's model and reward matches that of the AI, the problem reduces to an MDP. From result on approximate MDPs [START_REF] Even-Dar | Approximate equivalence of markov decision processes[END_REF], we know that our utility loss will be bounded by the L1 distances between our assumption and reality. In particular, for a finite-horizon γ-discounted problem, the error will be O( β1 -β2 1(1 -γ) -2 ).

The case of unknown beliefs.

In this setting, we assume that we just know that β2 ∈ B. In practice, the AI can simply construct a ball B around its own model, or sample a set of possible model from some distribution. In either case, the question of which belief to plan against is a problem. In prior work in MDPs with uncertain transitions, both minimax or maximax choices were considered [START_REF] Jay | Markovian decision processes with uncertain transition probabilities[END_REF]. We shall consider only the minimax problem here, as we believe it may provide robustness. Even then, though, we have two possible solutions. The first is to consider the minimax problem: min

β 2 ∈B max π 1 E σ,β 1 [u1 | π1, π * 2 (β2, π1)], (3.6)
π * 2 (β2, π1) ∈ arg max π 2 E σ,β 2 (u2 | π1, π2). (3.7)
For a finite B, this simply requires enumerating all possible models. After finding the minimising β2, we simply play the best response π1 to it. Unfortunately, this is somewhat optimistic for our purposes, and it is probably more robust to solve the corresponding maximin problem. max

π 1 min β 2 ∈B E σ,β 1 [u | π1, π * 2 (β2, π1)] (3.8)
The maximin problem is significantly harder, as it requires enumerating all policies π1. However, when B is a factored space, so that each part of the human's transition model can be changed independently of the others, we can use the following DP approach to find a maximin policy: βt ∈ arg min

β 1 E β 1 [V * (st+1) | st, at,1, a * t,2 ] (3.9) Q1,t(st, at,1) = ρ ( st) + γ E β 2 [V * (st+1) | st, at ,1, a * t,2 ] (3.10)
a * 1,1 ∈ arg max a 1 Q1,t(st, a1) (3.11) Vi,t(st) = Qi,t(st, a * t,1 ) (3.12)
In particular, if B is composed of a set of polytopes describing sets of transition probabilities for each state-action pair, then we only need to consider the vertices of this polytope. This is the case when B is the set of transition distributions within an L1 ball of the AI's model, i.e. when B is the set of models β2 satisfying β1(• | s, a) -β2(• | s, a) 1 ≤ ds,a for some permissible error bounds ds,a. This is essentially the approach used in the optimistic value iteration algorithm for UCRL2 [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF].

Example 1: Experiment design

A classical goal in experiment design [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF][START_REF] Lindley | On a measure of the information provided by an experiment[END_REF] is to maximise the expected information gain after T experiments. We assume the AI has an accurate probability table of different parameters, observations and experiments, while the human's model maybe incorrect. It is instructive to consider the particular case where the AI suggests a set of experiments, and the human selects one of them. The AI has two actions, the first leaves the human with a choice between using a stethoscope or a blood exam for antibody count. The second gives a choice between a stethoscope and an X-ray.

In this setting there is a true parameter θ * (the disease status) and we can make experiments a, observing outcomes x. Hence the state at time t is the complete history of experiments and outcomes st = (a k , x k ) t-1 k=1 , with s1 being empty. This can be seen as an information-state MDP, where each agent i has a prior belief ξi(θ) and a set of conditional probabilities pi(x|a, θ) over all outcomes, given an action a = (a1, a2), and disease status θ. Then the transition distribution for each player is decomposed as:

βi(st+1 = (st, at, x) | st, at) = θ∈Θ pi(x | at, θ)ξi(θ | st),
where is βi(θ | st), is the posterior distribution arising from the history st and the likelihood model ξi. After T tests, the game ends and the players obtain reward

ρi(sT ) = θ∈Θ ξi(θ | sT ) ln ξi(θ | sT ),
equal to the negative entropy of the parameter posterior, while ρi(st) = 0 for t < T . Note that in this scenario, the human's expected reward will not match the AI's due to the different posterior.

EXPERIMENTS.

We set out to investigate the performance of a human agent acting in an environment with possibly incorrect beliefs. We model this by the human using a transition matrix that deviates from the true world model. In all cases, we measure the expected utility with respect to correct world model, and provide the AI with the correct world model. Apart from the experiment design setting, both players rewards agree.

Environments and simulation

We experimented on the two detailed domains given in Examples 1 and 2, a number of randomly generated infinitehorizon problems, as well as randomly generated experiment design problems with the structure described in Example 1. In all cases, we measured performance in terms of the AI's model of the world, i.e. we assumed its correctness. To model human inaccuracy, the human model was a noisy version of the AI's model. All simulations were run 100 times for each measured point.

Infinite-horizon problems.

For those problems, we set γ = 0.95. The randomly generated domains had up to 16 states and 4 actions per agent. They were created by sampling transition matrices from uniform distributions on the simplex. All environments had reward of 0.1 in one state, and 1 in another state, with 0 everywhere else.

The human model for these problems was drawn from an product-Dirichlet prior that was 1/ -concentrated around the AI's belief.

Experiment design.

We tested randomly generated experiment design problems with 2 conditions, observations and actions per agent, and with a planning horizon of up to 3 steps. Both the AI and human had the same initial belief over the condition. However, the human's likelihood model p2 was generated by -contaminating the AI's model with the uniform distribution. This avoided creating loops in the information-state MDP for the human (though the AI has no way of knowing that).

Aiding an incorrect human

In our experiments, we considered four kinds of joint policies. We wished to test whether the AI could help improve the joint policy, even when it did not have an accurate idea of the human's beliefs. We examined the behaviour of a number of joint policies as the human's accuracy degrades with increasing . We tested each environment for different values of , with a different generated human belief each time, and measured the average over 100 trials. The cases we considered are given below.

Human only.

The human selects a joint policy according to its belief. This corresponds to the human programming the AI with the policy he thinks would be optimal and the AI and the human then acting in the world.

AI Known.

In this case, the AI is not only autonomous, but it also knows the belief of the human. We expect that in that case, human performance can be significantly improved even when human beliefs are far from being correct.

AI Unknown.

In this case, the AI does not know the human's belief.

More specifically, the AI assumes that its beliefs and those of the human are the same. While this may still help, in some cases it has the opposite effect.

AI Sample.

Finally, we also considered the case where the AI assumes a set of possible beliefs for the human, different from its own. In that case, decision making for the AI involves also solving a minimax problem.

Results

The experimental results for the above cases are shown in Figure 3. The horizontal axis is the amount of error of the human model, while the vertical axis is the expected utility measured under the model of the AI. We show results both for the infinite horizon domains (a-g) and for the experiment design domain (h).

We can see that when the human is correct, all cases obtain the same performance. However, the human's utility quickly deteriorates when he makes all the decisions by himself. If the AI knows exactly what the human model is, then it can significantly increase his performance. However, it is also interesting to investigate what happens when this is no longer true. We see that when the AI simply guesses that the human has the same model as it does, the joint policy is sometimes even worse than only when the human takes decisions. Perhaps surprisingly, sampling and using the minimax policy does not improve upon simply assuming that the human's model is the same as the AI's most of the time (see 3(h)). This might be due to the fact that these policies are overly pessimistic. 3

CONCLUSION AND FUTURE WORK

We introduced a framework for AI-helper agents. This relies on the premise that an AI will be useful for tasks where it could perform better than humans, due to its superior knowledge or computational capabilities. For this reason, we assume that the AI and human have different models of the world, and perhaps different utilities, but that the AI is correct. We show that games of this type, while not solveable exactly by efficient algorithms, can still be tackled with a simple dynamic programming method. Our experiments over a large number of domains, including a realistic experiment design problem, demonstrate that as the human's internal model deteriorates, the AI can still help him maintain his performance close to the best possible level. This was possible even when the human's model was unknown, and the AI simply assumed that he had an identical model to its own.

In future work, we would like to examine algorithms that scale better computationally and that do not suffer from the problems of the dynamic programming heuristic. One idea is to extend gradient methods developed in [START_REF] Amin | Gradient methods for stackelberg security games[END_REF] to the sequential setting. This might be particularly interesting since our results in Table 2 indicate that some performance gain can be achieved using stochastic policies when the human model is known. However, it is unclear whether there exists a viable method for the case when it is unknown.

We would also like to explore different assumptions for this problem. In particular, it would be interesting to see

  Appears in: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AA-MAS 2017), S. Das, E. Durfee, K. Larson, M. Winikoff (eds.), May 8-12, 2017, São Paulo, Brazil. Copyright c 2017, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

Figure 1 :

 1 Figure 1: Non-dominating counter-example. States are indicated by circles, with their reward written within. Squares indicate action pairs at each state. Black dotted lines indicate agreement in the model, while solid blue lines the model of player 1, and red dashed ones that of player 2. Omitted action pairs have arcs directly from the state.

Figure 2 :

 2 Figure 2: States are indicated by circles, with the reward at each state written within. Squares indicate action pairs at each state. Black dotted lines indicate agreement in the transition, while solid blue lines the model of player 1, and red dashed ones that of player 2.

Figure 4 :

 4 Figure4: In this illustration, the AI selects a set of exams out of which the physician can choose. The AI has two actions, the first leaves the human with a choice between using a stethoscope or a blood exam for antibody count. The second gives a choice between a stethoscope and an X-ray.

3 Figure 3 :

 33 Figure 3: Effect of incorrect human knowledge. The horizontal axis denotes the deviation of the human's model from reality. The vertical axis is the expected utility of the policies described in Section 4.2.

Table 1 :

 1 πi are deterministic policies, taking actions a1, a2, a3 in each respective state. The i-th column of Vj shows Vj(i). It can be seen that player 1 has no dominating policy.

				2.9 10.77 11
	1,2	1,2	2	20	19.1 20
	2,1	1,1 10.77 11.23	2 2.9
	2,2	2,2	2	20	2 20
	cyclic cyclic	19.1	20	16.6 20

Table 2 :

 2 Expected utility of policies found by three different algorithms in 6 different environments.

	Cyclic	11 12.8 10.4 0.9 8.5 19.6
	Stationary 11	2.8	9.0 0.9 8.4	11
	Local	11 13.4 10.5 0.9	9 19.4

More precisely, a line search algorithm on the principal axes, combined with random restarts.

Minimax results on the other domains not shown to avoid clutter.how to deal with the case where we assume that the human does not know the AI's policy, and only observes its actions. Finally, a natural extension of our work is to consider the case where the AI learns the reward or the world model of the human agent.


domain: spi info

text:
Amar Zeher
email: amar.zeher@u-bourgogne.fr

Stéphane Binczak

Jérôme Joli
email: jjoli@selecom.fr

Narrowband Digital Filtering With Random Frequency Hopping Spread Spectrum

Keywords: Frequency hopping, narrow band filtering, GSM modulation, High selectivity, FPGA resources

In digital signal filtering, channels with narrow bandwidth need high order digital filter to be selected without introducing modulation errors. If a carrier randomly switches from a channel to another as in military applications, or some civilian communication standards, it is necessary to detect and estimate these jumps before transposing and analyzing signals in the baseband. This paper presents a real time solution to filter narrow band signals with random frequency hopping spread spectrum. The proposed method is based on three steps. Firstly, the detection of Signal Frequency Hopping (SFH) using the Fast Fourier Transform (FFT), an algorithm to estimate the Dominant Frequency Value (DFV) is developed, it is necessary for better refining the original detection, in particular, with modulated signals. Secondly, the estimated frequency value is scaled and used with a Numerically Controlled Oscillator (NCO) in order shift the interest channel to baseband. Thirdly, the transposed channel in base band is selected using low pass Finite Impulse Response (FIR) filters. Whereas, the multi rate filtering techniques guarantee the high selectivity and low orders of these FIR filters. Each of the following stages is described in detail later in this paper, synthesizing these steps leads to the proposed solution, that is validated by using GSM signals. The algorithms are implemented in Field Programmable Gate Array (FPGA) Altera Cyclone III family.

I. INTRODUCTION

The spread spectrum technique was restricted for a long time to the military domain, it is now used in more and more non-military applications. It is also proposed as basic techniques for many future digital communication systems [START_REF] Berder | Identification of frequency hopping communications[END_REF].

Spread spectrum differs from a classical narrow band or broadband systems in that the signal energy is spread over a much wider frequency range, reducing the power spectral density of the signal and providing several advantages.

Spread spectrum signals are difficult to intercept. A spreadspectrum signal may simply appear as an increase in the background noise to a narrow band receiver. An eavesdropper may have difficulty intercepting a transmission in real time if the random sequence is not known.

Spread-spectrum transmissions can share a frequency band with many types of conventional transmissions with minimal interference. This means the possibility of Code Division Multiple Access (CDMA) operation [START_REF] Vucetic | Spread spectrum cdma systems for wireless communications[END_REF].

Frequency Hopping Spread Spectrum (FHSS) is a method of transmitting radio signals by jumping a carrier among many frequency channels, using a pseudo-random sequence known to both transmitter and receiver.

For example, GSM standard uses FHSS method to transmit radio signal among two or more channels depending on the Base Transceiver Station (BTS) capacity. In some situation, operators need to analyze and control the communication traffic of a given BTS, to attenuate or to eliminate some channels for example. For detection and estimation of FHSS, multiple methods based on FFT have been proposed in the literature [START_REF] Beaulieu | Interception of frequency-hopped spread-spectrum signals[END_REF][START_REF] Ko | Ml-based frequency estimation and synchronization of frequency hopping signals[END_REF]. Other methods using wavelet transform and compressive sensing have been discussed in [START_REF] Sirotiya | Detection and estimation of frequency hopping signals using wavelet transform[END_REF][START_REF] Yuan | The detection of frequency hopping signal using compressive sensing[END_REF]. Each of these methods has its advantages and disadvantages about algorithms speed, precision, FHSS parameters (time to hop, frequency of hop). In the context of real time constraints with limited FPGA resources the most appropriate solution is based on FFT algorithm, because it is easier to implement and it has an acceptable computation time.

Furthermore, controlling NCO needs to have the scaled DFV, for that purpose we merely represent the signal in frequency domain, with an additional algorithm to decide on the presence of a signal according to a given selection criterion. It is also possible to used other FHSS detection techniques, such as wavelet or compressive sensing, to elaborate the proposed solution, nevertheless using these algorithms need additional FPGA resources.

This paper discusses an efficient method for detecting and filtering modulated carriers with FHSS. Firstly, the method is developed for single channel with FHSS, after that, the model is generalized to several channels. An example of 3 channels with FHSS is illustrated in the experimental section.

II. FREQUENCY HOPPING DETECTION AND ESTIMATION

The Fourier transform is a well-established theory, it is not discussed in this work. Nevertheless, it may be useful for us to consider some of the essentials of FFT which is simply an algorithm (i.e. a particular method of performing a series of computations) that can compute the discrete Fourier transform much more rapidly than other available algorithms [START_REF] Brigham | The fast Fourier transform and its applications[END_REF]. Here some FFT parameter definition.

• FFT length :it is the number of samples applied to the algorithm, it is a power-of-two; 1024 points unless otherwise specified. It is noted N F F T . • Window function :also known as an apodization function or tapering function, is a mathematical function that is zero-valued outside of any chosen interval used to improve FFT performance. It is noted w. Many formulas of window exist, we discuss some of them later in this section.

• Frequency resolution :it is defined as the ratio of frequency sampling (f s ) and the FFT length. It is noted δf

such as δf = f s N F F T . (1)
Here,

δf = 100 1024 = 0.09765625 MHz. ( 2
)
According to frequency resolution and window function the FFT result is altered by errors. These errors are around 1 dB (best case) to 4 dB (worst case) as shown in Fig. 1. Note that, for frequencies whose value is multiple of δf (δf = 97.6562 KHz), errors are zeros. Here, the used FFT algorithm is provided by Altera FFT MegaCore that is configurable with Megawizard. An algorithm called Discretization Algorithm (DA) is developed to be used with FFT for detecting signals, DA refines the obtained to calculate the exact DFV. DA allows to "distinguish" between channels with different powers, even in the presence of frequency overlapping between modulated carriers. The DA uses some knowledge about signal information (channels spacing, neighbor, etc; with GSM for example).

III. FREQUENCY TRANSPOSITION

Once the frequency carrier is estimated using FFT and DA, the signal is transposed to the base band range. In this context, transposing frequency to the base band domain has two main advantages, it allows multi-rate processing (down-sampling, up-sampling) to use merely low pass filters with low order instead of high order band-pass filters. To this end, NCO is used, it offers several advantages over other types of oscillators in terms of agility, accuracy, stability and reliability.

The Altera MegaCore function generates NCOs customized for Altera devices. The IP Toolbench interface is used to implement a variety of NCO architectures, including ROMbased, CORDIC-based, and multiplier-based once.

The generated output frequency, f N CO for a given phase increment, Φ inc is determined by the following equation

f N CO = f s Φ inc 2 B Hz, (3)
where B is the accumulator precision and f s is the frequency sampling.

The frequency accuracy relative to the clock frequency is limited only by the precision of the arithmetic used to compute the phase. The frequency resolution (δf N CO ), defined as the smallest possible incremental change in frequency is given by

δf N CO = f s 2 B Hz. ( 4
)
In this work, the following parameters are used f s = 100 MHz and M = 18 bits.

The spread spectrum range is 10 MHz (20 to 30 MHz, chosen as an example). Consequently the maximum of baseband range is 10 MHz (if the interest channel is the edge of the spread spectrum, i.e, 20 MHz or 30 MHz), the minimum is 5 MHz (if the interest channel is the middle of the range, i.e, 25 MHz). DA scales the FFT frequencies to NCO phase increment.

The major disadvantages of frequency mixing is the problem of image frequencies that are given by

f img = f + 2f N CO , f N CO > f (high side injection) f -2f N CO , f N CO < f (low side injection).
(5) In fact, these frequencies image are mixed with the signal when down-sampling.

To suppress these unwanted signals, one of the most known methods is image-rejection (or image-suppress) [START_REF] Mohindra | Frequency offset image rejection[END_REF][START_REF] Pesola | Image rejection frequency converter as multi-band receiver[END_REF]. These methods cannot be used in this context because of the randomness of FHSP. Other methods may be used, such as I/Q image rejection [START_REF] Pun | Quadrature sampling schemes with improved image rejection[END_REF]. This method has the advantage to suppress image regardless the randomness of FHSS, it is illustrated in Fig. 4.

IV. MULTI-RATE PROCESSING

Transposing frequency to baseband range allows an efficient multi-rate processing. By reducing sampling rate called downsampling (over-sampling). Finite Impulse Response (FIR) filters with high selectivity (high order) can be realized with fewer FPGA logic elements. Designed FIR with single sampling rate requires significant FPGA resources to have high selectivity.

The multi-rate techniques are used to convert the given sampling rate to the desired sampling rate, and to provide different sampling rates through the system without destroying the signal components of interest. Two discrete signals with different sampling rates can be used to convey the same information [START_REF] Milic | Multirate Filtering for Digital Signal Processing: MATLAB Applications[END_REF].

The down-sampling operation with a down-sampling factor M , where M is a positive integer, power-of-two, is implemented by discharging M -1 consecutive samples and retaining every M th sample.

The up-sampling by an integer factor L is performed by inserting L -1 zeros between two consecutive samples, where L is a positive integer, power-of-two.

The drawback of the down-sampling is the aliasing effect, whereas the up-sampling produces the unwanted spectra in the frequency band of interest.

In this work, Spread spectrum W is equal to 10 MHz, theoretically, this means that the down-sampling factor M must be less than 5, because of the Nyquist-Shannon condition

f s M ≤ 2W ⇒ M ≤ f s 2W ≤ 100 20 = 5. (6)
However, here we allow spectrum overlapping up to the limit of an uncorrupted bandwidth U that must be larger than the half of interest channel bandwidth w. In Fig. 2, if :

• M = 5, Nyquist-Shannon condition is satisfied; no spectrum overlapping, then U = W >> w.

• M = 8, Nyquist-Shannon condition is not satisfied; partial spectrum overlapping, then

U = f s M -W = 100 8 -10 = 2.5 > w. (7)
Thus, the interest channel is not corrupted. • M = 10, Nyquist-Shannon condition is not satisfied; full spectrum overlapping, all the bandwidth is corrupted. Hence, the down-sampling factor M for which the downsampling is optimum without corrupting the signal is M = 8. As mentioned above, up-sampling operation creates aliasing, because of the zeros inserting. These aliases can be removed by the FIR low pass filter. The idea is to up-sampling 2 by 2 instead of 8 in such way that the cascaded FIR filters are clocked by different sampling rates (f s /4, f s /2 and f s ). It is better in hardware implementation because basic operations (multiplication, addition, etc) are done four times, two times faster. Furthermore, FIR filters are low order.

V. MULTI-CHANNEL FILTERING

As explained previously, the solution of narrow band digital filtering with random frequency hopping spread spectrum is the synthesis of three steps. Now, let us explain the mechanism, starting with single path of channel filtering, as shown in Fig. 3.

( In Fig. 4, the signal is split to I and Q signal. After filtering, the sum of I and Q signals gives the filtered single signal. The unwanted image frequencies are removed by summing. I and Q paths together form the single channel filter.

In Fig. 5, the parallel adding of several channel filters gives a n-channels filter. Finally, in Fig. 6, FFT with DA provides Φ inc values to the NCOs block, then NCOs generate corresponding frequencies to shift channels in the n-channels filter.

VI. SELECTIVITY AND EFFICIENCY MEASURES

In this part, the proposed solution has been tested with GSM signal; i.e GMSK modulation with frequency hopping, provided by an Agilent E4438C ESG generator.

This solution remains valid under Time Division Multiple Access (TDMA). position and multi-rate processing, the same filter would have required more than 95% of the whole FPGA resources. As explained previously, the single channel model can be generalized to several channels. The processing of channel is simultaneously performed. Fig. 8 shows a spectrum scope of 3-channel with FHSS. It should be noted that several channel models need an additional FPGA resources. In this example, FPGA resources are about 15%.

Saving FPGA resource percentage F P GA sav is expressed by

F P GA sav = +100 M -1 M %. (8)
According to this expression, the higher is the down-sampling factor M, more the hardware resources are saved. However multi-rate processing would require more FIR filters to eliminate aliasing when up-sampling. A compromise has therefore to be found between multi-rate factors and hardware resources.

VII. CONCLUSION

In this paper, we have proposed a method to select channels under random frequency hopping spread spectrum constraints with high selectivity, by combining three techniques (frequency detection, frequency transposition, multi-rate filtering). Hardware resources are saved by using multi-rate filtering. This method is implemented on a low cost FPGA, the efficiency has been approved with the GSM signal in real time conditions.

This solution can be applied in various fields, for example with GSM signals to filter channels without demodulating, for equalization of power between near and far MS/BTS. It can also used to eliminate unwanted spurious which may be present in the spread spectrum because of the signal processing operations or interferences.

For both modulated and or non modulated carriers, this technique remains valid. It detects weak signals (-80 dBm) and strong signals (-10 dBm) with speed frequency hopping (0.5 ms) with a single and three channels simultaneously. These performances can be extended for more channels by using high-quality FPGA.

Fig. 1 .

 1 Fig. 1. Estimation of approximation errors with different windows, N=1024 points.

Fig. 1

 1 Fig.1is obtained by sweeping non-modulated carrier frequency from 0.1 MHz to 1 MHz and measuring the difference between the expected maximum of power spectrum density and the actual maximum of PSD. As shown in the legend, mean errors of peaks for rectangular window is the highest (3.8841 dB), while the minimum is given by Chebyshev window (0.9304 dB). For this reason, Chebyshev window will be used.The incoming signal is digitized with an Analog to Digital Converter (ADC), the digital signal (data) is converted to an analog signal with a Digital to Analog Converter (DAC). Both ADC and DAC have a 16-bit bus width. This allows to detect weak signals (-80 dBm) and high level signals (-10 dBm). Thus the signal magnitude range is 70 dB. This means that the developed method works for far BTS/Mobile Station (MS) and near BTS/MS.

Fig. 2 .

 2 Fig. 2. Transposing a single channel to base band with spectrum overlapping.

  ) Input frequency transposing; intermediate frequency to base band frequency. The FIR filter (low order, N F IR = 8) attenuates the unwanted frequency image ( f + f N CO ). (2) Down-sampling (by 8 in this example), the Nyquist-Shannon condition is (100/8)/2 = 6.25 MHz. Overlapping is allowed without corrupting 0 to 2.5 MHz band, (cf : Fig. 2). (3) High selectivity FIR filter with low order. It processes the interest channel (attenuation, amplification). (4) Up-sampling 2 by 2 with FIR filters that are clocked at different frequency sampling, for saving FPGA resources. (5) Output frequency transposing (baseband to FI), the image is suppressed by I/Q technique. Cascading these blocks constitutes the filtering path I.

Fig. 3 .

 3 Fig. 3. I path channel filtering.

Fig. 4 .

 4 Fig. 4. Single channel filter.

Fig. 5 .

 5 Fig. 5. n-channels filter.

Fig. 7

 7 Fig. 6. n channel filtering with FHSS detection.

Fig. 7 .

 7 Fig. 7. Single channel FIR filter with FHSS.

Fig. 8 .

 8 Fig. 8. 3-channels FIR filter with FHSS.