Daniel Della-Bosca
email: d.della-bosca@griffith.edu.au

Dale Patterson
email: d.patterson@griffith.edu.au

Sean Costain
email: s.costain@griffith.edu.au

Fractal Complexity in Built & Game Environments

Keywords: fractal, surface, complexity, built environment, computer game

Fractal patterns provide an automated mathematical method to create rich and engaging visuals. These methods have been applied in the design of physical and game spaces to only a limited extent. The current physical and virtual game worlds are dominated by rectangles, squares and linear concepts. This research studied the nature of fractal patterns and in particular the use of differing levels of fractal complexity to design physical and virtual environments. The findings from the randomized trial identified differing levels of fractal complexity and their aesthetic appeal to participants. These levels of fractal complexity were then applied to spatial environments in games to create spaces that were more or less appealing to the participant. The principle of using fractal complexity as a design tool to make an environment more or less comfortable provided game and architectural designers an additional mechanism to enhance spaces and levels of participant engagement.

Introduction

The world of computer games and their interactive environments is one filled with a mixture of differing spatial locations. Much like the real world, each virtual location features structural elements, both man made and natural. Every location and surface is created geometrically and carefully designed to provide players with a particular visual, ideally immersive, experience. The repetitive process, at heart of fractal mathematics, generates engaging, often uncannily natural patterns, images and objects [START_REF] Mandelbrot | The fractal geometry of nature[END_REF][START_REF] Mandelbrot | Fractals: form, change and dimension[END_REF][START_REF] Walsh | The use of an aesthetic measure for the evolution of fractal landscapes[END_REF]. The potential to use this fractal technique to enhance the surface textures and bump maps in game spaces was the key focus of this project.

In aesthetic terms, 'An object is said to be self-similar if it looks "roughly" the same at any scale' [START_REF] Mandelbrot | The fractal geometry of nature[END_REF][START_REF] Mandelbrot | Fractals: form, change and dimension[END_REF], an image is called fractal if it displays self-similarity, that is, it can be broken into parts, each of which is (approximately) a reduced size copy of the whole. The father of fractals, Benoit Mandelbrot, summarized his career as the 'ardent pursuit of the concept of roughness.' [START_REF] Mandelbrot | The fractal geometry of nature[END_REF]. It is this "roughness" that creates the link to natural surfaces, spaces and objects, where fractal patterns are comparatively common [START_REF] Mandelbrot | The fractal geometry of nature[END_REF], [START_REF] Walsh | The use of an aesthetic measure for the evolution of fractal landscapes[END_REF], [START_REF] Fan | Realistic Rendering of Three-Dimensional Ocean Waves Based on Fractal[END_REF], [START_REF] Pentland | Fractal-based description of natural scenes. Pattern Analysis and Machine Intelligence[END_REF]. Analysis of architectural design also identifies fractal "cascade of details" in many iconic structures such as the Sydney Opera House, Taj Mahal and others, all applying fractal systems to positive impact [START_REF] Bovill | Fractal Geometry in Architecture and Design[END_REF][START_REF] Salingaros | A scientific basis for creating architectural forms[END_REF][START_REF] Salingeros | Connecting the Fractal City. Keynote speech, 5th Biennial of towns and town planners in Europe[END_REF].

Games design procedural techniques, including fractal systems have been used for content generation to good effect [START_REF] Walsh | The use of an aesthetic measure for the evolution of fractal landscapes[END_REF], [START_REF] Fan | Realistic Rendering of Three-Dimensional Ocean Waves Based on Fractal[END_REF], [START_REF] Patterson | Using Interactive 3D Game Play to Make Complex Medical Knowledge More Accessible[END_REF]. Aesthetics are less clearly understood.

Fractal Dimension, Complexity & Design

The concept of a fractal pattern being self-similar does not inherently require it to be either complex or simple. There exists a range of possible levels of fractal complexity within this mathematical space. For example the 2D fractal dimension (D value) ranges anywhere between 1.0 and 2.0. A pattern that fills the plane in very simplistic terms (a low order of roughness/irregularity) has a D value close to 1, and a pattern that fills the plane with detailed and intricate structure will have a D value close to 2.

From a designers perspective this allows the ability to consider the fractal dimension as a changeable variable to alter the visual and aesthetic nature of the fractal content being created. For 3D objects the dimension ranges from 2.0-3.0. Several research studies have measured the aesthetic preferences of participants with regard to images with varying levels of fractal complexity, indicating an average aesthetic preference for a fractal complexity level in the range of 1.3 to 1.5 [START_REF] Spehar | Universal aesthetic of fractals[END_REF][START_REF] Aks | Quantifying aesthetic preference for chaotic patterns[END_REF].

Experimental Study of Fractal Complexity

Earlier studies of fractal dimension and complexity have dealt with mixed imagery from both nature and digital systems, including variations in shape, color and pattern. This research sought to reduce the amount of variables in the imagery studied and to more specifically explore the link between fractal dimension and its aesthetic appeal.

The study included twenty-five participants from a range of cultures ranging in age from 18 to 52 years. Each participant was presented with a range of surface options, these surfaces included a range of digitally created fractal surfaces and objects, each with differing levels of fractal dimension. Fractal patterns can of course be extremely complex and involve variations in color, depth, shape and pattern. To keep the experiment to the simple focus of the fractal dimension, the surfaces produced were generated for their aesthetic neutrality (lack of association to natural or synthetic commonly recognised form). Each surface was presented in consistent simple neutral color and the base shape/function used to create the fractal pattern was consistent. The only varying element was the dimension of fractal complexity in the surface patterns (see Figure 2 for examples of some surfaces used (different levels of fractal dimension). The study entailed the observation and questioning of the participants regarding their interactions with these fractal surfaces. The participants were observed interacting with the visual and tactile fractal surfaces before being questioned regarding their preferences (surfaces featured 3D relief elements in physical and displacement/bump maps in visual, as result D values here are in the 2 to 3 range).

The participants visual preferences as recorded in the trial indicate that 18 of the 25 participants (72%) showed a visual preference for surfaces and objects within the fractal range of D=2.3 to D=2.5. This finding matches the results from earlier studies and highlights the fact that the fractal dimension, independent of other factors such as colour, is playing a key role in the aesthetic appeal of the surface and that the simple adjustment of the fractal complexity can alter the perception of the surface significantly [START_REF] Pentland | Fractal-based description of natural scenes. Pattern Analysis and Machine Intelligence[END_REF], [START_REF] Spehar | Universal aesthetic of fractals[END_REF], [START_REF] Aks | Quantifying aesthetic preference for chaotic patterns[END_REF]. The observational findings from the study also strongly demonstrated this altered perception of the surface, caused by change in its fractal dimension. Of specific note were the correlations between response time and the observation of emotive signal, for example, the observed facial cues associated with negative responses were very strong in relation to an unseen response (virtual tactile/touch) but almost imperceptible in relation to a negative visual response. These observations also found that the unseen tactile response is usually quick, under a three second response time, especially in regard to the objects which offer a greater level of manipulation. The visual response however was usually much slower and considered. Observation of the participants showed that visual preference was given only after careful comparison and categorisation. The key difference with this study was that the fractal surfaces presented were automatically created to meet fractal dimensional values and varied only in this factor. Thus the findings indicate that the fractal dimension itself played a key role in the aesthetic appeal, or otherwise, of a surface.

Applying Fractal Principles & Designs

The contemporary built environment, in both the real world and the virtual game worlds, is dominated by the Cartesian concept of space. The world of architecture, bricks, textures, UV, tiles, panels and pavement offer a familiar rectilinear package in which to place our identities, both virtual and real. The familiarity is based upon col-lective experience; a mechanistic experience built brick at a time. In contrast the natural world is filled with rough edges, asymmetries, complex interactions, profound depth of scale and above all, life. Fractals and other forms of recursive patterns can provide rich visuals, not only in the real natural world but also in the virtual space of interactive computer games [START_REF] Spehar | Universal aesthetic of fractals[END_REF], [START_REF] Hendrikx | Procedural content generation for games: A survey[END_REF]. In particular these mathematical patterns can often provide more natural appearing and three-dimensional structural forms [START_REF] Pentland | Fractal-based description of natural scenes. Pattern Analysis and Machine Intelligence[END_REF]. The use of fractal/recursive methods to automatically create complete structural game environments has been explored in several projects and this offers potential to address some issues regarding the scale of modern interactive computer games and the need for increasing numbers of new spaces and environments [START_REF] Walsh | The use of an aesthetic measure for the evolution of fractal landscapes[END_REF], [START_REF] Bourke | Space Filling: A new algorithm for procedural creation of game assets[END_REF].

As the results from this study indicate, people find objects and surfaces that are too simple (D values < 2.25) or too complex (D values > 2.75) to be less appealing. By quantifying this through fractal dimension/complexity, this provided a mechanism through which spaces could be designed to be more or less appealing. The second phase of this research involved not simply understanding the nature of aesthetic response to fractal dimension, but actively adjusting the fractal dimension for effect.

Fractal Surface Designs & Complexity in Game Environments

Applying fractal techniques to surfaces that require a more natural feel, and hence the breakup of the simple linear nature of polygonal and flat textured surfaces, into richer "self-similar" patterns has been explored in various forms. The most common examples of this include the use of fractal methods to add noise and natural disturbance to fog, dust and water patterns [START_REF] Fan | Realistic Rendering of Three-Dimensional Ocean Waves Based on Fractal[END_REF], [START_REF] Haase | Interactive fractal compositions[END_REF]. The key focus of these uses is in natural surfaces, although the principals have potential in other areas.

The second phase of this project addressed the application of fractal patterns in surfaces, but not those used in natural features like water and fog, but instead looked at the use of fractal surfacing in the built environment. Stepping into the very heart of the rectilinear world of bricks, tiles and pavers, this research applied the concepts and knowledge gained in the earlier trials, on fractal complexity, to these built environment features. The focus of this work was on the use of surfacing techniques in the form of texture and bump maps applied using a special shading mechanism based around creating different levels of fractal complexity in the surface.

Fractal Surface Design & Implementation

To apply the concept of fractal complexity to the design of surfaces a tiling technique was implemented. The fractal complexity was controlled through the use of tiled textures based on a simple equilateral triangle. These tiles were different to the normal rectangular tiles used in texture maps and were instead sphinx hexiamond based tiles (consisting of six equilateral triangles arranged as in Figure 3). These tiles can be added together to make larger versions and also recursively subdivided to differing levels of complexity in a classic fractal self-similar manner. The use of alpha channel based textures, with the sphinx hexiamond based tile pattern, and a shader that transformed and re-combined them based on fractal dimension provided the ability to utilize fractal tile patterns at varying levels of fractal complexity. This level of complexity can be varied by arranging tiles in differing patterns and also by subdividing the tiles into greater levels of detail (see Figure 4 for examples). This implementation provided a practical method, using simple tile based elements, to algorithmically create surfaces with differing levels of fractal complexity on demand. When combined with the knowledge of aesthetic preference of fractal complexity levels, this provides a means to create new surfaces of both aesthetically pleasing (D 2.3-2.5), and, perhaps for some game scenarios, aesthetically undesirable form (eg. 2.5+ for spaces to become more uncomfortable for players).

Conclusions & Discussion

Fractal patterns offer an automated mathematical mechanism to create rich patterns. These rich patterns can be applied in interactive game environments and in many cases can add a natural feel to the spaces in which they are used. The findings from this study have identified that differing levels of fractal dimension and complexity in a surface have a direct affect on the viewers comfort with that surface. Applied to games design, through the use of texture and bump maps, applied using non-standard shaders to construct the fractal complexity, this allows the designer to apply an automated mathematical approach to creating surfaces that can make the viewer more or less comfortable with the space.

Fig. 1 .

 1 Fig. 1. Early experimental fractal forms from this project demonstrating natural features

Fig. 2 .

 2 Fig. 2. Fractal surfaces used in experimental trial.

Fig. 3 .

 3 Fig. 3. Sphinx hexiamond tiles and laying patterns.

Fig. 4 .

 4 Fig. 4. Laying tiles using differing methods to achieve differing fractal complexity levels.


Elham Saadatian

Thoriq Salafi
email: thoriqsalafi@nus.edu.sg

Hooman Samani
email: hooman@mail.ntpu.edu.tw

Yu De Lim

Ryohei Nakatsu

Artificial Intelligence Model of an Smartphone-Based Virtual Companion

Keywords: Artificial Intelligence, Entertaining Virtual Companion, Affective Computing

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The aim of this research is to employ various sensors integrated in the modern smartphones to observe the behavior of users and develop smart systems to enrich communications and interactions. Emerging field of mediated affective communication relates to the technologies that aim to mediate personal communication across distance. Contemporary lifestyle changes have led to design and adoption of technologies in support of modern lifestyle. In our earlier work, a comprehensive study of existing prototypical systems and related conceptual studies was investigated [START_REF] Saadatian | Technologically mediated intimate communication: An overview and future directions[END_REF].

Intelligent virtual agents are human-like embodied characters [START_REF] Herrero | Modelling intelligent virtual agent skills with humanlike senses[END_REF]. These autonomous artificial characters have applications in many fields, such as computer game [START_REF] Welsh | Enhancing information acquisition in game agents[END_REF], conversational agents [START_REF] Alfonsi | Sassy Chatbot Wins with Wit[END_REF], and affective robotics systems [START_REF] Samani | A multidisciplinary artificial intelligence model of an affective robot[END_REF] and many more. In this study, we have proposed and AI system for intelligent affective virtual companion on smartphone. In this respect, a model is proposed to detect the mood state of a user (based on the smartphones sensors' data), and generate corresponding reactions to the detected mood. The methodology is described in details by exploring mood recognition from smartphone sensory data, controlling the behavior of the virtual companion and visualization of the working process. The proposed model has been implemented and evaluated, which is described in this paper.

Methodology

The proposed methodology is anchored on the idea of combining uncertainty modeling with behavior networks, proposed in few previous works such as [START_REF] Han | A hybrid personal assistant based on bayesian networks and a rule-based system inside a smartphone[END_REF][START_REF] Han | Synthetic character with bayesian network and behavior network for intelligent smartphone[END_REF]. The improvement on the initial previously proposed ideas is made by considering the mood history of user using DBNs, using more sensors from the smartphone and fusion of inference techniques, as well as customized design of the behavior network for the specific purpose of the artificial affective companion. The system performs two functions of mood inference and behavior generation, which are detailed below.

User mood Recognition from smartphone data

The mood estimation module of the system (PME) is composed of SVM and DBNs. SVM detects the physical activity level using accelerometer data and DBNs is designed to infer and map the valence and arousal result to the twodimensional valence arousal model as illustrated in [START_REF] Ouwerkerk | Unobtrusive emotions sensing in daily life[END_REF].

The DBNs is selected due to the uncertainties and dynamic environment of the smartphone [START_REF] Malm | Managing context information in mobile devices[END_REF]. DBNs is well suited to the problem of inferring high-level information such as the mood state by using the low-level data obtained from the smartphone. That is because the mood state of the user depends probabilistically on many different factors. For example, with the accelerometer, we can know whether he is moving or not, and if so, whether he is moving fast or slow, and with the GPS, we can estimate the user location, whether he is at home or at work or somewhere outdoors. This low-level data obtained from the smartphone sensors, can predict the conditional probability of the user status. By setting the logic based, conditional probabilities of the user mood in relation to the smartphone sensor data, the mood state could be estimated without the need of precise knowledge and training the system such as in the method proposed by [START_REF] Likamwa | Moodscope: building a mood sensor from smartphone usage patterns[END_REF]. Figure 1 shows the designed DBNs model. The model infers the valance and arousal level of the user, which could be mapped to the Valance-Arousal Model (VAM) and define the detected mood state.

Behavior controller of the virtual companion

After detecting the users mood state, there is a need for an algorithm to control the respective artificial companion behavior. In this respect, a behavior network Fig. 1: Dynamic baysian network for mood estimation is designed. In the proposed behavior network, The environment and sensing part of the behavior network comes from DBNs output, which consists of user and the agents internal (or a remote user) mood and local time. There are three goals in this behavior network, imitation, feedback and special time. The imitation goal triggers the character to emulate his or her partner's mood. The feedback goal intends to give feedback for the user's mood. The special time goal greets the user about the time change. The special time goal is triggered when there is a change in the time period, such as morning afternoon and evening. The feedback goal will be triggered only when there is a prominent user's mood that reaches a certain threshold, otherwise the imitation goal will be activated. In the feedback mode, the personality of the partner is considered and represented by the animation speed. The behavior network will determine the animation of the character behavior, and the animation speed of the character depend on the personality of the partner. The more extrovert the partner is, the faster the animation of the character will move. The designed behavior network is shown in 2.

Visualization of the working process of the system

In order to demonstrate the generated behaviors of artificial companion, an experiment with two partners is performed. The reason for choosing a second real user (partner) is to attribute the artificial agent's mood to a real user. Artificial agents with anthropomorphic features could be perceived more natural and realistic [START_REF] Duffy | Anthropomorphism and the social robot[END_REF]. The first five sets of the mood data from the user, and its partner with the respective animated agent's behavior is shown in figure3. The proposed AI is applied in a smartphone Android app and the prototype screen shot is shown in Figure 3f.

System Evaluation

In order to evaluate the system, (n = 10) active smartphone users, including five females and five males, aged between 21 to 33, (M ean = 25.8, SD = 3.82), were randomly selected from National University of Singapore's staff and students. None of the participants had previous experience of interacting with similar technologies such as empathetic virtual agents or emotional robots. The evaluation was performed in two stages using a simulator. The first stage the PME module was evaluated and in the second stage, the fitness of the virtual companion behaviors was tested.

The PME was tested by comparing 120 samples of mood data inferred from the proposed PME model against the self-reported user moods. Each user has logged the smartphone usage and context data such as time, location, running apps, call logs etc. in relation to their self-perceived mood. The self-perceived user mood state was compared against the result of the proposed model. The Mann-Whitney U test was used to evaluate whether or not there was any significance difference in the valence arousal space between self-perceived and the automatically inferred results. The p value for two tailed is 0.64 for the valence space, and 0.73 for the arousal space. Both p values are higher than 5%. Therefore, could be concluded that there is no significance difference in the proposed model and user self-perceived affective state. This suggests the success of PME model in the correct inference of the mood state of the user.

In the second experiment, the goal was to confirm that the interactive companion could produce corresponding behaviors, which relates to the mood. The fitness of the virtual companion behaviors points to the correspondence of the auto-generated agent's behavior from the point of view of the users. Since, the suitability of the behavior is a subjective issue and cannot be measured quantitatively we adopted the method proposed by [START_REF] Yoon | An intelligent synthetic character for smartphone with bayesian networks and behavior selection networks[END_REF] to assess the model. In this method, the participants were given 10 different combinations of the user mood (themselves), artificial companion's mood, and time of the day (special time or not). For each scenario of the mentioned combinations, they observed 5 randomly generated behavior by the animated agent followed by 5 behavior generated by the proposed behavior network. Afterward, they were asked to rate the appropriateness of the behavior from 1 (strongly inappropriate) to 5 (strongly appropriate). The mean fitness scores of each participant were calculated as shown in table 1. The result was analyzed by Wilcoxon signed-rank test with the fitness scores. As a result, the p value was obtained as 0.005 < 0.5% which confirms the proposed model succeeded in generating suitable behavior compared to randomly generated behaviors.

Conclusion

The aim of this study was designing an (AI) model for smartphone to detect the user's mood state and generate adaptive behaviors via an animated artificial Participant pa1 pa2 pa3 pa4 pa5 pa6 pa7 pa8 pa9 pa10 Random 2.75 2.25 1.87 2.5 3.125 2.25 2.75 1.62 2.5 2.12 Behavior Net. 4 4.25 3.37 3.25 3.25 3.87 3.62 3.62 4 3.12 Table 1: Mean fitness ranks companion with internal mood state. The internal mood state of the agent could also come from another smartphone user. The AI model was developed based by fusion of a novel DBNs and Behavior network model. The system was tested by users, and the fitness of the generated behaviors were confirmed.

Acknowledgement

This research is supported by the Singapore National Research Foundation under its International Research Center Keio-NUS CUTE Center @ Singapore Funding Initiative and administered by the IDM Program Office.

Fig. 2 :Fig. 3 :

 23 Fig. 2: Behavior network for agent's behavior control


Geoffrey Hookham
email: geoffrey.hookham@newcastle.edu.au

Joyce Cooper
email: joyce.cooper@newcastle.edu.au

Rohan Rasiah
email: rohan.rasiah@newcastle.edu.au

Hayley Croft
email: hayley.croft@newcastle.edu.au

Keith Nesbitt
email: keith.nesbitt@newcastle.edu.au

Efficacy and Usability in the Design of a Pharmacy Education Game

Keywords: Engagement, Gamification, Pharmacy, Usability, Efficacy

This study introduces a puzzle game called the 'Virtual Dispensary' that was developed to assist in teaching dispensing skills to first year pharmacy students. We describe the key game elements and reports on initial findings from a study of the usability and effectiveness of the game.

Introduction

Throughout history, games have been used to educate, train, inform and distract [START_REF] Koster | A theory of fun for game design[END_REF].

As of 2014 there is a groundswell of enthusiasm surrounding the 'engaging' nature of computer games and the potential to leverage this engagement for more 'effective' education [START_REF] Kapp | The Gamification of Learning and Instruction: Game-based Methods and Strategies for Training and Education[END_REF]. This motivates a number of research questions around serious games about what is engagement, how to measure effectiveness and the role of usability in ensuring games meet there serious intention.

The game described in this study, the Virtual Dispensary, was developed to assist teaching dispensing skills to first year Pharmacy students. We take an iterative approach to creating the Virtual Dispensary, developing and evaluating game prototypes to ensure we meet the expected educational directions of the serious game and also ensuring that key usability issues that might detract from engagement are identified early in the development process. We report here on some of the key design elements integrated into the game and report on a first usability trial with a representative sample of students. Both the novel domain and the issues uncovered should be of interest to all designers of serious games.

2

The Virtual Dispensary

The online Virtual Dispensary provides pharmacy students with an exploratory space that allows the students to practice typical forensic skills related to prescribing medi-cations. A single play session of the game requires the student to solve a quiz that requires navigating and interaction with elements in a virtual pharmacy. The structure and gameplay of the Virtual Dispensary prototype places the game within the 'puzzle game' genre, as it consists of conceptual reasoning challenges requiring extrinsic knowledge for successful completion [START_REF] Adams | Fundamentals of Game Design[END_REF].

The game world itself is based on a virtual tour created from sixteen, 360º panoramic photographs of a community pharmacy. The functionality of the community pharmacy tour allows students to navigate about the pharmacy and zoom in to examine products in detail. The tour also provides information about the key locations of the pharmacy by way of auditory descriptions and information pop-ups. Players have the task of identifying and verifying prescriptions, which includes checking medication packaging and labels on interactive 3D models situated at typical locations.

Usability Study

The subjects for the study were 10 students currently studying the Masters of Pharmacy program at the University of Newcastle. There were six males, and four females. Four of the subjects were under the age of 23, four were between the ages of 24-34 and two were older than 35. Most subjects (n=9) completed the game in less than 30 minutes while one subject played for slightly longer. After completing the game, subjects completed an anonymous survey, containing eleven Likert-scale questions designed to measure the perceived effectiveness and usability (Table 1) of the Virtual Dispensary. Students could also respond to two open questions to identify the features of the Virtual Dispensary they enjoyed the most and to suggest possible improvements.

In terms of effectiveness, all 10 subjects agreed that the Virtual Dispensary provided an effective way of learning about dispensing. For the two questions related to confidence, 12 of the twenty responses agreed that the game improved their confidence about dispensing while five disagreed. Seven of the subjects formed no opinion about whether or not the application stimulated their interest to learn.

When asked to identify the best thing about the Virtual Dispensary, four noted the scripting examples with checking. Three subjects highlighted the realism of the pharmacy environment and three suggesting the interactive products and packing as key elements. A range of improvements were suggested, these focused on providing more content, in particular three subjects requested increasing the number of products and scripts available. Another four subjects wanted more product information to be integrated into the game. Other subjects suggested integrating even more elements of pharmacy practice, such as patient counselling into the game.

According to the feedback, the application of interactive and game elements was perceived to be a fun and effective learning technique, however this is no indication of the effectiveness in terms of learning outcomes. There were some interesting feedback elements, namely that the majority of respondents indicated that the game functions were well integrated. Further development that provides more product infor-mation and interactive components is the next goal of this research followed by better measure of effectiveness using pre and post testing of student knowledge [START_REF] Girard | Serious Games as new education tools: how effective are they? A meta-analysis of recent studies[END_REF].

Table 1 .

 1 Perceived Effectiveness and Usability Questions and Responses (n=10)

	Effectiveness Questions	strongly disagree	disagree	no opinion	agree	strongly agree
	Using this type of technology is an effec-
	tive way of learning about dispensing				5	5
	I feel I have gained confidence from
	learning more about dispensing before my next placement		2	3	4	1
	I feel I have gained confidence from
	learning more about dispensing before my dispensing exam		3		6	1
	The Virtual Dispensary Application
	stimulated my interest to learn		1	7	2
	Usability Questions	strongly disagree	disagree	no opinion	agree	strongly agree
	I thought the application was easy to use		1	2	4	3
	I thought the application was fun to use			1	7	2
	I thought the application was realistic				7	3
	I found the different functions in this
	application were well integrated	1		4	3	2
	I imagine that people would learn to use
	this application very quickly		2		4	4
	I thought there was too much incon-
	sistency in the application	1	4	5
	I need more instructions on how to use
	the application before I am confident to use it effectively	1	3	3	3


Degenne Rémy
email: degenne@cmla.ens-cachan.fr

Lmpa

Vianney Perchet
email: perchet@normalesup.org

Combinatorial semi-bandit with known covariance

The combinatorial stochastic semi-bandit problem is an extension of the classical multi-armed bandit problem in which an algorithm pulls more than one arm at each stage and the rewards of all pulled arms are revealed. One difference with the single arm variant is that the dependency structure of the arms is crucial. Previous works on this setting either used a worst-case approach or imposed independence of the arms. We introduce a way to quantify the dependency structure of the problem and design an algorithm that adapts to it. The algorithm is based on linear regression and the analysis develops techniques from the linear bandit literature. By comparing its performance to a new lower bound, we prove that it is optimal, up to a poly-logarithmic factor in the number of pulled arms.

Introduction and setting

The multi-armed bandit problem (MAB) is a sequential learning task in which an algorithm takes at each stage a decision (or, "pulls an arm"). It then gets a reward from this choice, with the goal of maximizing the cumulative reward [START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF]. We consider here its stochastic combinatorial extension, in which the algorithm chooses at each stage a subset of arms [START_REF] Audibert | Regret in online combinatorial optimization[END_REF][START_REF] Cesa | Combinatorial bandits[END_REF][START_REF] Chen | Combinatorial multi-armed bandit: General framework and applications[END_REF][START_REF] Gai | Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations[END_REF]. These arms could form, for example, the path from an origin to a destination in a network. In the combinatorial setting, contrary to the the classical MAB, the inter-dependencies between the arms can play a role (we consider that the distribution of rewards is invariant with time). We investigate here how the covariance structure of the arms affects the difficulty of the learning task and whether it is possible to design a unique algorithm capable of performing optimally in all cases from the simple scenario with independent rewards to the more challenging scenario of general correlated rewards.

Formally, at each stage t ∈ N, t ≥ 1, an algorithm pulls m ≥ 1 arms among d ≥ m. Such a set of m arms is called an "action" and will be denoted by A t ∈ {0, 1} d , a vector with exactly m non-zero entries. The possible actions are restricted to an arbitrary fixed subset A ⊂ {0, 1} d . After choosing action A t , the algorithm receives the reward A t X t , where X t ∈ R d is the vector encapsulating the reward of the d arms at stage t. The successive reward vectors (X t ) t≥1 are i.i.d with unknown mean µ ∈ R d . We consider a semi-bandit feedback system: after choosing the action A t , the algorithm observes the reward of each of the arms in that action, but not the other rewards. Other possible feedbacks previously studied include bandit (only A t X t is revealed) and full information (X t is revealed). The goal of the algorithm is to maximize the cumulated reward up to stage T ≥ 1 or equivalently to minimize the expected regret, which is the difference of the reward that would have been gained by choosing the best action in hindsight A * and what was actually gained:

ER T = E T t=1 (A * µ -A t µ) .
For an action A ∈ A, the difference ∆ A = (A * µ -A µ) is called gap of A. We denote by ∆ t the gap of A t , so that regret rewrites as ER T = E T t=1 ∆ t . We also define the minimal gap of an arm, ∆ i,min = min {A∈A:i∈A} ∆ A .

This setting was already studied [START_REF] Cesa | Combinatorial bandits[END_REF], most recently in [START_REF] Richard Combes | Combinatorial Bandits Revisited[END_REF][START_REF] Branislav Kveton | Tight regret bounds for stochastic combinatorial semi-bandits[END_REF], where two different algorithms are used to tackle on one hand the case where the arms have independent rewards and on the other hand the general bounded case. The regret guaranties of the two algorithms are different and reflect that the independent case is easier. Another algorithm for the independent arms case based on Thompson Sampling was introduced in [START_REF] Komiyama | Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays[END_REF]. One of the main objectives of this paper is to design a unique algorithm that can adapt to the covariance structure of the problem when prior information is available.

The following notations will be used throughout the paper: given a matrix M (resp. vector v), its (i, j) th (resp. i th ) coefficient is denoted by M (ij) (resp. v (i) ). For a matrix M , the diagonal matrix with same diagonal as M is denoted by Σ M .

We denote by η t the noise in the reward, i.e. η t := X t -µ. We consider a subgaussian setting, in which we suppose that there is a positive semi-definite matrix C such that for all t ≥ 1,

∀u ∈ R d , E[e u ηt ] ≤ e 1 2 u Cu .
This is equivalent to the usual setting for bandits where we suppose that the individual arms are subgaussian. Indeed if we have such a matrix C then each η

(i) t is √ C (ii) -subgaussian.
And under a subgaussian arms assumption, such a matrix always exists. This setting encompasses the case of bounded rewards.

We call C a subgaussian covariance matrix of the noise (see appendix A of the supplementary material). A good knowledge of C can simplify the problem greatly, as we will show. In the case of 1-subgaussian independent rewards, in which C can be chosen diagonal, a known lower bound on the regret appearing in [START_REF] Richard Combes | Combinatorial Bandits Revisited[END_REF] is d ∆ log T , while [START_REF] Branislav Kveton | Tight regret bounds for stochastic combinatorial semi-bandits[END_REF] proves a dm ∆ log T lower bound in general. Our goal here is to investigate the spectrum of intermediate cases between these two settings, from the uninformed general case to the independent case in which one has much information on the relations between the arm rewards. We characterize the difficulty of the problem as a function of the subgaussian covariance matrix C. We suppose that we know a positive semi-definite matrix Γ such that for all vectors v with positive coordinates, v Cv ≤ v Γv, property that we denote by C + Γ. Γ reflects the prior information available about the possible degree of independence of the arms. We will study algorithms that enjoy regret bounds as functions of Γ.

The matrix Γ can be chosen such that all its coefficients are non-negative and verify for all i, j, jj) . From now on, we suppose that it is the case. In the following, we will use t such that η t = C 1 /2 t and write for the reward:

Γ (ij) ≤ √ Γ (ii) Γ (
X t = µ + C 1 /2 t .

Lower bound

We first prove a lower bound on the regret of any algorithm, demonstrating the link between the subgaussian covariance matrix and the difficulty of the problem. It depends on the maximal off-diagonal correlation coefficient of the covariance matrix. This coefficient is γ = max {(i,j)∈[d],i =j}

C (ij) √ C (ii) C (jj)
. The bound is valid for consistent algorithms [START_REF] Leung | Asymptotically efficient adaptive allocation rules[END_REF], for which the regret on any problem verifies ER t = o(t a ) as t → +∞ for all a > 0.

Theorem 1. Suppose to simplify that d is a multiple of m. Then, for any ∆ > 0, for any consistent algorithm, there is a problem with gaps ∆, σ-subgaussian arms and correlation coefficients smaller than γ ∈ [0, 1] on which the regret is such that

lim inf t→+∞ ER t log t ≥ (1 + γ(m -1)) 2σ 2 (d -m) ∆
This bound is a consequence of the classical result of [START_REF] Leung | Asymptotically efficient adaptive allocation rules[END_REF] for multi-armed bandits, applied to the problem of choosing one among d/m paths, each of which has m different successive edges (Figure 1). The rewards in the same path are correlated but the paths are independent. A complete proof can be found in appendix B.1 of the supplementary material.

OLS-UCB Algorithm and analysis

Faced with the combinatorial semi-bandit at stage t ≥ 1, the observations from t -1 stages form as many linear equations and the goal of an algorithm is to choose the best action. To find the action with the highest mean, we estimate the mean of all arms. This can be viewed as a regression problem. The design of our algorithm stems from this observation and is inspired by linear regression in the fixed design setting, similarly to what was done in the stochastic linear bandit literature [START_REF] Rusmevichientong | Linearly Parameterized Bandits[END_REF][START_REF] Filippi | Parametric Bandits: The Generalized Linear Case[END_REF]. There are many estimators for linear regression and we focus on the one that is simple enough and adaptive: Ordinary Least Squares (OLS).

Fixed design linear regression and OLS-UCB algorithm

For an action A ∈ A, let I A be the diagonal matrix with a 1 at line i if A (i) = 1 and 0 otherwise. For a matrix M , we also denote by M A the matrix I A M I A . At stage t, if all actions A 1 , . . . , A t were independent of the rewards, we would have observed a set of linear equations

I A1 X 1 = I A1 µ + I A1 η 1 . . . I At-1 X t-1 = I At-1 µ + I At-1 η t-1
and we could use the OLS estimator to estimate µ, which is unbiased and has a known subgaussian constant controlling its variance. This is however not true in our online setting since the successive actions are not independent. At stage t, we define

n (i) t = t-1 s=1 I{i ∈ A s }, n (ij) t = t-1 s=1 I{i ∈ A s }I{j ∈ A s } and D t = t-1 s=1 I As ,
where n

(i)
t is the number of times arm i has been pulled before stage t and D t is a diagonal matrix of these numbers. The OLS estimator is, for an arm i ∈

[d], μ(i) t = 1 n (i) t s<t:i∈As X (i) s = µ (i) + (D -1 t t-1 s=1 I As C 1 /2 s ) (i) .
Then for all A ∈ A, A (μ t -µ) in the fixed design setting has a subgaussian matrix equal to D -1 t ( t-1 s=1 C As )D -1 t . We get confidence intervals for the estimates and can use an upper confidence bound strategy [START_REF] Leung | Asymptotically efficient adaptive allocation rules[END_REF][START_REF] Auer | Finite-time analysis of the multiarmed bandit problem[END_REF]. In the online learning setting the actions are not independent but we will show that using this estimator still leads to estimates that are well concentrated around µ, with confidence intervals given by the same subgaussian matrix. The algorithm OLS-UCB (Algorithm 1) results from an application of an upper confidence bound strategy with this estimator.

Algorithm 1 OLS-UCB. Require: Positive semi-definite matrix Γ, real parameter λ > 0.

1: Choose actions such that each arm is pulled at least one time.

2: loop: at stage t, 3:

A t = arg max A A μt + E t (A) with E t (A) = 2f (t) A D -1 t (λΣ Γ D t + t-1 s=1 Γ As )D -1 t A.

4:

Choose action A t , observe I At X t .

5:

Update μt , D t .

6: end loop

We now turn to an analysis of the regret of OLS-UCB. At any stage t ≥ 1 of the algorithm, let

γ t = max {(i,j)∈At,i =j} Γ (ij) √ Γ (ii) Γ (jj) be the maximal off-diagonal correlation coefficient of Γ At and let γ = max {t∈[T ]} γ t be the maximum up to stage T .
Theorem 2. The OLS-UCB algorithm with parameter λ > 0 and f (t) = log t + (m + 2) log log t + m 2 log(1 + e λ ) enjoys for all times T ≥ 1 the regret bound

E[R T ] ≤16f (T ) i∈[d] Γ (ii) ∆ i,min 5(λ + 1 -γ) log m 1.6 2 + 45γm + 8dm 2 max i {C (ii) }∆ max ∆ 2 min + 4∆ max ,
where x stands for the smallest positive integer bigger than or equal to x. In particular, 0 = 1.

This bound shows the transition between a general case with a dm log T ∆ regime and an independent case with a d log 2 m log T ∆ upper bound (we recall that the lower bound is of the order of d log T ∆ ). The weight of each case is given by the maximum correlation parameter γ. The parameter λ seems to be an artefact of the analysis and can in practice be taken very small or even equal to 0.

Figure 1 illustrates the regret of OLS-UCB on the parallel paths problem used to derive the lower bound. It shows a linear dependency in γ and supports the hypothesis that the true upper bound matches the lower bound with a dependency in m and γ of the form (1 + γ(m -1)).

Corollary 1. The OLS-UCB algorithm with matrix Γ and parameter λ > 0 has a regret bounded as

E[R T ] ≤ O( dT log T max i∈[d] {Γ (ii) } 5(λ + 1 -γ) log m 1.6 2 + 45γm ) .
Proof. We write that the regret up to stage T is bounded by ∆T for actions with gap smaller than some ∆ and bounded using theorem 2 for other actions (with ∆ min ≥ ∆). Maximizing over ∆ then gives the result.

Comparison with other algorithms

Previous works supposed that the rewards of the individual arms are in [0, 1], which gives them a 1 /2-subgaussian property. Hence we suppose (∀i

∈ [d], C (ii) = 1 /2) for our comparison.
In the independent case, our algorithm is the same as ESCB-2 from [START_REF] Richard Combes | Combinatorial Bandits Revisited[END_REF], up to the parameter λ. That paper shows that ESCB-2 enjoys an O( d

√ m log T ∆ ) upper bound but our analysis tighten it to O( d log 2 m log T ∆ ).
In the general (worst) case, [START_REF] Branislav Kveton | Tight regret bounds for stochastic combinatorial semi-bandits[END_REF] prove an O( dm log T ∆ ) upper bound (which is tight) using CombUCB1, a UCB based algorithm introduced in [START_REF] Chen | Combinatorial multi-armed bandit: General framework and applications[END_REF] which at stage t uses the exploration term

√ 1.5 log t i∈A 1/ n (i) t . Our exploration term always verifies E t (A) ≤ f (t) i∈A 1/ n (i)
t with f (t) ≈ log t (see section 3.6). Their exploration term is a worst-case confidence interval for the means. Their broader confidence intervals however have the desirable property that one can find the action that realizes the maximum index by solving a linear optimization problem, making their algorithm computationally efficient, quality that both ESCB and OLS-UCB are lacking.

None of the two former algorithms benefits from guaranties in the other regime. The regret of ESCB in the general possibly correlated case is unknown and the regret bound for CombUCB1 is not improved in the independent case. In contrast, OLS-UCB is adaptive in the sense that its performance gets better when more information is available on the independence of the arms.

Regret Decomposition

Let H i,t = {|μ (i) t -µ (i) | ≥ ∆t 2m } and H t = ∪ d i=1 H i,t .
H t is the event that at least one coordinate of μt is far from the true mean. Let G t = {A * µ ≥ A * μt + E t (A * )} be the event that the estimate of the optimal action is below its true mean by a big margin. We decompose the regret according to these events:

R T ≤ T t=1 ∆ t I{G t , H t } + T t=1 ∆ t I{G t } + T t=1 ∆ t I{H t }
Events G t and H t are rare and lead to a finite regret (see below). We first simplify the regret due to G t ∩ H t and show that it is bounded by the "variance" term of the algorithm. Lemma 1. With the algorithm choosing at stage t the action

A t = arg max A (A μt + E t (A)), we have ∆ t I{G t , H t } ≤ 2E t (A t )I{∆ t ≤ E t (A t )}.
Proof in appendix B.2 of the supplementary material. Then the regret is cut into three terms,

R T ≤ 2 T t=1 E t (A t )I{∆ t ≤ 2E t (A t )} + T t=1 ∆ t I{G t } + T t=1 ∆ t I{H t } .
The three terms will be bounded as follows:

• The H t term leads to a finite regret from a simple application of Hoeffding's inequality.

• The G t term leads to a finite regret for a good choice of f (t). This is where we need to show that the exploration term of the algorithm gives a high probability upper confidence bound of the reward.

• The E t (A t ) term, or variance term, is the main source of the regret and is bounded using ideas similar to the ones used in existing works on semi-bandits.

Expected regret from H t

Lemma 2. The expected regret due to the event

H t is E[ T t=1 ∆ t I{H t }] ≤ 8dm 2 maxi{C (ii) }∆max ∆ 2 min .
The proof uses Hoeffding's inequality on the arm mean estimates and can be found in appendix B.2 of the supplementary material.

Expected regret from G t

We want to bound the probability that the estimated reward for the optimal action is far from its mean. We show that it is sufficient to control a selfnormalized sum and do it using arguments from [START_REF] Victor H Peña | Self-normalized processes: Limit theory and Statistical Applications[END_REF], or [START_REF] Abbasi-Yadkori | Improved Algorithms for Linear Stochastic Bandits[END_REF] who applied them to linear bandits. The analysis also involves a peeling argument, as was done in one dimension by [START_REF] Garivier | Informational confidence bounds for self-normalized averages and applications[END_REF] to bound a similar quantity.

Lemma 3. Let δ t > 0. With f (δ t ) = log(1/δ t )+m log log t+ m 2 log(1+ e λ
) and an algorithm given by the exploration term

E t (A) = 2 f (δ t ) A D -1 t (λΣ Γ D t + t-1 s=1 Γ As )D -1 t A, then the event G t = {A * µ ≥ A * μt + E t (A * )} verifies P{G t } ≤ δ t .
With δ 1 = 1 and δ t = 1 t log 2 t for t ≥ 2, such that f (δ t ) = f (t), the regret due to G t is finite in expectation, bounded by 4∆ max .

Proof. We use a peeling argument: let η > 0 and for a = (a 1 , . . . , a m ) ∈ N m , let D a ⊂ [T ] be a subset of indices defined by

(t ∈ D a ⇔ ∀i ∈ A * , (1 + η) ai ≤ n (i) t < (1 + η) ai+1 ). For any B t ∈ R, P A * (µ -μt ) ≥ B t ≤ a P A * (µ -μt ) ≥ B t |t ∈ D a .
The number of possible sets D a for t is bounded by (log t/ log(1 + η)) m , since each number of pulls n (i) t for i ∈ A * is bounded by t. We now search a bound of the form P A * (µ -μt ) ≥ B t |t ∈ D a . Suppose t ∈ D a and let D be a positive definite diagonal matrix (that depends on a).

Let

S t = t-1 s=1 I As∩A * C 1 /2 s , V t = t-1 s=1 C As∩A * and I Vt+D ( ) = 1 2 S t 2 (Vt+D) -1 . Lemma 4. Let δ t > 0 and let f (δ t ) be a function of δ t . With a choice of D such that I A * D λI A * Σ C D t for all t in D a , P A * (µ-μ t )≥ 2 f (δ t )A * D -1 t (λΣ C D t +V t )D -1 t A * t∈D a ≤ P I Vt+D ( )≥ f (δ t )|t∈D a . Proof in appendix B.2 of the supplementary material.
The self-normalized sum I Vt ( ) is an interesting quantity for the following reason: exp(

1 2 I Vt ( )) = max u∈R d t-1 s=1 exp(u I As∩A * C 1 /2 s -u C As∩A * u).
For a given u, the exponential is smaller that 1 in expectation, from the subgaussian hypothesis. The maximum of the expectation is then smaller than 1. To control I Vt ( ), we are however interested in the expectation of this maximum and cannot interchange max and E. The method of mixtures circumvents this difficulty: it provides an approximation of the maximum by integrating the exponential against a multivariate normal centered at the point V -1 t S t , where the maximum is attained. The integrals over u and can then be swapped by Fubini's theorem to get an approximation of the expectation of the maximum using an integral of the expectations. Doing so leads to the following lemma, extracted from the proof of Theorem 1 of [START_REF] Abbasi-Yadkori | Improved Algorithms for Linear Stochastic Bandits[END_REF].

Lemma 5. Let D be a positive definite matrix that does not depend on t and

M t (D) = det D det(Vt+D) exp(I Vt+D ( )). Then E[M t (D)] ≤ 1. We rewrite P I Vt+D ( ) ≥ f (δ t ) to introduce M t (D), P I Vt+D ( ) ≥ f (δ t )|t∈D a = P M t (D) ≥ 1 det(I d + D -1 /2 V t D -1 /2 ) exp( f (δ t )) t∈D a .
The peeling lets us bound V t . Let D a be the diagonal matrix with entry (i, i) equal to (1 + η) ai for i ∈ A * and 0 elsewhere.

Lemma 6. With D = λΣ C D a + I [d]\A * , det(I d + D -1 /2 V t D -1 /2 ) ≤ (1 + 1+η λ ) m .
The union bound on the sets D a and Markov's inequality give

P A * (µ -μt ) ≥ 2 f (δ t ) λA * Σ C D -1 t A * + A * D -1 t V t D -1 t A * ≤ Da P M t (D) ≥ (1 + 1 + η λ ) -m/2 exp( f (δ t ))|t ∈ D a ≤ log t log(1 + η) m (1 + 1 + η λ ) m/2 exp(-f (δ t ))
For η = e -1 and f (δ t ) as in lemma 3, this is bounded by δ t . The result with Γ instead of C is a consequence of C + Γ. With δ 1 = 1 and δ t = 1/(t log 2 t) for t ≥ 2, the regret due to G t is

E[ T t=1 ∆ t I{G t }] ≤ ∆ max (1 + T t=2 1 t log 2 t
) ≤ 4∆ max .

Bounding the variance term

The goal of this section is to bound E t (A t ) under the event jj) . From the Cauchy-Schwartz inequality, n

{∆ t ≤ E t (A t )}. Let γ t ∈ [0, 1] such that for all i, j ∈ A t with i = j, Γ (ij) ≤ γ t √ Γ (ii) Γ (
(ij) t ≤ n (i) t n (j)
t . Using these two inequalities,

A t D -1 t ( t-1 s=1 Γ As )D -1 t A t = i,j∈At n (ij) t Γ (ij) n (i) t n (j) t ≤ (1 -γ t ) i∈At Γ (ii) n (i) t + γ t ( i∈At Γ (ii) n (i) t ) 2 .
We recognize here the forms of the indexes used in [START_REF] Richard Combes | Combinatorial Bandits Revisited[END_REF] for independent arms (left term) and [START_REF] Branislav Kveton | Tight regret bounds for stochastic combinatorial semi-bandits[END_REF] for general arms (right term). Using ∆ t ≤ E t (A t ) we get

∆ 2 t 8f (t) ≤ (λ + 1 -γ t ) i∈At Γ (ii) n (i) t + γ t ( i∈At Γ (ii) n (i) t ) 2 . (1)
The strategy from here is to find events that must happen when (1) holds and to show that these events cannot happen very often. For positive integers j and t and for e ∈ {1, 2}, we define the set of arms in A t that were pulled less than a given threshold: S j t,e = {i ∈ A t , n

(i) t ≤ α j,e 8f (t)Γ (ii) ge(m,γt) ∆ 2 t
}, with g e (m, γ t ) to be stated later and (α i,e ) i≥1 a decreasing sequence. Let also S 0 t,e = A t . (S j t,e ) j≥0 is decreasing for the inclusion of sets and we impose lim j→+∞ α j,e = 0, such that there is an index j ∅ with S j ∅ t,e = ∅. We introduce another positive sequence (β j,e ) j≥0 and consider the events that at least mβ j,e arms in A t are in the set S j t,e and that the same is false for k < j, i.e. for t ≥ 1, A j t,e = {|S j t,e | ≥ mβ j,e ; ∀k < j, |S k t,e | < mβ k,e }. To avoid having some of these events being impossible we choose (β j,e ) j≥0 decreasing. We also impose β 0,e = 1, such that |S 0 t,e | = mβ 0,e . Let then A t,e = ∪ +∞ j=1 A j t,e and A t = A t,1 ∪ A t,2 . We will show that A t must happen for (1) to be true. First, remark that under a condition on (β j,e ) j≥0 , A t is a finite union of events, Lemma 7. For e ∈ {1, 2}, if there exists j 0,e such that β j0,e,e ≤ 1/m, then A t,e = ∪ j0 j=1 A j t,e . We now show that A t is impossible by proving a contradiction in (1). Lemma 8. Under the event A t,1 , if there exists j 0 such that

β j0,1 ≤ 1/m, then i∈At Γ (ii) n (i) t < m∆ 2 t 8f (t)g 1 (m, γ t )   j0 j=1 β j-1,1 -β j,1 α j,1 + β j0,1 α j0,1   .
Under the event A t,2 , if lim j→+∞ β j,2 / √ α j,2 = 0 and

+∞ j=1 βj-1,2-βj,2 √ αj,2 exists, then i∈At Γ (ii) n (i) t ≤ m∆ t 8f (t)g 2 (m, γ t ) +∞ j=1 β j-1,2 -β j,2 √ α j,2 .
A proof can be found in appendix B.2 of the supplementary material. To ensure that the conditions of these lemmas are fulfilled, we impose that (β i,1 ) i≥0 and (β i,2 ) i≥0 have limit 0 and that lim j→+∞ β j,2 / √ α j,2 = 0. Let j 0,1 be the smallest integer such that

β j0,1,1 ≤ 1/m. Let l 1 = βj 0,1 ,1 αj 0,1 ,1 + j0,1 j=1 βj-1,1-βj,1 αj,1
and

l 2 = +∞ j=1 βj-1,2-βj,2 √ αj,2
. Using the two last lemmas with (1), we get that if A t is true,

∆ 2 t 8f (t) < ∆ 2 t 8f (t) (λ + 1 -γ t ) ml 1 g 1 (m, γ t ) + γ t m 2 l 2 2 g 2 (m, γ t ) .
Taking g 1 (m, γ t ) = 2(λ + 1 -γ t )ml 1 and g 2 (m, γ t ) = 2γ t m 2 l 2 2 , we get a contradiction. Hence with these choices A t must happen. The regret bound will be obtained by a union bound on the events that form A t . First suppose that all gaps are equal to the same ∆. Lemma 9. Let γ = max t≥1 γ t . For j ∈ N * , the event A j t,e happens at most dαj,e8f (T ) maxi{Γ (ii) }ge(m,γ) mβj,e∆ 2 times.

Proof. Each time that A j t,e happens, the counter of plays n (i) t of at least mβ je arms is incremented. After αj,e8f (T ) maxi{Γ (ii) }ge(m,γ) ∆ 2

increments, an arm cannot verify the condition on n times.

If all gaps are equal to ∆, an union bound for A t gives

E[ T t=1 ∆I{H t ∩ G t }] ≤ 16 max i∈[d] {Γ (ii) } f (T ) ∆ d   (λ + 1 -γ)l 1 j0,1 j=1 α j,1 β j,1 + γml 2 2 +∞ j=1 α j,2 β j,2   .
The general case requires more involved manipulations but the result is similar and no new important idea is used. The following lemma is proved in appendix B.2 of the supplementary material:

Lemma 10. Let γ (i) = max {t,i∈At} γ t . The regret from the event H t ∩ G t is such that E[ T t=1 ∆ t I{H t ∩ G t }] ≤ 16f (T ) i∈[d] Γ (ii) ∆ i,min   (λ + 1 -γ)l 1 j0 j=1 α j,1 β j,1 + γml 2 2 +∞ j=1 α j,2 β j,2   .
Finally we can find sequences (α j,1 ) j≥1 , (α j,2 ) j≥1 , (β j,1 ) j≥0 and (β j,2 ) j≥0 such that

E[ T t=1 ∆I{H t ∩ G t }] ≤ 16f (T ) i∈[d] Γ (ii) ∆ i,min 5(λ + 1 -γ (i) ) log m 1.6 2 + 45γ (i) m
See appendix C of the supplementary material. In [START_REF] Richard Combes | Combinatorial Bandits Revisited[END_REF], α i,1 and β i,1 were such that the log 2 m term was replaced by √ m. Our choice is also applicable to their ESCB algorithm. Our use of geometric sequences is only optimal among sequences such that β i,1 = α i,1 for all i ≥ 1. It is unknown to us if one can do better. With this control of the variance term, we finally proved Theorem 2.

Conclusion

We defined a continuum of settings from the general to the independent arms cases which is suitable for the analysis of semi-bandit algorithms. We exhibited a lower bound scaling with a parameter that quantifies the particular setting in this continuum and proposed an algorithm inspired from linear regression with an upper bound that matches the lower bound up to a log 2 m term. Finally we showed how to use tools from the linear bandits literature to analyse algorithms for the combinatorial bandit case that are based on linear regression.

It would be interesting to estimate the subgaussian covariance matrix online to attain good regret bounds without prior knowledge. Also, our algorithm is not computationally efficient since it requires the computation of an argmax over the actions at each stage. It may be possible to compute this argmax less often and still keep the regret guaranty, as was done in [START_REF] Abbasi-Yadkori | Improved Algorithms for Linear Stochastic Bandits[END_REF] and [START_REF] Richard Combes | Combinatorial Bandits Revisited[END_REF].

On a broader scope, the inspiration from linear regression could lead to algorithms using different estimators, adapted to the structure of the problem. For example, the weighted least-square estimator is also unbiased and has smaller variance than OLS. Or one could take advantage of a sparse covariance matrix by using sparse estimators, as was done in the linear bandit case in [START_REF] Carpentier | Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit[END_REF].

A The subgaussian covariance matrix

Property 0. An α-subgaussian variable X verifies Var[X] ≤ α 2 .
Let η be a noise in R d with mean 0 and subgaussian covariance matrix C. The following properties are immediate consequences of property 0 and are presented as a justification for the name subgaussian "covariance" matrix.

Property 1. For all i ∈ [d], Var[η (i) ] ≤ C (ii) . Property 2. For all (i, j) ∈ [d], Var[η (i) ] + Var[η (j) ] + 2Cov[η (i) , η (j) ] ≤ C (ii) + C (jj) + 2C (ij) . Property 3. If Var[η (i) ] = C (ii) and Var[η (j) ] = C (jj) , Cov[η (i) , η (j) ] ≤ C (ij) .

B Missing proofs

B.1 Lower bound

Proof. We consider the problem where A is a set of d/m disjoint actions A 1 , . . . , A d/m and suppose that these actions are independent. This is not more than a bandit problem with d/m arms, each with m sub-arms. We choose a noise ∼ N (0, σ 2 I d ) (multivariate normal with mean 0 and covariance matrix I d ) and a subgaussian matrix C = (1 -γ)I d + γJ blocs , where J blocs is a bloc matrix such that each m × m bloc indexed by an action A j contains only ones and other coefficients are 0. The actions are independent and the sub-arms are correlated with correlation γ.

Then C 1 /2 = √ 1 -γI d + 1 m ( 1 + γ(m -1) - √ 1 -γ)J blocs .
The mean of the best action is taken to be 0 and the mean of other actions is -∆. The algorithm has access to all these informations, except for the identity of the optimal action. Suppose for notational convenience that the first action is optimal. The reward of the best action is ν 1 = 1 + γ(m -1) i∈A1 i , while the reward of a sub-optimal action A j is ν j = 1 + γ(m -1) i∈Aj i -∆.

We use a result from [START_REF] Leung | Asymptotically efficient adaptive allocation rules[END_REF] which states that in this bandit case,

lim inf t→+∞ R t log t ≥ d/m j=2 ∆ D KL (ν j , ν 1 ) . (2)
In our setting, the Kullback-Leibler divergence is

D KL (ν j , ν 1 ) = D KL ( 1 + γ(m -1) i∈Aj i -∆, 1 + γ(m -1) i∈A1 i ) = D KL N (-∆, σ 2 m(1 + γ(m -1))), N (0, σ 2 m(1 + γ(m -1))) = ∆ 2 2σ 2 m(1 + γ(m -1))
.

This together with (2) proves the theorem.

B.2 Upper bound

Proof. Lemma 1.

I{G t , H t } = I{A * µ ≤ A * μt + E t (A * ), H t } ≤ I{A * µ ≤ A t μt + E t (A t ), H t } ≤ I{A * µ ≤ A t µ + ∆ t 2 + E t (A t )} = I{∆ t ≤ 2E t (A t )} ,
where we used first that the algorithm chooses A t = arg max A (A μt + E t (A)), then that under H t we have A t μt ≤ A t µ + ∆t 2 .

E[

T t=1 ∆ t I{G t , H t }] ≤ T t=1 E[∆ t I{∆ t ≤ 2E t (A t )}] ≤ 2 T t=1 E[E t (A t )I{∆ t ≤ 2E t (A t )}] Proof. Lemma 2. T t=1 ∆ t P{H t } ≤ T t=1 i∈At ∆ t P{H i,t } = T t=1 i∈At ∆ t P{|μ (i) t -µ (i) | ≥ ∆ t 2m } = d i=1 T t=1 ∆ t P{i ∈ A t , |μ (i) t -µ (i) | ≥ ∆ t 2m } ≤ ∆ max d i=1 T t=1 P{i ∈ A t , |μ (i) t -µ (i) | ≥ ∆ min 2m } ≤ ∆ max d i=1 T t=1 exp(- ∆ 2 min t 8m 2 C (ii) ) ≤ 8dm 2 max i {C (ii) }∆ max ∆ 2 min .
Proof. Lemma 4.

A * (µ -μt ) = -A * D -1 t t-1 s=1 I As C 1 /2 s = -A * D -1 t t-1 s=1 I As∩A * C 1 /2 s = -A * D -1 t (D + t-1 s=1 C As∩A * ) 1 /2 (D + t-1 s=1 C As∩A * ) -1 /2 t-1 s=1 I As∩A * C 1 /2 s ≤ A * D -1 t (D + t-1 s=1 C As∩A * )D -1 t A * t-1 s=1 I As∩A * C 1 /2 s (D+ t-1 s=1 C As∩A * ) -1
where the last step is the Cauchy-Schwarz inequality. Since

I A * D λI A * Σ C D t , A * (µ -μt ) ≤ λA * Σ C D -1 t A * + A * D -1 t V t D -1 t A * 2I Vt+D ( ) .
We proved

P A * (µ-μ t )≥ 2 f (δ t )A * D -1 t (λΣ C D t +V t )D -1 t A * t∈D a ≤ P I Vt+D ( )≥ f (δ t )|t∈D a .
Proof. Lemma 5. Let F t be the σ-algebra σ(A 1 , 1 , . . . , A t-1 , t-1 , A t ). Let f (u) be the density of a multivariate normal random variable independent of all other variables with mean 0 and covariance D -1 . Then from the proof of lemma 9 of [START_REF] Abbasi-Yadkori | Improved Algorithms for Linear Stochastic Bandits[END_REF],

M t (D) = det D det(D + V t ) exp(I Vt+D ( )) = R d exp u t-1 s=1 I As∩A * C 1 /2 s - 1 2 u t-1 s=1 C As∩A * u f (u)du
We define the following quantities, for u ∈ R d ,

M u t = exp u t-1 s=1 I As∩A * C 1 /2 s - 1 2 u t-1 s=1 C As∩A * u , D u s = exp u I As∩A * C 1 /2 s - 1 2 u C As∩A * u such that M u t = t-1 s=1 D u s .
From the subgaussian property of s , E[D u s |F s ] ≤ 1.

E[M u t |F s-1 ] = E[ t-1 s=1 D u s |F s-1 ] = ( t-2 s=1 D u s )E[D u t-1 |F t-1 ] ≤ M u t-1 .
Thus M u t is a supermartingale and

E[M u 1 ] = E[D u 1 ] ≤ 1. So for all t, E[M u t ] ≤ 1. Finally, E[M t (D)] = E u E[M u t |u]] ≤ 1.
Proof. Lemma 6.

We have

-1 /2 V t D -1 /2 1+η λ D -1 /2 t Σ -1 /2 C V t Σ -1 /2 C D -1 /2 t
, which is 1+η λ times a matrix with m ones and d -m zeros on the diagonal. The determinant of a positive definite matrix is smaller than the product of its diagonal terms, so

det(I d + D -1 /2 V t D -1 /2 ) ≤ det(I d + 1 + η λ D -1 /2 t Σ -1 /2 C V t Σ -1 /2 C D -1 /2 t ) ≤ (1 + 1 + η λ ) m .
Proof. Lemma 7.

Let j 0 such that β j0,e ≤ 1/m. Then for all j > j 0 , A j t,e = {|S j t,e | ≥ 1; ∀k < j 0 , |S k t,e | < mβ k,e ; ∀k ∈ {j 0 , . . . , j -1}, |S k t,e | = 0} .

But as the sequence of sets (S j t,e ) j is decreasing, {|S j0 t,e | = 0} and {|S j t,e | ≥ 1} cannot happen simultaneously. A j t,e cannot happen for j > j 0 .

Proof. Lemma 8. First we rewrite A t,1 , following [START_REF] Branislav Kveton | Tight regret bounds for stochastic combinatorial semi-bandits[END_REF],

A t,1 = ∩ j0 j=1 A j t,1 = ∩ j0 j=1 {|S j t,1 | < mβ j,1 } ∪ (∪ j-1 k=1 {|S k t,1 | ≥ mβ k,1 }) = ∩ j0 j=1 {|S j t,1 | < mβ j,1 } = (∩ j0-1 j=1 {|S j t,1 | < mβ j,1 }) ∩ {|S j0 t,1 | = 0} .
The complementary set of

S j t,1 in A t is S j t,1 = {i ∈ A t , i / ∈ S j t,1 }. If we have A t,1 , then S j0 t,1 = A t and thus i∈At Γ (ii) n (i) t = j0 j=1 i∈S j t,1 \S j-1 t,1 Γ (ii) n (i) t < j0 j=1 i∈S j t,1 \S j-1 t,1 ∆ 2 t 8f (t)g 1 (m, γ t )α j,1 = ∆ 2 t 8f (t)g 1 (m, γ t ) j0 j=1 |S j t,1 \ S j-1 t,1 | α j,1 < m∆ 2 t 8f (t)g 1 (m, γ t )   j0 j=1 β j-1,1 -β j,1 α j,1 + β j0,1 α j0,1   , (3)
where (3) follows the same steps as lemma 4 of [START_REF] Branislav Kveton | Tight regret bounds for stochastic combinatorial semi-bandits[END_REF]. Proof of the second statement of the lemma: First, follow the same steps as before to get i∈At

Γ (ii) n (i) t < m∆ t 8f (t)g 2 (m, γ t )   j0 j=1 β j-1,2 -β j,2 √ α j,2 + β j0,2 √ α j0,2   .
Then take the limit when j 0 → +∞.

Proof. Lemma 10. We break the events A j t,e into sub-events A j,a t,e = A j t,e ∩ {a ∈ A t , n C Finding the best sequences for the sums indexed by 1.

The constraints on the four sequences (α i,1 ) i≥1 , (α i,2 ) i≥1 , (β i,1 ) i≥0 and (β i,2 ) i≥0 are that they must be positive decreasing with limit 0, β 0,1 = β 0,2 = 1 and lim j→+∞ β j,2 / √ α j,2 = 0.

For i ≥ 1, we take β i,1 = α i,1 = β i with β ∈ (0, 1). Then j 0,1 = log m log 1/β and l 1 j0,1 j=1 αj,1 βj,1 = j 2 0,1 (1/β -1) + j 0,1 ≤ j 2 0,1 /β. We take β i,2 and α i,2 as in [START_REF] Branislav Kveton | Tight regret bounds for stochastic combinatorial semi-bandits[END_REF]: β i,2 = β i 2 with β 2 = 0.236; α i,2 = 1-β2 √ α-β2 2 α i , with α = 0.146. Then +∞ j=1 αj,2 βj,2 ≤ 45 and l 2 ≤ 1. The optimal choice for β is close to 1/5, value for which we get the wanted regret bound.

We now show that the choice of α j,1 and β j,1 made previously is close to optimal among the sequences with α j,1 = β j,1 .

Lemma 11. Suppose that for all j, α j = β j . Then the optimal value v of ( ) is such that v ≥ 1.54 log 2 m .

Proof. We want to minimize j 0 j0 j=1 ( βj-1 βj -1) under the constraint that j 0 = min{j : β j ≤ 1 m }. Let h j = βj-1 βj -1, then the decreasing constraint on the (β j ) sequence imposes that for all j ≥ 1, h j ≥ 0. Also, β j0 ≤ 1 m implies j0 j=1

1
hj +1 ≤ 1 m .

Figure 1 :

 1 Figure 1: Left: parallel paths problem. Right: regret of OLS-UCB as a function of m and γ in the parallel paths problem with 5 paths (average over 1000 runs).

t

  any more. There are d arms, so the event can happen at most d 1 mβj e αj,e8f (T ) maxi{Γ(ii) }ge(m,γ) ∆ 2

  1 1+η I A * D t D a I A * D t . We use D = λΣ C D a + I [d]\A

* . Then λ 1+η I A * Σ C D t D. The I [d]\A * part in D is there only to satisfy the positive definiteness and has no consequence.

These matrix inequalities show that D

  Each arm a is contained in N a actions. Let ∆ a,1 ≥ . . . ≥ ∆ a,Na be the gaps of these actions and let ∆ a,0 = +∞. Then , ∆ t = ∆ a,n } Let θ j,e,a = α j,e 8f (T )Γ (aa) g e (m, γ). In the following equations, changes between successive lines are highlighted in blue.I{a ∈ A t , n I{a ∈ A t , n I{a ∈ A t , n I{a ∈ A t , n

	T t=1	∆ t I{H t ∩ G t } ≤	2 e=1	T t=1	j0 j=1	d a=1	Na n=1	∆ a,n mβ j,e	I{A j,a t,e , ∆ t = ∆ a,n }
					≤	2 e=1	T t=1	j0 j=1	d a=1	Na n=1	∆ a,n mβ j,e	I{a ∈ A t , n (a) t	≤ α j,e	8f (t)Γ (aa) g e (m, γ t ) ∆ 2 a,n
		T t=1	Na n=1 ∆ a,n (a) t	≤ α j,e	8f (t)Γ (aa) g e (m, γ t ) a,n ∆ 2	, ∆ t = ∆ a,n }
			≤	T t=1	Na n=1	∆ a,n (a) t	≤	θ j,e,a a,n ∆ 2	, ∆ t = ∆ a,n }
			=	T t=1	Na n=1	n p=1	∆ a,n (a) t	∈ (	θ j,e,a ∆ 2 a,p-1	,	θ j,e,a a,p ∆ 2	], ∆ t = ∆ a,n }
			≤	T t=1	Na n=1	n p=1	∆ a,p (a) t	∈ (	θ j,e,a ∆ 2 a,p-1	,	θ j,e,a a,p ∆ 2	], ∆ t = ∆ a,n }
			≤	T t=1	Na n=1	Na p=1	∆ a,p I{a ∈ A t , n (a) t	∈ (	θ j,e,a ∆ 2 a,p-1	,	θ j,e,a a,p ∆ 2	], ∆ t = ∆ a,n }
	α j,e	8f (t)Γ (aa) ge(m,γt) ∆ 2 ≤ T t=1 Na p=1	∆ a,p I{a ∈ A t , n (a) t	∈ (	θ j,e,a ∆ 2 a,p-1	,	θ j,e,a a,p ∆ 2	], ∆ t > 0}	t	≤
	than the threshold, we have ≤ θ j,e,a ∆ a,1 + Na p=2 θ j,e,a ∆ a,p (	1 ∆ 2 a,p	-	1 a,p-1 ∆ 2	)	pulled less
			≤	θ j,e,a ∆ a,1	I{A j t,e } ≤ ∆a,1 ∆ a,Na + θ j,e,a	1 mβ j,e x -2 dx	d a=1	I{A j,a t,e } .
	The regret that we want to bound is = θ j,e,a ∆ a,Na = θ j,e,a ∆ a,min .
				T							2	T	j0
					∆ t I{H t ∩ G t } ≤	∆ t I{A j t,e }
				t=1							e=1	t=1	j=1
											≤	2 e=1	T t=1	j0 j=1	d a=1	∆ t mβ j,e	I{A j,a t,e } .

t } that at least mβ j,e arms are not pulled often and that the arm a is one of them. Since A j t,e implies that at least β j,e m arms are

T t=1 ∆ t I{H t ∩ G t } ≤

Acknowledgements

The authors would like to acknowledge funding from the ANR under grant number ANR-13-JS01-0004 as well as EDF through the Program Gaspard Monge for Optimization And the Irsdi project Tecolere.

* V. Perchet is partially funded by the ANR grant ANR-13-JS01-0004-01, benefited from the support of the "FMJH Program Gaspard Monge in optimization and operation research" and from EDF, and also from the support of the CNRS.

We solve the following minimization problem: minimize over j 0 , (h j ):

For a fixed j 0 , the minimum in (h j ) is attained for all h j equal to m 1/j0 -1. Then we should minimize j 2 0 (m 1/j0 -1) + j 0 with respect to j 0 . We will instead write that j 2 0 (m 1/j0 -1) + j 0 ≥ j 2 0 (m 1/j0 -1) and find a lower bound with this latter expression.

Let f (x) = x 2 (m 1/x -1) for x ∈ R + . Then with y = x log m , f (x) = y 2 (e 1/y -1) log 2 m. The function g(y) = y 2 (e 1/y -1) has a unique minimum and plotting g shows that this minimum x * is such that f (x * ) ≥ 1.54 log 2 m.


Julia Stefan
email: julia.stefan@griffithuni.edu.au

Generative Methods for Automated Music Video Editing

Keywords: Music videos, generative composition, online videos, non-linear video, adaptability

In order to enhance viewer experience when watching music videos, a set of methods for generative music video editing has been developed. These algorithms use stochastic selection based on user-defined shot characteristics, as well as temporal constraints to manage narrative structures. The prototype application is introduced and demonstrated by showing two examples of software-generated music videos, and the basic concepts behind the algorithms will be explained.

Introduction

Music videos are a popular format for audio-visual experiments. In recent years, they have been used to explore the possibilities presented by online technologies and interactive applications through the use of moving images. Popular examples include The Wilderness Downtown 1 , Like a Rolling Stone 2 and Do Not Touch 3 . In comparison to feature films for instance, the shorter running time of music videos makes them a popular format for experiments. This popularity is further increased due to the genre's aesthetic flexibility and its focus on the creation of rhythm and emotional engagement rather than narrative coherence [START_REF] Vernallis | Unruly Media: YouTube, Music Video, and the New Digital Cinema[END_REF].

By implementing options for user interaction, video sequences may become more personal and therefore more engaging for viewers. Interactive online music videos have been used to explore a number of different concepts for interactivity. These include game-like videos and tree-structured, choose-your-own-adventure type narratives. Interactive online music videos also allow for new possibilities of personalisation by embedding content from social networking websites and search engines. These "hypervideos" [START_REF] Hammoud | Interactive Video: Algorithms and Technologies[END_REF] generally either depend on viewer participation during playback or preliminary input in order to generate variations. Additionally, 1 http://www.thewildernessdowntown.com 2 http://video.bobdylan.com 3 http://donottouch.org many of these videos are based on comparatively rigid structures in order to maintain coherence and to ensure that the director's concepts are still being realised.

In contrast, the research concerning generative video composition presented in this paper is based on the idea of providing variable music videos, which can be generated in real-time without the requirement of viewer interaction and which therefore depend on processes that are to some extent beyond the director's control [START_REF] Boden | What is generative art? Digital Creativity[END_REF]. Thus, the methods presented here aim to provide a new creative tool for video directors, as well as an engaging viewing experience for audiences.

Music Video Generation

This demonstration presents a prototype application of Dividation, a software for generative music video editing utilising real-time assembling of video sequences from individually prepared pools of video footage using algorithmic decision-making processes based on the creator's clip classifications.

Sequence generation is achieved using stochastic processes based on Markov chains and probabilistic structures to describe the editing dynamics. A database of sufficiently annotated original video footage is used. Assuming the individual shot to be the basic building block of these videos, a sequence is assembled shot by shot according to the video's principal key characteristics as defined by the video director.

Additional structuring methods, such as underlying ordered lists, help to ensure narrative coherence through the specification of forced shots and the definition of temporal windows within which the stochastic selections are constrained.

Demonstration

Two music videos are used to demonstrate the video generation method described above: Majestic and Eloise.

The music video Majestic consists of a simple narrative, in which the protagonist is drawn into the televised action of the musicians' performances. Six parameters are used to categorise the video content and are mapped to temporal probabilities. The mapped temporal probabilities describe the amount of visual features that should be seen during particular sections of the song. This music video uses a pool of roughly two hundred clips with a length varying from less than one second up to three minutes. An algorithmic decision-making process is then employed for both the automatic sequencing of the video footage and the cutting of the footage into shots of appropriate lengths.

In comparison, the music video Eloise uses a slightly more detailed narrative. Here, the protagonist, Eloise, is seen inside her home, while the musicians are performing the song inside her living room. A secondary protagonist singer urges the woman to leave her house and quit her bad habits, which she finally does. For this video, the editing dynamics are based on the use of three visual parameters and a predefined narrative structure. This provides an additional guide to the order of the shots. The video uses approx. 550 pre-cut clips with a length varying from less than one second up to ten seconds. In this example, the algorithmic decision-making process is only applied to the sequencing of the video content. The selected shots are played in their entirety, unless a temporal alteration is required to ensure an accurate synchronisation.

Both videos demonstrate (1) the potential of using generative composition methods for online music video creation, (2) the resulting editing aesthetics, as well as (3) some of the challenges of this process. With the use of randomness as a driving factor for sequence creation, the resulting music videos may not always be coherent to the audience and accurate enough to the editor's intentions. An appropriate management of this problem requires correct and well-balanced definitions of the probabilistic and narrative structures and constitutes a central aspect of this research.

4

Discussion and Future Outlook Further research will focus on refining the quality of the applied editing algorithms in greater detail and extending the repertoire of specific methods by taking into account the requirements introduced by different progressive and narrative structures. Furthermore, it must deal with the creation of adequate interfaces to involve the editors in the generative composition process. Compared to traditional methods of manual video editing, the creation and editing of music videos by using generative composition methods is a rather abstract creative process because it requires a stronger conceptual involvement in order to properly communicate to the composition software how to edit a specific sequence, rather than manually executing this task oneself. Ongoing research as part of this project will reveal the effectiveness of the editing algorithms in terms of viewer engagement, and its practicality for editors.


Stig Magnus Halvorsen

Kjetil Raaen

Implementing Virtual Clients in Quake III Arena

Keywords: Virtual Client, Quake III Arena, Quake 3, Load Generation

Performing server and network experiments on video games can be cumbersome because it usually requires a large number of players to generate sufficient server and network load. A solution is automated artificial intelligence-controlled virtual clients that behave as real players. This paper describes an implementation of virtual clients in the open source video game Quake III Arena, which converts the game into an open source tool for generating server load with realistic network traffic for investigating game system scalability.

Introduction

Network and server load can be generated through the use of live sessions with real people as test candidates, as it was done in [START_REF] Claypool | Latency and Player Actions in Online Games[END_REF]. Alternatively, automated artificial intelligence (AI)-controlled virtual clients, or simply "virtual clients", can be used as demonstrated in [START_REF] Raaen | Lears: A lockless, relaxed-atomicity state model for parallel execution of a game server partition[END_REF]. The latter is beneficial as it allows experiments to be done by a single scientist requiring little time and hardware. We want to follow the second approach in our research and in [START_REF] Halvorsen | Games for Research: A Comparative Study of Open Source Game Projects[END_REF], we proposed several open source games as potential tools for scientific work. None are ideal for server and network experiments because no tools are provided for server load and network traffic generation. This paper documents the addition of virtual clients to Quake III Arena (Q3A) to solve this lack of tools. Q3A is an open source game already discussed in [START_REF] Halvorsen | Games for Research: A Comparative Study of Open Source Game Projects[END_REF]. The modified game can be used as a load-generating tool that scientists may use or alter to test and evaluate their concepts.

Implementing Virtual Clients

We were inspired by Q3A's implementation of the single player game mode. The design solves a similar problem to ours because it requires some server-side logic within the client to function properly. Single-player mode is started by first launching a local and "hidden" server with a specified map, followed by launching the client logic that connects to the local server.

Our solution is designed to launch from a console, using the engine's built-in console variable (cvar) system. A virtual client can hence be enabled by setting the proper cvars through program arguments, followed by connecting to a server. The virtual client retrieves a message containing the configuration of the server on connection. This is used to create a local shadow copy of the game server, with the same loaded map, entities and configuration. The entire procedure utilizes a modified version of the local server initialization process from the original single player mode.

Once the shadow server is initialized, it sleeps approximately a second to synchronize the shadow server with the game server. The received data from the game server contains the initial position and view angles of the client, which is used to add a bot to the shadow server at the exact same position. The bot library enables the interaction of bot entities with the map. The bot's commands are transmitted to the shadow server in the same way as connected regular clients. All commands are processed in a server function that takes a given command as a parameter. The function is modified to enqueue the received command in the client's command queue. The engine notices the new command in the client queue and immediately transmits it to the game server. Updates from the game server are forwarded to the shadow server by copying the player and entity states from each received update into the bot and entity structures of the shadow server.

Results

Server with 0-48 Connected Virtual Clients

Fig. 2: CPU & Memory Utilized

To evaluate how the virtual clients affect the server, we ran an experiment with 0-48 virtual clients connected to a single, unmodified Q3A server. Figure 1 shows the server's network load. The server's Data in graph shows that bandwidth increases proportionally with the number of clients. Data out increases quadratically because each client needs updates from all the other clients within its view area [START_REF] Stefyn | Quake III Arena game structures[END_REF]. Figure 2 illustrates server CPU and memory utilization. CPU utilization increases until it reaches approximately 71% with 21 connected virtual clients. The server starts to struggle since the operating system needs to share its processing capabilities with other processes. Memory usage remains constant as the game engine always pre-allocates enough memory for the maximum number of supported clients.

Our implementation is capable of running in graphical and console mode. Table 1 shows an average of the various client types' resource usage. The data is the average of ten readings from a host with a quad core 2.6Ghz CPU (max 400%) and 4GB memory. The console version utilizes one thread, while the two others use six. The console client requires significantly less processing power and memory than the others, while network differences are minimal. The console version allows up to 57 instances on this specific host, multiple host machines should be used for large scale testing.

Evaluation & Conclusion

Q3A has been modified into a load-generating tool for investigating game system scalability, by implementing virtual clients that produce server load with authentic network traffic. Researchers can implement their concepts into the game and analyze performance differences by utilizing the virtual client support. This can be used to improve the credibility of [START_REF] Raaen | Lears: A lockless, relaxed-atomicity state model for parallel execution of a game server partition[END_REF] and similar research. Q3A is old and may not be advanced enough for some researchers, but is likely a better test platform than small prototypes such as the one utilized in [START_REF] Raaen | Lears: A lockless, relaxed-atomicity state model for parallel execution of a game server partition[END_REF]. Virtual clients may be considered complex in comparison to client packet capture and playback. However, packet traces cannot support evaluation of server processing load. The current implementation supports only one virtual client per instance of the software, wasting resources when launching multiple.

  Fig. 1: Network Load

Table 1 :

 1 Various Client Types and their System Load

	Type	CPU Memory Bandwidth in	Bandwidth out
	Regular player	252.42% 79 MB 1.64 Kb/s	5.80 Kb/s
	VC Graphical	234.26% 94 MB 2.00 Kb/s	5.14 Kb/s
	VC Console	6.94% 29 MB 1.41 Kb/s	6.00 Kb/s


David Mirk

Helmut Hlavacs
email: helmut.hlavacs@univie.ac.at

Using Drones for Virtual Tourism

In this paper we evaluate the usability of flying drones in tourism. A live video feed is streamed live from a drone to a tourist at some distance, wearing only a VR visor, and steering the drone with head movements. 1

Introduction

Virtual reality offers tourism many useful possibilities to create or extend virtual experiences that tourists may accept and use as partial alternatives for real visitation [START_REF] Guttentag | Virtual reality: Applications and implications for tourism[END_REF][START_REF] Letellier | Virtual reality -a new tool for sustainable tourism and cultural heritage sites management[END_REF]. Especially in some areas of tourism, e.g. marketing, entertainment or education virtual reality will become more and more valuable. The vision of this work is to allow users of a client software application to receive real-time video images of different places of the world and watch them locally. As a special feature, and unlike to fixed stationary webcams, the user should be as free as possible to define where the "Virtual Eye" resides and what it is looking at.

The Virtual Tourist Project

Our approach is to use a cheap off-the-shelf drone (a Parrot ARDrone 2.0 [6] [8]) as a flying camera, and be used in a live scenario by tourists to roam around remote areas and ideally be immersed in the application such that the tourist has the impression of really being there.

To fulfill the task as complete as possible, we decided to choose a development pattern which divides the control application to be developed into three main components. Firstly, the server application, which is responsible for the direct control of the ARDrone, transmitting the calculated navigation vectors to the ARDrone. The second main component defines the graphical user client (client application), which processes and transmits the direct input to the ground station via TCP. Finally, the existing SDK for this purpose must be modified and extended in order to allow the user to use a wide a range of different control devices (e.g. "Oculus Rift").

The ARDrone 2.0 is very susceptible to outer influences. Moderate wind gusts deviate the drones very quickly from their original course which leads to a behavior where the electronics of the quadrocopter try to counteract this divergence with abrupt control maneuvers. This makes it difficult to provide a stable (vibration-free) video sequence to the user [START_REF] Balas | Modelling and linear control of a quadrotor[END_REF][START_REF] Brooks | Real-time digital image stabilization[END_REF][START_REF] Czyba | European Micro Aerial Vehicle Conference and Competition[END_REF]. Furthermore, the rigid mounting of the video cameras leads to an undesirable side effect: basics quadrocopters control their flight direction by changing the speeds of their propellers and thus changes their attitude. At an acceleration to the front the drone tilts with the front camera toward the ground, on a flight back into sequence then turned toward the sky. To avoid this effect a modification with a steerable front camera on a ball joint would be necessary. A practical test arrangement showed that it is not possible to give the user complete freedom of the control over his permit virtual eyes. For this reason, a virtual route in the form of GPS waypoints must be predefined, on which the ARDrone travels within certain tolerances. As a result the user directly controls only the flight speed of the virtual tour, not the drone navigation directions. However, this allows a completely free focus and control of the front camera orientation.

Navigation

Due to the small narrow field of view of 91 degree and the rigidly mounted front camera a user-controlled direct navigation of the ARDrone would only be possible after several exercise passages. The specification of a flight course, which on the one hand is free of any obstacles (thus the risk of collisions decreases), and on the other hand provides optimized designed sightseeing courses (i.e., they lie within the flight range of the ARDrone and show the most important sights), allows the user to enjoy a satisfactory experience without the need of having knowledge of the actual flight behavior and functional ways of the quadrocopter.

Virtual Reality

The ARDrone 2.0 and the provided SDK already provides numerous possibilities for real-time symbol or character recognition to developers. Necessary calculations are made directly on the ARDrone hardware/firmware and the results are processed in a client application. The Oculus Rift is a virtual reality headset, originally designed for immersive gaming. To create a strong sense of immersion it is designed to almost fill the wearer's entire field of view and to completely block out the real world. The pincushioned image for each eye (640×800 resolution) is corrected by lenses in the headset. The used combination of 3-axis gyros, accelerometers, and magnetometers make it capable of absolute (relative to earth) head orientation tracking without drift [START_REF] Mondragon | Unmanned aerial vehicles uavs attitude, height, motion estimation and control using visual systems[END_REF][START_REF] Tico | Robust method of digital image stabilization[END_REF][START_REF] Silven | Video stabilization performance assessment[END_REF].

Conclusion and Future Work

The aim of this project was to develop a system that allows a user from anywhere on the world to control a ARDrone 2.0 via the Internet where the direct control of the direction of the quadrocopter is exclusively managed by the server application and only the alignment of the front camera is assumed by the user. However, the difficulties and problems that occurred while developing and testing this solution with the consumer grade Parrot ARDrone 2.0, led us to the conclusion that for a practicable use of the Virtual Tourist in tourism, new quadrocopter model has to be chosen, which fulfills more of the given requirements.

Fig. 1 .Fig. 2 .

 12 Fig. 1. View through Oculus Rift (Carinthia/Austria)


Patrick Ng

Keith Nesbitt

Karen Blackmore
email: karen.blackmore@newcastle.edu.au

H Ng

Informative Sound and Performance in a Team Based Computer Game

Keywords: Dota 2, Auditory Display, Auditory Icons, Earcons. 1

This study focuses on the role of sound in the popular multiplayer online battle arena game, Dota 2. Our initial results indicate that team performance improves with the use of sound. By contrast, some individuals performed better with sound and some without.

Introduction

For game developers, integrating informative sound has the potential to provide additional feedback to the player. In this paper we explore the relationship between sound and performance by evaluating the role of sound in player performance in the multiplayer online battle arena game, Dota 2.

Prior works within the field of auditory display have identified two key ways that sound can be used to improve the functionality and efficiency of user feedback Gaver described the design of 'Auditory Icons' in the interface, an approach that builds on the everyday listening skills of users [START_REF] Gaver | Auditory Icons: Using Sound in Computer Interfaces[END_REF]. Blattner suggested an alternative means of creating auditory messages called 'Earcons', that rely upon musical conventions such as pitch, timbre and dynamics to communicate abstract information [START_REF] Blattner | Earcons and icons: their structure and common design principles[END_REF].

Research conducted on video game audio and performance has shown mixed results in regards to whether sound has a positive or negative impact on performance. Tafalla reported that participants playing the game DOOM with the soundtrack scored almost twice as many points to those playing without the sound [START_REF] Tafalla | Gender differences in cardiovascular reactivity and game performance related to sensory modality in violent video game play[END_REF]. In contrast, Yamada et al found that the presence of music had a negative effect on performance [START_REF] Yamada | The effects of music on the performance and impression in a racing game[END_REF]. Further studies into the effects of sound on performance levels have found that players perform the weakest when playing without sound while the highest scores were obtained when playing with music unrelated to the game [START_REF] Tan | Effects of Built-in Audio versus Unrelated Background Music on Performance in an Adventure Role-Playing Game[END_REF]. Each of these findings suggest that sound could play a factor on players performance levels in games.

As information gathering plays an important task for players in most games, further research is required to better understand the role sound plays in performance. To this end, this preliminary study was conducted to examine the effects of informative sound in a team-based game. The main question we consider in this research is: "Can sound be used to improve player performance in computer games?"

Evaluating Performance

A total of 20 participants (19 males, 1 female) took part in this experiment. Of these participants, 18 were undergraduate students aged between 18-25 years while 2 participants were postgraduate students aged between 26-40 years. In the sound on condition, players were required to have the in game background music and sounds from the game turned on. This included voice chat. Participants in the sound off condition were not allowed to have any sounds from the game on and played in complete silence. Other sounds, such as personal music, were not allowed in either of the two conditions. In both conditions players were allowed to communicate using text based chat to each. The server selected to host all matches was US west. This server provided the best possible latency levels for all players based on their Internet connection speeds. The game mode selected was all pick which allows player's access to all heroes in the game.

We recorded a total of 140 comparative measures (7 performance measures x 5 players x 4 teams) for analyzing individual performance. Of these 82 showed improvements in performance when sound is included, 10 showed no difference and 48 displayed a reduction in performance. We collated the individual performance data further, calculating the average individual results across the 7 measures. Out of these 7 measures, 1 showed a reduction in performance, 6 showed improvements when sound was present (see table 1). The difference for the measure of 'Hero levels' was found to be significant. In addition to recording individual performances, we also recorded 16 team measures in total (4 teams x 4 performance) for measuring team performance. Out of these, nine showed an increase in performance with sound on while seven showed a decrease in performance. We analysed the team performance data further, calculating the average team results for the three expert teams (see table 2). Out of the 4 measures, 3 showed improvements in performance when sound is present while only 1 measure recorded a reduction in performance with sound.

Discussion

In this study we have undertaken a preliminary examination of the role of information and sound in video games. Specifically, we looked at whether sound could offer improved performance levels in the multiplayer online battle arena game, Dota 2. In our preliminary experiment, we attempted to measure the difference in performance levels by adding and removing sound from the gameplay. We tested both individual and team performance levels in two different sound conditions (on and off) using seven individual and four team measures. Our analysis of the initial results has shown mixed results in terms of whether players and teams performance actually improved when there is sound. While over half of the total individual comparative measures have shown improved performance with sound, 58 displayed either no difference or a reduction in performance. We also found a similar pattern in team performance where 9 of the comparative measures displayed an increase with sound while 7 showed a reduction in performance. A post survey conducted after the experiment revealed that 18 of the 20 players felt that removing sound affected their performance negatively. The next stage of our work will address some of the issues encountered with the design of this preliminary study. We will focus on two expert teams who play an extended number of games against each other so that the additional data gathered might highlight further significant differences in performance.

Table 1 .

 1 Average Individual Performance with Sound On and Sound Off

	Individual Measure	Sound Off	Sound On
	Hero Levels*	17.2	18.6
	Hero Kills	6.8	7.1
	Hero Deaths	10.8	11.5
	Kill Assists	7.1	7.4
	Total Gold Earned	12555	13170
	Gold per Minute	312.8	314.8
	Experience Points per Minute	427.9	453.8

Table 2 .

 2 Average team performance (3 expert teams)

	Team Measure	Sound Off	Sound On
	Total Gold Earned	62383.3	64331.7
	Total Experience Points Earned	85693.3	94206.7
	Hero Kills	35.7	37.8
	Hero Deaths	7.1	7.4