Collin Allison

Alan Ruddle
email: alanr@dcs.st-and.ac.uk

Rosa Michaelson
email: r.michaelson@dundee.ac.uk

Collin Allison

Colin Allison

Systems Support for Collaborative Learning

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

From the perspective of good educational practice an online collaborative learning environment should provide certain features for learners:

1. group-work support [START_REF] Michaelson | Web-based Group Work[END_REF] 2. interactive, engaging, responsive 3. real-world input 4. student-centred 5. anytime/anywhere Those pedagogical goals imply certain technical requirements.

Support for group working means that online resources may be shared and used by multiple concurrent readers and writers. This requires concurrency control, and the usual associated concerns with liveness, safety and fairness. In addition, multi-user awareness is important for teamwork. Members of a group need to know what each other are doing, and have appropriate communication options to co-ordinate with each other. In particular, distributed real-time multimedia channels may be used to augment distributed resource coherence [START_REF] Allison | Object Coherence in Distributed Interaction[END_REF].

Interactivity implies that online working is much more than simply browsing lecture notes dumped on the Web. Regardless of the balance of computation between server and client the system must be geared to writers as well as readers. Responsiveness is essential for creating an interactive feel when working on the web. It means that the delay between a user making a request and a result being returned to them should be no longer than some period that is considered reasonable within a particular context. For example, a user working from home over a relatively low bandwidth modem line will have lower expectations than one attached to a high-speed campus network. If a network service is perceived to be slow then it will be seen as an unproductive use of time, and may be abandoned.

Real world input is facilitated by direct Internet connection to real world data sets. For example, students of meteorology may gain access to real satellite weather image downloads within an hour of them happening and can learn from making their own weather predictions which can be later compared with established media channel predictions. The Finesse portfolio management facility [START_REF] Power | The Finesse Portfolio Management Facility[END_REF] allows the management of a portfolio of shares by a student group. The groups maintain their portfolios by buying and selling shares chosen from a database of live data for companies quoted on the London Stock Exchange.

Student-centred means focusing on the user as an individual. It also implies strong monitoring capabilities, for manual inspection or automatic adaptation. In an interactive online environment it is of course possible to implement extensive activity logging (by careful choice of a meaningful activity), which can then be "mined" for useful feedback on a student's use of a set of educational resources. This feedback can be used to inform the resource development and adaptation process and thereby enhance the learning environment.

Anytime/anywhere implies a resilient, highly available web-based service. Availability means coping with faults. Providing a service based on multiple servers can reduce periods of non-availability caused by server crashes. These servers may be distributed across a wide area, possibly globally. If they are also used to share the load then replication becomes an attractive strategy as it can, in principle, also support performance by providing an appropriate ratio of users to servers. This approach is further useful as a practical means of implementing incremental scalability, which may be necessary to cope with a dynamically changing user population.

THE TAGS FRAMEWORK FOR COLLABORATIVE LEARNING

TAGS [START_REF] Allison | An Integrated Framework for Distributed Learning Environments[END_REF] is a framework for the development, deployment and maintenance of webbased collaborative learning environments. At present TAGS is being used by tutors and students in the context of accredited degree programmes at six Scottish universities in ten departments, representing a wide range of subject areas: Physics and Astronomy; Medicine; Languages; Accountancy, Finance and Management; Information Technology; and Educational Studies. Further expansion of types of use is planned. The TAGS framework, see Figure 1, is concerned with supporting highly interactive multi-user, concurrent environments, accessible via standard Web browsers [START_REF] Allison | The TAGS Framework for Web-Based Learning Environments[END_REF]. Requirements of the architecture include concurrency control, availability and responsiveness. When the latter two requirements are supported by replication local concurrency control mechanisms must be subsumed by global coherence. There can be a tension between strong replica synchronisation and maintaining interactive response times. TAGS accordingly provides a plug'n'play set of replication synchronisation mechanisms to support a range of resource types.

Tutors may be computer literate, but are rarely computing specialists with an understanding of distributed systems. Accordingly, a key role for TAGS is to provide useful abstractions for tutors to work with. For example, the three basic abstractions provided for tutors are users, groups, and resources. One can imagine providing tutors with further abstractions such as "course", "class", "assignment" and so on. In our experience systems, which, attempt to constrain the options of course, directors are not popular. It is more productive to provide basic building blocks. For example, the potential to group users readily supports the concept of a class, and the ability to group resources supports the notion of a course consisting of components.

TAGS also provides a developers and application programmers service interface (DAPSI), which allows educational resource developers to concentrate on content, by supplying commonly needed system services.

The project has addressed issues in usability, security, responsiveness, concurrency control, availability and infrastructure Quality of Service (QoS) that would have been unlikely to arise in a pure research environment. Much of the utility of TAGS comes from its strong support for group-based learning, which has in turn resulted in the group ethos permeating the system.

THE USE OF GROUPS AS A STRUCTURING PRINCIPLE

The concept of the group is central to TAGS, where it is used to support many functions, including the following:

• privileges and access control • information dissemination and event awareness • teamwork involving shared, multi-user educational resources • the management of online collaborative learning,

• user-centric portal generation • collaborative development In practical terms, tutors construct a collaborative learning environment by using the Users, Groups and Resources management tool. This sets up arbitrary relationships between users and resources, using groups as the basis for the mapping. Users and groups are unique by name; resources are unique by name and type. Access rights can be specified when a resource is allocated to a group. A resource may simply be distinguished as Read-only or Read-Write, or it may export a more subtle set of access methods. Figure 2 illustrates an example set of relationships between users, groups and resources. When a user is a member of multiple groups who have different access privileges to the same resource then they are credited with the highest level from their set of privileges.

Users Groups Resources

Students

It is hard to overstate the importance of access control and security in online environments.

Privacy is essential to ensure that a student's online work is not corrupted or plagiarised (and is not in itself the result of plagiarism). Authentication is essential to the maintenance of identity, establishing that a user is who they say they are. Once authentication is established, authorisation needs to be performed each time a resource is accessed, to establish whether the user has the right to perform the requested operation on the resource.

The TAGS scheme for distributed authentication and authorisation is shown in Fig. 3. This allows for the secure remote access of distributed resources. When a user logs on to the system they are authenticated against a database (which may be replicated). Once a user is authenticated they may attempt to use a number of resources. Each access attempt is then authorised against the user database. Group membership allows access to resources. A simple web interface is provided to allow the allocation and revocation to groups of access rights to resources.

Note that a group does not explicitly have to be an access control group, or an information dissemination group, or any other type of group -it is the responsibility of the resource to use the groupings as it sees fit.

Support for Shared Resources

The concept of a learning resource in TAGS is deliberately loose. It can be a simple timetable, an automated assessment exercise or an interactive multi-user simulation.

In contrast to learners and tutors, developers are computing specialists. They are the people who develop and maintain resources. It is important to let people play to their strengths, and in the case of developers this means allowing them to focus on providing functionality without worrying about deployment, distribution, and management of a resource. These needs are generic and a collaborative learning environment can provide a useful set of services and interfaces for developers. Generic models for distribution allow a developer to choose the conditions, under which their resource can be made available, replicated for performance or fault tolerance, copied, re-used, and accounted for.

USER-CENTRIC PORTAL GENERATION

The purpose of a web portal in general is to provide a single, initial point of contact for a range of services. It is a technique widely used by web-based service providers. It reduces the time that individuals spend searching, although it only promotes options that are commercially sponsored. Portals sometimes offer facilities for personal customization; for example, an interest in specific sporting events or the local weather forecast. However, these options are very limited. They require identity and registration, which in the context of general web services must be user-driven as the service provider has little idea of who is using a portal. Any type of user may use a search engine portal for example. By and large, web portals are public and cater for anonymous users.

User portals differ from public portals in that they are built entirely around the identity of the user. Their utility in a collaborative learning environment is that they can be generated for individuals and dynamically maintained using information that is already known about an individual's roles and responsibilities. For example, if a lecturer is (i) a 1st Year Advisor of Studies for the Science Faculty, (ii) teaching modules CS3013 and CS2001 and (iii) responsible for tutorial group CS1001/5, all the links to the relevant resources associated with these responsibilities can be aggregated onto a single page. Similarly, a student who is on courses CS3020, IS 1902 and EC4221 will find all their learning resources clearly presented as on their home page.

A users home page is updated dynamically with links to all the resources they have been allocated via their group memberships. This tends to mean that a student has a relatively clutter free, minimal home page; a tutor has more resources; and a course director may have an over-crowded view. Accordingly a view manager is being developed to help users who are members of a large number of groups to manage their home page.

RESOURCE REPLICATION ON CLUSTERS

Groups of servers are referred to as clusters. Replication and clustering can support high availability, good responsiveness and incremental scalability where appropriate middleware is provided.

A resource in TAGS may consist of a set of CGI programs, servlets, static HTML pages, applets, streaming media, multi-way conferencing channels and so on. The important feature of a resource in the clustering context is that it is the unit of replication management. We distinguish between resource-specific requirements and generic service needs. For example, if a resource contains continuous media then, in addition to the generic requirements of responsiveness and availability, it will also need appropriate network QoS for the satisfactory rendering of its media streams. If a resource is shared between many concurrent users then it will also require resource-specific concurrency control. If a resource is the focus of a collaborative effort then it will also need specific multi-user awareness features. Whenever a resource is replicated it will need resourcespecific replication coherence.

The motivation for distinguishing between types of replication coherence is to avoid a "one-size-fits-all" approach. If such an approach is adopted then the synchronisation of replica updates must be able to satisfy the most stringent requirements, such as traditional atomic transactions. The undesirable consequence is that all resources, including those with relatively relaxed coherence requirements, must pay the same high price in terms of delay and protocol overhead. It can be argued that a uniform approach, such as distributed shared memory, is suitable for developers, but we believe that developers are capable of and willing to select from a range of coherence models in order to best meet the requirements of their applications. This means that the required response time can be traded off against the speed of convergence. The TAGS replicated resource architecture is more fully described in [START_REF] Allison | Replicating the R in URL[END_REF].

CONCLUSION

TAGS has evolved in line with the pedagogical needs of its users. The group ethos in TAGS is reflected from the application level all the way through the system design. The group mechanism provided by TAGS is part of a small and simple but powerful set of abstractions, which can be used to create a wide variety of collaborative learning environments.

Figure 1 :

 1 Figure 1: The TAGS Framework

Figure 2 :

 2 Figure 2: Basic Relations

Figure 3 :

 3 Figure 3: TAGS authentication and authorisation

1st LEGE-WG international workshop on e-Learning and GRID Technologies:Educational models for GRID based services.

ACKNOWLEDGMENTS

TAGS was funded under the SHEFC Use-of-the-MANS II and ScotCIT programmes (1997)(1998)(1999)(2000)(2001).


Zhengyuan Zhou
email: zyzhou@stanford.edu

Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr

Susan Athey
email: athey@stanford.edu

Nicholas Bambos
email: bambos@stanford.edu

Peter Glynn
email: glynn@stanford.edu

Yinyu Ye
email: yinyu-ye@stanford.edu

Learning in Games with Lossy Feedback

We consider a game-theoretical multi-agent learning problem where the feedback information can be lost during the learning process and rewards are given by a broad class of games known as variationally stable games. We propose a simple variant of the classical online gradient descent algorithm, called reweighted online gradient descent (ROGD) and show that in variationally stable games, if each agent adopts ROGD, then almost sure convergence to the set of Nash equilibria is guaranteed, even when the feedback loss is asynchronous and arbitrarily corrrelated among agents. We then extend the framework to deal with unknown feedback loss probabilities by using an estimator (constructed from past data) in its replacement. Finally, we further extend the framework to accomodate both asynchronous loss and stochastic rewards and establish that multi-agent ROGD learning still converges to the set of Nash equilibria in such settings. Together, these results contribute to the broad lanscape of multi-agent online learning by significantly relaxing the feedback information that is required to achieve desirable outcomes.

Introduction

In multi-agent online learning [START_REF] Busoniu | Multi-agent reinforcement learning: An overview[END_REF][START_REF] Lugosi | Prediction, learning, and games[END_REF][START_REF] Grover | Learning policy representations in multiagent systems[END_REF][START_REF] Shoham | Multiagent systems: Algorithmic, game-theoretic, and logical foundations[END_REF], a set of agents repeatedly interact with the environment and each other while accumulating rewards in an online manner. The key feature in this problem is that to each agent, the environment consists of all other agents who are simultaneously making such sequential decisions, and hence, each agent's reward depends not only on their own action, but also on the joint action of all other agents. A common way to model reward structures in this multi-agent online learning setting is through a repeated but otherwise unknown stage game: the reward of the i-th agent at iteration n is r i (a n i , a n -i ), where a n i is agent i's action at n and a n -i is the vector of all other agents's actions at stage n.

Even though the underlying stage game is fixed (i.e. each r i (•) is fixed), from each agent's own perspective, its reward is nevertheless a time-varying function when viewed solely as a function of its own action, i.e., r n i (•) = r i (•, a n -i ), and it needs to select an action a n i before receiving the reward r n i (a n i ). As such, each agent is exactly engaged in a classical online learning process [START_REF] Blum | On-line algorithms in machine learning[END_REF][START_REF] Hazan | Introduction to Online Convex Optimization[END_REF][START_REF] Shalev-Shwartz | Online learning: Theory, algorithms, and applications[END_REF][START_REF] Al | Online learning and online convex optimization[END_REF]. In this context, there is a fruitful line of existing literature providing a rich source of online learning algorithms to minimize the standard performance metric known as regret [START_REF] Blum | From external to internal regret[END_REF], defined as Reg Alg T = max ai∈A T t=1 {r t i (a i ) -r t i (a t i )} with the sequence of actions a t i generated by some online learning algorithm Alg. These algorithms, already classical, include "follow-theregularized-leader" [START_REF] Kalai | Efficient algorithms for online decision problems[END_REF], online gradient descent [START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF], multiplicative/exponential weights [START_REF] Arora | The multiplicative weights update method: a meta-algorithm and applications[END_REF], online mirror descent [START_REF] Shalev-Shwartz And | Convex repeated games and Fenchel duality[END_REF], and many others. Perhaps the simplest algorithm in the above list is Zinkevich's online gradient descent (OGD) method, where the agent simply takes a gradient step (using their current reward function) to form the action for the next stage, performing a projection if the iterate steps out of the feasible action set. This algorithm, straightforward as it is, provides (asymptotically) optimal regret guarantees (see Section B in the appendix for a brief review) and is arguably one of the most well-studied and widely-used algorithms in online learning theory and applications [START_REF] Hazan | Logarithmic regret algorithms for online convex optimization[END_REF][START_REF] Quanrud | Online learning with adversarial delays[END_REF][START_REF] Zinkevich | Online convex programming and generalized infinitesimal gradient ascent[END_REF].

Consequently, several natural questions arise in multi-agent online learning : if each agent adopts OGD to minimize regret, what is the resulting evolution of the joint action? Specifically, under what games/assumptions would it lead to a Nash equilibrium (the leading solution concept in multi-agent games)? These questions fall in the broader inquiry of understanding the joint convergence of no-regret online learning algorithms, an inquiry that lies at the heart of game-theoretical learning for well-grounded reasons: Specifically, studying whether the process converges at all provides an answer as to the stability of the joint learning dynamics, while studying whether it converges to a Nash equilibrium provides an answer as to whether the joint learning dynamics lead to the emergence of rationality. Specifically, for the latter point, if, when agents adopt an online learning algorithm the joint action converges to a point that is not a Nash equilibrium, each agent would be able to do better by unilaterally deviating from that algorithm. Hence, convergence to a non-Nash point would inherently produce "regret" in equilibrium.

Related Work

Despite the fact that game-theoretic learning has received significant scrutiny in the literature, the questions raised above are still open for several reasons.

First, in general, joint convergence of no-regret learning does not hold. In fact, even in simple finite games (where each agent has a finite number of actions), no-regret learning may fail to converge [START_REF] Mertikopoulos | Cycles in adversarial regularized learning[END_REF]. Even if it does converge, in mixed extensions of finite games (where each agent's action set is a probability simplex over a finite number of actions), the limit can assign positive weight only to strictly dominated actions. Consequently, establishing joint convergence to Nash equilibria under no-regret learning algorithms (OGD included) for a broad and meaningful subclass of games has been a challenging ongoing effort.

Second, the extensive existing literature in the field has mainly focused on studying convergence in (mixed extensions of) finite games [START_REF] Bloembergen | Evolutionary dynamics of multi-agent learning: a survey[END_REF][START_REF] Monnot | Limits and limitations of no-regret learning in games[END_REF][START_REF] Shoham | Multiagent systems: Algorithmic, game-theoretic, and logical foundations[END_REF][START_REF] Viossat | No-regret dynamics and fictitious play[END_REF]. Earlier work of game-theoretic learning (see [START_REF] Levine | The Theory of Learning in Games, vol. 2 of Economic learning and social evolution[END_REF] for a comprehensive review) has mainly focused on learning in finite games with dynamics that are not necessarily regret-less (e.g. best-response dynamics, fictitious play and the like). Subsequently, the seminal work [START_REF] Lugosi | Prediction, learning, and games[END_REF] (see also the many references therein) has provided a unified treatment of joint convergence of various no-regret learning algorithms in mixed extensions of finite games. The primary focus of [START_REF] Lugosi | Prediction, learning, and games[END_REF] is convergence to other, coarser equilibrium notions (e.g. correlated equilibria), where a fairly complete characterization is given. On the other hand, as pointed out in [START_REF] Lugosi | Prediction, learning, and games[END_REF], convergence to Nash is a much more difficult problem: recent results of [START_REF] Viossat | No-regret dynamics and fictitious play[END_REF] have clearly highlighted the gap between (coarse) correlated equilibria obtained by no-regret learning processes and Nash equilibria. More positive results can be obtained in the class of potential games where, in a recent paper, the authors of [START_REF] Cohen | Learning with bandit feedback in potential games[END_REF] established the convergence of multiplicative weights and other regularized strategies in potential games with only payoff-based, bandit feedback. However, moving beyond mixed extensions of finite games, much less is known, and only a moderate amount of literature exists. In the context of mixing in games with continuous action spaces, the authors of [START_REF] Perkins | Mixed-strategy learning with continuous action sets[END_REF] provide a convergence analysis for a perturbed version of the multiplicative weights algorithm in potential games. In a pure-strategy setting, the network games considered in [START_REF] Menache | Network games: Theory, models, and dynamics[END_REF] belong to the much broader class of games known as concave games: each agent's reward function is individually concave. 1 Therein, the dynamics investigated may lead to positive regret in the limit. The recent paper [START_REF] Balandat | Minimizing regret on reflexive banach spaces and learning nash equilibria in continuous zero-sum games[END_REF] studied a two-player continuous zero-sum game, and showed that if both players adopt a no-regret learning algorithm, then the empirical time-average of the joint action converges to Nash equilibria. However, barring a few recent exceptions, the territory of no-regret learning on concave games is not well understood (let alone in general games with continuous action sets). An exception to this are the recent papers [START_REF] Mertikopoulos | Distributed stochastic optimization via matrix exponential learning[END_REF][START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF] where the authors establish the convergence of mirror descent in monotone games -a result later extended to learning with bandit, zeroth-order feedback in [START_REF] Bervoets | Learning with minimal information in continuous games[END_REF][START_REF] Bravo | Bandit learning in concave N -person games[END_REF].

Third, the convergence mode that is commonly adopted in the existing literature is ergodic convergence (i.e. convergence of 1 n t t=n a t ), rather than the convergence of the actual sequence of play (i.e. a n ). The former is convergence of the empirical frequency of play, while the latter is convergence of actual play: note that the latter implies the former, but not the other way round. It is important to point out, however, that convergence of the actual sequence of play is more desirable2 not only because it is theoretically more appealing, but also because it characterizes the joint evolution of the system in no-regret learning (since a n , rather than 1 n t t=n a t , is the actual action taken). This issue was highlighted in [START_REF] Mertikopoulos | Cycles in adversarial regularized learning[END_REF], where it is shown that even though continuous-time followthe-regularized-leader (another no-regret learning algorithm) converges to Nash equilibrium in linear zero-sum games in the sense of time-averages, actual play orbits Nash equilibria in perpetuity. However, most of the existing work focus on establishing ergodic convergence (which granted is some form of stability), where the tools developed are far from sufficient to ensure convergence of actual play. Some recent exceptions in specific games do exist: [START_REF] Krichene | Convergence of heterogeneous distributed learning in stochastic routing games[END_REF][START_REF] Lam | On learning how players learn: estimation of learning dynamics in the routing game[END_REF] studied nonatomic routing games (a special class of concave games) and established that both online mirror descent and multiplicative weights (yet another two no-regret algorithms) converge to Nash equilibria; while [START_REF] Palaiopanos | Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos[END_REF] established multiplicative weights converge to Nash equilibria under certain conditions in atomic routing games (a subclass of finite games). Theoretically, the main difficulty in establishing convergence of the sequence of play lies in cleverly designing (as done in [START_REF] Krichene | Convergence of heterogeneous distributed learning in stochastic routing games[END_REF][START_REF] Lam | On learning how players learn: estimation of learning dynamics in the routing game[END_REF][START_REF] Palaiopanos | Multiplicative weights update with constant step-size in congestion games: Convergence, limit cycles and chaos[END_REF][START_REF] Zhou | Countering feedback delays in multi-agent learning[END_REF]) specific and much sharper Lyapunov functions for the specific learning algorithms at hand. This difficulty is partially overcome in [START_REF] Bravo | Bandit learning in concave N -person games[END_REF] for strongly monotone games where, assuming perfect gradient observations, an O(1/n) convergence rate is established.

Our Contributions

In this paper, we study the convergence of OGD to Nash equilibrium in general continuous games. To the best of our knowledge, the existing state-of-the-art convergence guarantee is that multi-agent OGD converges to Nash equilibria in monotone games in the sense of ergodic averages, a result due to [START_REF] Nesterov | Primal-dual subgradient methods for convex problems[END_REF]. Monotone games 3 are an important and well-known subclass of concave games (in particular, it includes convex potential games as a special case). On a related note, a very recent paper [START_REF] Salehisadaghiani | Distributed nash equilibrium seeking via the alternating direction method of multipliers[END_REF] considered pseudo-monotone games (which strictly contain monotone games but also belong to concave games) and devised two distributed algorithms for computing Nash equilibria. However, it is far from clear that the algorithms devised are no-regret when used in an online fashion.

In this paper, we work with a broad class of general continuous games (not necessarily concave even), known as variationally stable games [START_REF] Zhou | Countering feedback delays in multi-agent learning[END_REF][START_REF] Zhou | Mirror descent learning in continuous games[END_REF], that strictly include pseudo-monotone games (and hence, in a chain of inclusion, monotone games and convex potential games), and also nonatomic routing games, linear Cournot games, resource allocation auctions, etc. More importantly, we go a step further and consider an even more general multi-agent online learning problem, where we allow agents to have asynchronous gradient feedback losses (note that so far the game-theoretical learning discussion is under perfect feedback, where the resulting landscape is already challenging). More specifically, instead of assuming that every agent receives information at every stage, we allow for cases where a (random) subset of agents remains informed (specifically, each agent i has a probability p i of receving the feedback and probability 1 -p i of losing it).

Two important features of this model are: 1) the feedback loss can be asynchronous; 2) the feedback loss can be arbitrarily correlated among agents (whether some agent loses its feedback on the current iteration may affect whether others lose theirs). In this asynchronous context, we design a simple variant of OGD, called reweighted online gradient descent (ROGD), where each agent corrects its own marginal bias via dividing the received gradient (if any) by p i . This is inspired by the classical EXP3 algorithm [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF][START_REF] Bubeck | Regret analysis of stochastic and nonstochastic multi-armed bandit problems[END_REF]) in the multi-armed literature, where it has a similar feature of weighting the observed bandit feedback by the probability of selecting the corresponding arm. We then establish in Theorem 4.3 that, in this asynchronous feedback loss setting, the sequence of play induced by joint ROGD converges almost surely to Nash equilibria in variationally stable games. We achieve this strong theoretical guarantee by designing an energy function that sharply tracks the progress made in the joint evolution of the ROGD update of all agents under feedback loss. We mention that a very recent work that also studies multi-agent online learning under imperfect information at the generality of variationally stable games is [START_REF] Zhou | Countering feedback delays in multi-agent learning[END_REF]. In particular, it is shown there that online mirror descent (also no-regret) converges to Nash even in the presence of super-linear but sub-quradtic growing delays in gradients. However, in that context, in addition to studying a different algorithm, [START_REF] Zhou | Countering feedback delays in multi-agent learning[END_REF] focuses on delays and in particular requires all gradients to be received (i.e. no gradient loss is allowed). Consequently, the results in [START_REF] Zhou | Countering feedback delays in multi-agent learning[END_REF] are strictly complementary to ours here: in particular, it is unclear whether online mirror descent would converge to Nash under feedback loss.

Finally, we make two practically useful and theoretically meaningful extensions. First, we extend to the case where the loss probabilites (which are assumed to be known so far) are not known. In this case, we can replace the actual probabilities p i by an estimate. Our main message (Theorem 5.1) is that provided the estimator is √ n-consistent, then convergence to Nash in last iterate under ROGD is still guaranteed. Note that a simple estimator that satisfies this guarantee is the sample mean estimator (with Laplace smoothing). Second, we extend the multi-agent online learning setup to also accomodate for stochastic reward functions, where in each iteration only a random reward function is realized. In such cases, we first note an important equivalence result, both from a modeling standpoint and from a proof standpoint: the setup where agents' reward functions are iid can be identified with the setup where agents' reward functions are fixed and deterministic but the received feedback gradients are noisy (but unbiased). We then establish that (in either setup) multi-agent ROGD learning still converges almost surely to the set of Nash equilibria when noise has bounded support (Theorem E.4 in the appendix); and converges in probability to the set of Nash equilibria if noise has unbounded support but has finite second moment (Theorem E.6 in the appendix): both are in last iterate. Due to space limitation, this part is placed in the appendix. Together, these results not only make meaningful progress towards the challenging open problem of convergence of no-regret algorithms to Nash in general continuous games under perfect information, but also, more importantly, contribute to the broad lanscape of multi-agent online learning under imperfect information.

Problem setup 2.1 Rewards for Multi-Agent Online Learning

We consider a general continuous game model for the rewards in multi-agent online learning:

Definition 2.1. A continuous game G is a tuple G = (N , A = N i=1 A i , {r i } N i=1
), where N is the set of N agents, X i is a convex and compact subset of R di representing the action space of agent i, and r i :

A → R is agent i's reward function, such that r i (a) = r i (a 1 , a 2 , . . . , a N ) is continuous in a and continuously differentiable in a i for each i ∈ N and ∇ ai r i (a) is Lipschitz continuous in a. Definition 2.2. Given a continuous game G, a * ∈ X is called a Nash equilibrium if for each i ∈ N , r i (a * i , a * -i ) ≥ r i (a i , a * -i ), ∀a i ∈ X i .
For the rest of the paper, we set d = N i=1 d i , which denotes the dimension of the joint action space: A ⊂ R d . Variables associated with agent i are denoted by subscripts. If there is no subscript, then it is understood that it is a joint variable of all agents. When each agent is applying 4 OGD independently, we obtain multi-agent OGD in Algorithm 1 (we assume

∞ n=1 γ n+1 = ∞, ∞ n=1 γ 2 n+1 < ∞):
Algorithm 1: Multi-Agent OGD Learning

Require: Each agent i picks an arbitrary a 0

i ∈ R di 1: n ← 0, y 0 i ← a 0 i 2: repeat 3:
for each agent i do 4:

y n+1 i = y n i + γ n+1 ∇ ai r i (a n ) 5: a n+1 i = Proj Ai (y n+1 i ) 6:
end for 7:

n ← n + 1 8: until end

Asynchronous Feedback Loss

The setup described in Algorithm 1 is multi-agent learning under perfect feedback information. Here we extend the model to allow for asynchronous feedback loss, where at each time step, only a subset N n+1 ⊂ N of the agents receive their gradients from time5 n, while other agents' gradients are lost. We assume that this subset is drawn iid from a fixed distribution across time steps.

To faciliate the discussion, let the indicator variable I n+1 i be 1 if agent i's gradient from n is received (at the beginning of n + 1) and 0 otherwise. Mathematically:

I n+1 i = 1, if i ∈ N n+1 , 0, if i / ∈ N n+1 . (2.1)
Note that under this model, even though N n+1 is drawn iid across time steps, within the same time step, I n+1 i and I n+1 j can be arbitrarily correlated (whether agent i's feedback is lost can influence whether agent j's feedback is lost). We assume each agent i only knows its own marginal loss probability 1 -p i , where

p i = E[I n+1 i ].
We refer to this setup as asynchronous feedback loss, because different agents can have different feedback loss pattern at any iteration. Applying multi-agent OGD in the feedback loss model yields:

Algorithm 2: Multi-Agent OGD Learning under Asynchronous Feedback Loss Require: Each agent i picks an arbitrary

A 0 i ∈ R di 1: n ← 0, Y 0 i ← A 0 i 2: repeat 3:
for each agent i do 4:

Y n+1 i = Y n i + γ n+1 ∇ ai r i (A n ), if I n+1 i = 1 Y n i , if I n+1 i = 0 5: A n+1 i = Proj Ai (Y n+1 i ) 6:
end for 7:

n ← n + 1 8: until end Here we have capitalized the iterates Y n i , A n i because they are now random variables (due to random feedback loss). Specifically, denoting by I the vector of indicator variables for all the agents, we have that both Y n i and A n i are adapted to A 0 , I 1 , I 2 , . . . , I n . Note the important but subtle point here: Y n i and A n i are not adapted to A 0 i , I 1 i , I 2 i , . . . , I n i , because each individual's gradient update is coupled with all the other agents' actions, which is a fundamental phenomenon in multi-agent learning.

Variationally Stable Games

Consequently, special structures must be imposed on the games/reward functions. Here we consider a broad meta class of games, called variationally stable games [START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF][START_REF] Zhou | Mirror descent learning in continuous games[END_REF], that contain many existing well-known classes of games, such as convex potential games, monotone games, pseudo-monotone games [START_REF] Zhu | Distributed robust adaptive equilibrium computation for generalized convex games[END_REF], coercive games [START_REF] Salehisadaghiani | Distributed nash equilibrium seeking via the alternating direction method of multipliers[END_REF], influence network games [START_REF] Zhou | Dynamics on linear influence network games under stochastic environments[END_REF][START_REF] Zhou | A game-theoretical formulation of influence networks[END_REF], non-atomic routing games [START_REF] Roughgarden | Selfish routing and the price of anarchy[END_REF]. See [START_REF] Zhou | Countering feedback delays in multi-agent learning[END_REF] for more details. Definition 2.3. G is a variationally stable game if its set of Nash equilibria A * is non-empty and satisfies: ∇ a r(a), a -a * N i=1 ∇ ai r i (a), a i -a * i ≤ 0, ∀a ∈ A, ∀a * ∈ A * , with equality if and only if a ∈ A * . Remark 1. Monotone games require ∇ a r(a) -∇ a r(a ), a -a ≤ 0, ∀a, a ∈ A. Pseudo-monotone games require: if ∇ a r(a ), a -a ≤ 0, then ∇ a r(a), a -a ≤ 0, ∀a, a ∈ A. That monotone is a special case of pseudo-monotone is obvious. That pseduo-monotone is a special case of variational stability follows by recalling the standard characterization of a Nash equilibrium: a * satisfies ∇ a r(a * ), a -a * ≤ 0, ∀a ∈ A.

In the presence of feedback loss, the convergence of multi-agent OGD given in Algorithm 2 to Nash equilibria cannot be guaranteed in variationally stable games (and there exist cases where it doesn't, in fact, convergence of OGD is not guaranteed even in convex potential games). In the next section, we present a simple modification of the vanilla multi-agent OGD that will later be shown to converge to Nash equilibria, even in the presence of asynchronous delays. We shall then see that as a corollary (see Corollay 4.4), multi-agent OGD will converge to the set of Nash equilibria (almost surely) if the feedback loss are synchronous (and as a further special case, if there is no feedback loss).

Algorithm and energy function

In this section, to deal with asynchronous feedback loss, we give a new algorithm called Reweighted Online Gradient Descent (ROGD) for the multi-agent learning problem.

Reweighted Online Gradient Descent

The main idea in the modification of OGD lies in each agent individually correcting its marginal bias (which comes from the loss of the gradient feedback) by dividing the probability. More specifically, when a gradient is lost on the current time step, the agent uses the previous action as in OGD. Otherwise, when a gradient is indeed available, the gradient will be weighted by p i first before getting updated. This results in reweighted online gradient descent: Algorithm 3: Multi-Agent ROGD Learning under Asynchronous Feedback Loss Require: Each agent i picks an arbitrary

A 0 i ∈ R di 1: n ← 0, Y 0 i ← A 0 i 2: repeat 3:
for each agent i do 4:

Y n+1 i = Y n i + γ n+1 ∇a i ri(A n ) pi , if I n+1 i = 1 Y n i , if I n+1 i = 0 5: A n+1 i = Proj Ai (Y n+1 i ) 6:
end for 7:

n ← n + 1 8: until end We emphasize once again that the gradient loss among agents can be correlated. However, in ROGD, each agent only corrects its own marginal bias and does not concern itself with other agents' feedback loss. To analyze the ROGD algorithm, we next introduce an important theoretical tool.

Energy Function

We start by defining the energy function, an important tool we use to establish convergence later. a * is always any fixed Nash equilibrium. Definition 3.1. Define the energy function L : R d → R as follows:

L(y) = a * 2 2 -Proj A (y) 2 2 + 2 y, Proj A (y) -a * . (3.1) Lemma 3.2. Let y n be a sequence in R d 1. L(y n ) → 0 implies Proj A (y n ) → a * . 2. Proj A (y) -ŷ 2 2 -Proj A (ŷ) -ŷ 2 2 ≤ y -ŷ 2 2
, for any y, ŷ ∈ R d 3. L(y + ∆y) -L(y) ≤ 2 ∆y, Proj A (y) -a * + ∆y 2 2 , for any y, ∆y ∈ R d . Remark 2. The second statement of the lemma serves as an important intermediate step in proving the third statement, and is established by leveraging the envelop theorem and several important properties of Euclidean projection. To see that this is not trivial, consider the quantity Proj A (y) -ŷ 2 -Proj A (ŷ) -ŷ 2 , which we know by triangle's inequality satisfies:

Proj A (y) -ŷ 2 -Proj A (ŷ) -ŷ 2 ≤ Proj A (y) -Proj A (ŷ) 2 ≤ y -ŷ 2 , (3.2)
where the last inequality follows from the fact that projection is an non-expansive map. However, this inequality is not sufficient for our purposes because in quantifying the perturbation L(y +∆y)-L(y), we also need the squared term ∆y 2 2 , which is not easily obtainable from Equation (3.2). In fact, a finer-grained analysis is needed to establish that y -ŷ 2 2 is an upper bound on

Proj A (y) -ŷ 2 2 - Proj A (ŷ) -ŷ 2 2 .
4 Almost sure convergence to Nash equilibria

In this section, we establish that when agents' rewards come from a variationally stable game, multiagent ROGD converges to the set of Nash equilibria almost surely under asynchronous feedback loss.

For ease of exposition, we break the framework into three steps, each of which centers on one idea and is described in detail in a subsection. All the proof details are given in the appendix. For the first two subsections, let a * be an arbitrary Nash equilibrium.

Controlling the Tail Behavior of Expectation

Our first step lies in controlling the tail behavior of the expected value of the sequence { ∇ a r(A n ), a * -A n } ∞ n=0 . Note that by variational stability, we have: ∀n, ∇ a r(A n ), a * -A n ≥ 0, a.s. Consequently, E[ ∇ a r(A n ), a * -A n ] ≥ 0, ∀n. By leveraging the energy function, its telescoping sum and an appropritate conditioning, we show that (next lemma) this sequece of expectations should be rather small in the limit and its tail should "mostly" go to 0. Lemma 4.1.

∞ t=0 γ n+1 E[ ∇ a r(A t ), a * -A t ] < ∞. (4.1) Remark 3. Since ∞ t=0 γ n+1 = ∞, Lemma 4.1 that lim inf n→∞ E[ ∇ a r(A t ), a * -A t ] = 0. Note that the converse is not true: when a subsequence of {E[ ∇ a r(A n ), a * -A n ]} ∞
n=0 converges to 0, the sum need not be finite. As a simple example, consider γ n+1 = 1 n , and

E[ ∇ a r(A n ), a * -A n ] = 1 n , if t = 2 k 1, otherwise. (4.2)
Then the subsequence on indicies 2 k converges to 0, but the sum still diverges. This means that Equation (4.1) is stronger than subsequence convergence.

Bounding the Successive Differences

However, Equation (4.1) is still not strong enough to guarantee that lim n→∞ E[ ∇ a r(A t ), a * -A t ] = 0, let alone lim n→∞ ∇ a r(A t ), a * -A t = 0, a.s.. This is because the convergent sum given in Equation (4.1) only limits the tail growth somewhat, but not completely. As an example to demonstrate this point, let C t be the following boolean variable6 :

C t = 1, if t contains the digit 9 in its decimal expansion 0, otherwise. (

Now define γ n+1 = 1 n , and

E[ ∇ a r(A n ), a * -A n ] = 1 n , if C t = 1 1, if C t = 0.
Then it follows from a straightforward calculation that [START_REF] Souza | Berkeley Problems in Mathematics, Problem Books in Mathematics[END_REF]). However, the limit E[ ∇ a r(A t ), a * -A t ] does not exist. This indicates that to obtain almost sure convergence of ∇ a r(A n ), a * -A n to 0, we need to impose more stringent conditions to ensure its sufficient tail decay. One way is to bound the difference between every two successive terms in terms of a decreasing sequence. This ensures that ∇ a r(A t ), a * -A t cannot change two much from iteration to iteration. Further, the change between two successive terms will become smaller and smaller. This result is formalized in the following lemma (the proof is given in the appendix): Lemma 4.2. There exists a constant C > 0 such that for every n,

∞ t=0 γ n+1 E[ ∇ a r(A t ), a * -A t ] < ∞ (see Problem 1.3.24 in
∇ a r(A n+1 ), a * -A n+1 -∇ a r(A n ), a * -A n ≤ Cα n+1 , a.s.
(4.4)

Main Convergence Result

We are now finally ready to put all the pieces together and state the main convergence result.

Theorem 4.3. Let the reward functions be given from a variationally stable game. Define the point-to-set distance in the standard way: dist(a, A * ) = inf a * ∈A * a -a * 2 . Then for any strictly positive probabilities {p i } N i=1 , ROGD converges almost surely to the set of Nash equilibria: lim n→∞ dist(A n , A * ) = 0 a.s., as n → ∞, where A n is a sequence generated from Algorithm 3. Remark 4. As a quick outline here (the details are in appendix), pick an arbitrary Nash equilibrium a * ∈ A * . Lemma 4.1 and Lemma 4.2 will together ensure that lim n→∞ ∇ a r(A t ), a * -A t = 0, a.s. Since ∇ a r(a), a * -a > 0 if and only if a / ∈ A * and ∇ a r(a), a * -a = 0 if and only if a ∈ A * , it then follows by continuity of ∇ a r(•) that lim n→∞ ∇ a r(A t ), a * -A t = 0, a.s. implies lim n→∞ dist(A n , A * ) = 0 a.s..

Although not mentioned in this theorem, another useful and interesting structural insight to point out here is that as ∇ a r(A t ), a * -A t converges to 0, if it ever becomes 0 at n, then A t ∈ A * , and furthermore, the joint action will stay exactly at that Nash equilibrium forever. Why? There are two cases to consider.

1. First, this Nash equilibrium a * is an interior point in A. In this case, ∇ a r(a * ) = 0 and hence ∇ a r(A n ) = 0. Consequently, per the ROGD update rule, whether any agent updates or not does not matter: either the gradient is not received, in which case no gradient update happens; or a gradient is received, but at this Nash equilibrium, it is 0 and therefore nobody will want to make any update.

2. Second, this Nash equilibrium a * is a boundary point in A. In this case, ∇ a r(a * ) may not be 0, but it always points outside the feasible action set A. Consequently, even if an agent receives a gradient and hence makes a gradient update, its action will immediately get projected back to the same point. As a result, the joint action A n will stay exactly at A (even though the Y n variables will still change). This can be easily seen that by noting that the probability can be absorbed into the step-size.

Corollary 4.5. Under the same setup as in Theorem 4.3, if there is no feedback loss (p i = 1, ∀i), multi-agent OGD in Algorithm 2 converges to A * in last iterate.

Remark 5. Note that as stated, our above results require a joint learning step-size policy, even if there is no missing gradient feedback -otherwise, the players' individual gradients weighted by individual step-sizes might not be "stable" and can cause divergence (and, of course, the situation only becomes worse in the "lossy" regime). That said, our analysis still holds if each player i ∈ N uses an individual step-size policy γ i n such that lim sup n→∞ γ i n /γ j n < ∞ for all pairs i, j ∈ N , i.e., if the players' updates do not follow different "time-scales" (so to speak). In that case however, the proofs (and the overall write-up) would become much more cumbersome, so we avoided this extra degree of generality in this paper.

Extension: Unknown Loss Probabilities

So far we have assumed p i 's are known. We close the paper with a brief comment on how to remove this assumption. When each agent i does not know the underlying loss probability p i , ROGD is no longer feasible. To overcome this, we use an estimator pi (obtainable from the past history) in replacement of the true probability p i . Since the only information an agent has is the past history of received gradients, we require the estimator pi to be adapted to the sequence of the indicator functions I t i 's: pn i = pt i (I 1 i , . . . , I n i ). The resulting algorithm will be called EROGD. An estimator pn is called

√ n-consistent if E[(p n -p) 2 ] = O( 1 n )
, where p is the true parameter (note that it is called √ n-consistent because root-mean-squared error is typically used to define the rate of consistency.). We have the following result (proof omitted due to space limitation): Theorem 5.1. Under the same setup as in Theorem 4.3, if pn i is √ n-consistent for every i ∈ N , and if

∞ n=1 γ n 1 √
n < ∞, then the last iterate of EROGD converges to A * in probability. Remark 6. One simple estimator that is √ n-consistent is sample mean with smoothing (where the smoothing is used to prevent the estimator from ever reaching 0):

p n+1 i = n s=1 I s i +1 n+1
. Further, many step-size sequences satisfy the requirement: examples include γ n = 1 n α where 0.5 < γ < 1.

Concluding remarks

In this paper, we have provided an algorithmic framework to deal with multi-agent online learning under feedback loss and obtained broad convergence-to-Nash results under fairly general settings. We also believe more exciting work remains. For instance, our formulation is game-theoretical where participating agents are self-interested. A parallel facet to multi-agent online learning is coordination [START_REF] Anand | Asap-uct: Abstraction of state-action pairs in uct[END_REF][START_REF]A novel abstraction framework for online planning[END_REF][START_REF] Dimakopoulou | Coordinated exploration in concurrent reinforcement learning[END_REF][START_REF] Grover | Evaluating generalization in multiagent systems using agent-interaction graphs[END_REF], where participating agents coordinate to achieve a common goal. Understanding how to effectively cooperate under imperfect information will be an interesting future direction. Another direction is to incorporate state into the reward and allow actions to also depend on the underlying state that may transition. Such settings belong broadly to multi-agent online policy learning, where the imperfect information regime is under-explored. Empirically, we believe the recent advances in deep learning and representation learning could possibly [START_REF] Goodfellow | Deep Learning, Adaptive computation and machine learning[END_REF][START_REF] Mnih | Playing atari with deep reinforcement learning[END_REF][START_REF] Yin | Deepprobe: Information directed sequence understanding and chatbot design via recurrent neural networks[END_REF][START_REF] Yin | The global anchor method for quantifying linguistic shifts and domain adaptation[END_REF][START_REF] Yin | On the dimensionality of word embedding[END_REF] provide a flexible architecture for learning good policies in the imperfect information regime, although characterizations of theoretical guarantees may require novel machinery. Finally, it would also be interesting to further extend the results into partial feedback settings. In the presence of a single agent, such problems have been studied in the context of offline policy learning [START_REF] Kallus | From predictive to prescriptive analytics[END_REF][START_REF] Zhou | Offline multi-action policy learning: Generalization and optimization[END_REF] and online bandits (with imperfect information) [START_REF] Grover | Best arm identification in multi-armed bandits with delayed feedback[END_REF][START_REF] Joulani | Online learning under delayed feedback[END_REF][START_REF] Pike-Burke | Bandits with delayed, aggregated anonymous feedback[END_REF]. However, the multi-agent learning setting is again under-explored; we leave that for future work.

Corollary 4 . 4 .

 44 Under the same setup as in Theorem 4.3, if feedback loss is synchronous on average (p i = p j , ∀i, j), then multi-agent OGD in Algorithm 2 converges almost surely to A * in last iterate.

In this vein, mixed extensions of finite games can be called linear games, because each agent's reward is individually linear in its own action. Note also that convex potential games is a subclass of concave games. The following gives the set membership: finite games ⊂ mixed extension of finite games ⊂ concave games ⊂ general continuous games.

Of course, convergence in ergodic average is still valuable in many contexts, particularly when convergence of actual play fails to hold.

In short, it means (∇a 1 r1(•), ∇a 2 r2(•), . . . , ∇a n rn(•)) is a monotone operator on the joint action space. Note that if there is only 1 player, this means the underlying problem is a convex optimization problem since the gradient of a convex function is monotone. In this case, a Nash equilibrium is a globally optimal solution.

Note that in particular, the gradient here is a partial gradient with respect to one's own action, and its dimension is equal to di, the dimension of its own action space.

Here the superscript n + 1 means that set N n+1 is revealed at the beginning of time n + 1

By it definition, c9 = 1, c11 = 0.


Cord Hockemeyer

Dietrich Albert

Adaptive e-Learning and the Learning Grid

Keywords: adaptive eLearning, Learning Grid, knowledge structures, competencies

One important aim of LeGE-WG is the integration of new eLearning methodologies into Learning Grid technology. A central issue in these new eLearning methodologies is the concept of individualised and personalised learning to be realised by adaptive tutoring systems. The adaptivity of such systems goes far beyond adapting to the users' preferences with respect to the user interface; in cooperation between computer science, psychology, and pedagogy, systems adapting, e.g., to the individual learners' current knowledge, cultural background, learning style, or special needs are developed. Adaptive tutoring systems can be integrated into a Learning Grid at different levels of ambitiousness. We will discuss these different levels of integration based on our prior experiences with respect to reusability of adaptive learning resources.

INTRODUCTION

Adaptive and personalised hypermedia systems have been of increasing interest in recent research and development in eLearning [START_REF] De Bra | Eds Adaptive Hypermedia and Adaptive Web-Based Systems[END_REF][START_REF]ED-MEDIA--World Conference on Educational Multimedia, Hypermedia & Telecommunications Proceedings CD-ROM[END_REF]. Integrating adaptive techniques enriches eLearning systems by adding psychological and pedagogical findings about knowledge and learning to technical systems.

Connecting adaptive techniques -and the underlying models of learning and knowledge -with Grid technology brings up new challenges, e.g. in the area of interoperability, but also new options.

In the following, we will first discuss adaptivity within eLearning in general as well as the knowledge space based approach pursued in our research group. Subsequently, we will discuss the issue of interoperability of adaptive eLearning systems based on our previous experiences. Finally, we look at different levels of integrating adaptive eLearning into a Learning Grid.

ADAPTIVE AND PERSONALISED ELEARNING

Using the computer for education allows -comparable to private teachers in former times -a personalised, adaptive learning, i.e. the teaching system adapts the selection and the presentation of contents to the individual learner and their learning status, their needs and preferences (see, e.g., [START_REF] Albert | Contributions of cognitive psychology to the future of e-learning[END_REF]).

Within the EASEL project, many different types of adaptivity have been identified focusing on objects and objectives of adaptivity [START_REF]EASEL Requirement specification[END_REF]. Objects of adaptivity can be, e.g., the selection of learning objects, their presentation, or the choice of input methods and devices. Objectives of adaptivity can be, e.g., the learners' pre-knowledge, their curriculum and aimed knowledge state, special needs, learning styles, or cognitive styles.

Our research group focuses on adaptivity to learners' current knowledge based on the theory of knowledge spaces [START_REF] Doignon | Spaces for the assessment of knowledge[END_REF][START_REF] Doignon | Knowledge Spaces[END_REF]. Knowledge space theory is a psychological model for structuring domains of knowledge based on prerequisite relationships between content objects. From these structures, learning paths are derived.

The relational formalisation of this model allows an easy transfer to computer systems, especially to relational databases. Thus, it can easily be applied to adaptive eLearning [START_REF] Hockemeyer | Adaptive and dynamic hypertext tutoring systems based on knowledge space theory[END_REF].

Currently, there are two adaptive eLearning systems on the Web which are based on this theory, RATH [START_REF] Hockemeyer | RATH ---a relational adaptive tutoring hypertext WWW--environment based on knowledge space theory[END_REF] and ALEKS (see [START_REF] Doignon | Knowledge Spaces[END_REF]).

More recent extensions of knowledge space theory distinguish between concrete learning objects or observable performances on the one side and underlying skills or competencies on the other side (see, e.g., [START_REF] Lukas | Knowledge Spaces: Theories, Empirical Research, Applications[END_REF][START_REF] Düntsch | Skills and knowledge structures[END_REF][START_REF] Korossy | Extending the theory of knowledge spaces: A competence-performance approach[END_REF]). These extensions also use mathematical formalisations, thus they can be applied for adaptive eLearning easily [START_REF] Hockemeyer | Extending the Competence-Performance-Approach for Building Dynamic and Adaptive Tutoring Systems[END_REF]. Such an application is discussed in the context of interoperability in the next section.

INTEROPERABILITY AND ADAPTIVE ELEARNING

Reusability and interoperability of computer based learning resources have received an increasing interest in recent years. This can, for instance, be seen in the development of standards and standardisation organisations in this area (see, e.g., [START_REF]IEEE Learning Technology Standards Committee (LTSC[END_REF]14]). However, all these specifications are oriented towards static material. One aim of the EASEL project in the FP5 IST programme was to extend existing interoperability standards to cover also adaptive features of learning resources [START_REF] Easel | Educator Access to Services in the Electronic Landscape)[END_REF].

In a first step, an extension to learning object metadata (LOM) standards was developed that allows a generic description of adaptive features of the material, i.e. this adaptivity element is not limited to specific types of adaptivity [START_REF] Conlan | Extending educational metadata schemas to describe adaptive learning resources[END_REF][START_REF] Albert | Reusing adaptive learning resources[END_REF]. These metadata specifications are primarily used for search and retrieval but they can also be used by the eLearning system for realising the adaptivity itself [START_REF] Conlan | Metadata driven approaches to facilitate adaptivity in personalized eLearning systems[END_REF].

The second step deals with interoperability between material and learning management system (LMS) directly. Adaptive material often needs to store and retrieve more information about the learner than static material. Based on AICC/SCORM [19,[START_REF]Sharable Content Object Reference Model[END_REF] standards on such information exchange, a set of information usually needed by adaptive resources has been defined that can be stored in and retrieved from the LMS through the SCORM API [START_REF] Conlan | An architecture for integrating adaptive hypermedia service with open learning environments[END_REF].

Based on these developments, the APeLS system was developed which is based on knowledge space theory extended by the competencies approach. This system is ready to be used from an LMS which then also does user identification and similar administrative tasks [START_REF] Conlan | Metadata driven approaches to facilitate adaptivity in personalized eLearning systems[END_REF].

ADAPTIVITY AND GRID TECHNOLOGY

The developments described in the previous sections provide already a large step for the integration of adaptive material and adaptive services into a Learning Grid. However, the integration can be performed at different levels.

At a minimal level, the Grid provides only user authentification while all other functionality is kept within an independent adaptive server. In a second step toward higher integration, also other information about the learner are stored within the Grid and are thus exchanged between different adaptive servers belonging to the same Grid.

While in the aforementioned levels adaptivity is basically still provided through a self-contained adaptive server, the third level of integration starts realising adaptivity in a distributed service through content repositories distributed over the Grid while the core adaptive system is still located at one server.

Finally, adaptivity itself could be realised in a distributed way through co-operation of different adaptive servers and services over the Grid. Methods for such distributed adaptive services have yet to be developed. However, integrating adaptivity into Learning Grid technology at such a high level promises to bring forward also a higher level of adaptivity than it could be realised on stand-alone services.

1st LEGE-WG international workshop on e-Learning and GRID Technologies:Educational models for GRID based services.